[PDF] [PDF] CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

[PDF] Congruences et équations diophantiennes - Université de Sherbrooke

Divisibilité et congruences les congruences modulo, les r`egles de divisibilité des nombres et autres sont satisfaisant les r équations de congruence

[PDF] Congruences et théorème chinois des restes - Apprendre-en-lignenet

Résolution des équations sur les congruences Supposons que l'on cherche à résoudre : 3x ≡ 5 (mod 7) Cela est facile car le modulo est premier : On sait que  

[PDF] CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

pour la division (et la simplification des congruences), c'est plus compliqué Exemple : 2 ≡ 16 et [5] H W Lenstra, Jr Solving the Pell equation Notices Amer

[PDF] Ch 7 Congruences - LACIM

congruence 2x≡ 4mod 6 a les deux solutions x= 2 et x=5, qui sont non congrus modulo 6 7 11 Théorème L'équation ax≡ b mod n a une solution dans Z si et 

[PDF] DIVISIBILITÉ ET CONGRUENCES - maths et tiques

≡1145 × 4 7⎡⎣⎤⎦ ≡ 4 7⎡⎣⎤⎦ Le reste est égal à 4 Méthode : Résoudre une équation avec des congruences Vidéo https://youtu be/Hb39SqG6nbg

[PDF] Congruences, applications

p est exactement égal `a l'ensemble des racines de l'équation X(p−1)/2 = 1 la loi de réciprocité quadratique, le résultat ne dépend que de la congruence

[PDF] Cours S4 : Mathématiques pour linformatique

1 5 Équations en nombres entiers ou diophantiennes 23 1 7 Exemples d'équations de congruences C'est la congruence modulo m

[PDF] Les congruences Principe des congruences Les congruences sont

Pour déterminer des congruences modulo n , on élimine du nombre les multiples que c'est une équation avec des congruences qu'on demande de résoudre

[PDF] ÉQUATIONS DIOPHANTIENNES MODULO N - Normale Sup

Pour résoudre des équations diophantiennes, on a souvent recours à des congruences en considérant l'équa- tion modulo N Mais quel modulo N choisir ?

[PDF] exercices corrigés sur les congruences pdf

[PDF] cours coniques terminale pdf

[PDF] cours conique bac math tunisie

[PDF] conique hyperbole

[PDF] conique cours

[PDF] conique parabole

[PDF] conique exercice corrigé

[PDF] exercices corrigés coniques terminale s pdf

[PDF] conjecture geometrie

[PDF] limite de

[PDF] suite définie par récurrence limite

[PDF] conjecture d'une suite

[PDF] comportement d'une suite exercices

[PDF] comportement d'une suite 1ere s

[PDF] conjecturer le comportement d'une suite ? l'infini

CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

1.Congruences

Définition 1.1.Soitm;a;bentiers. On dit queaest congru àbmodulomsimdiviseab. (On dit aussi que "aetbsont congrus modulom".) En symboles ab(modm)()mjab() 9k2Zavecab=kn. Par exemple on a28 (mod 3)car3divise28 =6. On aa0 (mod 2)si et seulement si2divisea0 =a, c"est à dire ssiaest pair. On aa1 (mod 2)ssi il existek aveca1 = 2ket donca= 2k+ 1est impair. Similairement on a a2 (mod 5)()a= 5k+ 2aveckentier, a1 (mod 4)()a= 4k+ 1aveckentier, a3 (mod 4)()a= 4k+ 3aveckentier.

Surtout on aa0 (modn)()a=nkaveckentier.()aest un multiple denQuelques propriétés de la congruence

Théorème 1.2.Soita;b;c;a0;b0;nentiers. Les énoncés suivants sont vrais : (a) (Reflexivité)aa(modn). (b) (Symétrie)ab(modn)impliqueba(modn). (c) (Transitivité)ab; bc(modn)impliqueac(modn). (d)aa0; bb0(modn)impliqueaa0bb0(modn). (e)aa0; bb0(modn)impliqueaa0bb0(modn). (f)Sidest un diviseur commun dea,betn, alorsab(modn)impliquead bd (modnd (g)Siddivisen, alorsab(modn)impliqueab(modd). Donc les règles de manipulation des congruences contiennent la plupart des règles de ma-

nipulations d"égalités entre entiers pour l"addition, la soustraction, et la multiplication. Mais

pour la division (et la simplification des congruences), c"est plus compliqué. Exemple :216et310 (mod 7)impliquent231610et donc6160 (mod 7).

Preuve.(a)aa= 0 = 0n.

(b)ab=kn=)ba=kn. (c)ab=kn; bc=`n=)ac= (ab) + (bc) = (k+`)n. (d) Laissée comme exercice. (e)aa0=kn; bb0=`n=)aba0b0=aba0b+a0ba0b0= (aa0)b+a0(bb0) = (kb+a0`)n. (f) Laissée comme exercice. (g) Sidjnetnjab, alorsdjab. Théorème 1.3.Soientnetaentiers avecn1. Alorsaest congru modulonà exactement un des nombres0;1;2;:::;n1. 26
CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE 27 Donc chaque entier est congru à0ou1modulo2, mais pas aux deux. Chaque entier est congru à0,1ou2modulo3, mais pas à plus qu"un parmi les trois. Etc. Preuve.Par la division euclidienne, on peut écrirea=qn+ravecq;rentiers et0r n1. Etar(modn)car leur différence estqn. Doncaest congru à un des nombres

0;1;2;:::;n1.

Supposons maintenant queaest congrus à deux nombresretsparmi0;1;:::;n1. Par symétrie et transitivitéretssont aussi congrus, et il existekentier avecrs=kn. Or on a0r < netn Commekest entier, on ak= 0etr=s.

2.Les congruencesaxb(modn).

On cherche les solutionsxde congruences commes7x11 (mod 31)et en généralaxb (modn). On considère d"abord le cas oùaetnsont premiers entre eux, comme7et31. Théorème 2.1.Siaetnsont premiers entre eux, alors il existe une solutionxdeaxb (modn), et c"est unique modulon. Existence.On cherche une relation de Bezout7u+ 31v=1par l"algorithme d"Euclide

étendu.+++

a i423 u i317310 7p i014931 +31q
i10127 On trouve31279 =1. Modulo31, on a310, donc cela devient791 (mod 31). On multiplie par11donnant791179911 (mod 31), et on réduit modulo31par la division euclidienne99 = 331+6. Donc996et7611 (mod 31). Finalement pour tout x6 (mod 31)on aura aussi7x11 (mod 31). A noter que dans la relation de Bezout on utilise le numérateur9et le dénominateur2de l"avant-dernière réduite de 317
, avecsignes opposés. La même méthode marche pour toute congruenceaxb(modn)tant queaetnsont premiers entre eux. Unicité.En général, siaetnsont premiers entre eux, et on aaxbetayb(modn), alors on aaxay(modn)par transitivité, et doncaxay0eta(xy)0 (modn). Doncndivisea(xy). Maisaetnsont premiers entre eux. Donc par le lemme de Gauss,n doit diviserxy, et doncxetysont congrus modulon.

Le cas oùaetnnon premiers entre eux.

Théorème 2.2.Il existe une solutionxdeaxb(modn)si et seulement sid= pgcd(a;n) diviseb. La solutionxest unique modulond La condition queddivisebest nécessaire, c"est à dire, si la congruence a une solution, alors ddiviseb. En effet, si on aaxb(modn), alors il existekentier avecaxb=knet b=axkn. Commeddiviseaetn, il divise aussiaxkn=b. La condition queddivisebest suffisante aussi, c"est à dire, siddiviseb, alors la congruence a une solution. En effet, siddiviseb, alors en appliquant l"algorithme d"Euclide étendu àn

28 CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

eta, on trouveu= (1)NpN1etv= (1)N1qN1avecau+vn=d. Cela donneaud (modn). En multipliant parbd on trouvera(ubd )b(modn).

La congruenceaxb(modn)est équivalente àad

xbd (modnd )avecad etnd premiers entre eux. Comme les solutions de cette dernière congruence sont uniques modulo nd , les solutions deaxb(modn)sont uniques modulond aussi.

Deux exemples :

(1) Dans la congruence36x80 (mod 90), on apgcd(36;90) = 18, mais18ne divise pas

80. Donc il n"y a pas de solution.

(2) Pour résoudre125x275 (mod 450), on applique l"algorithme d"Euclide étendu à450 et125+++ a i3112 u i4501257550250 125p
i0134718 +450q
i101125 On trouve125(7)+4502 = 25, et donc125(7)25 (mod 450). Maintenant on multiplie par 27525
= 11, donnant125(77)275 (mod 450). La solution est unique modulo45025 = 18, donc la solution estx 77 (mod 18)ou bienx13 (mod 18).

3.Le théorème chinois

Le théorème chinois.Soitmetndes entiers premiers entre eux. Alors quelque soitaet bentiers il existe des solutions simultanées dexa(modm)etxb(modn), et cette solutionxest unique modulomn. Unicité.Soitxune solution simultanée des deux congruences, et soityun deuxième entier. Alorsyest aussi une solution des deux congruences ssi on axy(modm)etxy (modn). Alorsmjxyetnjxy, ce qui équivaut à ce queppcm(m;n)jxyouxy (mod ppcm(m;n)). Mais commemetnsont premiers entre eux, on appcm(m;n) =mn. Doncyest aussi une solution des deux congruences ssixy(modmn). Existence.On cherche une relation de Bezoutmu+nv= 1. Alors on anv= 1muet mu= 1nv. Il s"ensuit qu"on a nv1 (modm); mu0 (modm);nv0 (modn); mu1 (modn): Il s"ensuit que si on prendx=anv+bmuon a bienxa1 +b0a(modm)et xa0 +b1b(modn). Faisons un exemple. Cherchons lesxavecx11 (mod 18)etx25 (mod 77). On cherche une relation de Bezout18u+ 55v= 1.++++ a i43112 u i771853210 18p i01413173077 +77q
i10134718 On a1830+77(7) = 1avecu= 30etv=7. La solution estx1177(7)+251830

7571. Comme on a1877 = 1386, les solutions sontx7571641 (mod 1386).

CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE 29 Quandmetnne sont pas premiers entre eux, on a le théorème suivant. Théorème 3.1.Soitmetnentiers naturels, etd= pgcd(m;n). Alors il existe une solution simultanéexdexa(modm)etxb(modn)si et seulement si on aab(modd). La solutionxest unique moduloppcm(m;n). Existence.Soity=xa. On chercheyvérifianty0 (modm)etyba(modn). Par le lemme de Bezout il existeuetvavecmu+nv=d. On a doncmu0 (modm)etmud (modn). Comme on aab(modd), le nombrebad est entier. On prendy=mubad et donc x=a+mubad comme solutions. Unicité.Similaire au cas oùmetnsont premiers entre eux.

4.Systèmes de représentants modulon

Définition 4.1.Une famille denentiersa1;:::;antelle que tout entier est congru à modulo nà exactement un desaiestun système de représentants modulon. Donc0;1;2;3;4est un système de représentants modulo5. On peut substituer5pour0, car ils sont congrus modulo5, et1;2;3;4;5est un système de représentants modulo5. Les entiers congrus à1;2;3;4 (mod 5)y restent; les entiers congrus à0sont congrus aussi à

5. Similairement on peut passer de0;1;2;3;4à0;1;2;2;1 =2;1;0;1;2car3 2

et4 1 (mod 5). Les entiers congrus à0;1;2continuent à l"être, ceux congrus à3sont congrus à2, et ceux congrus à4sont congrus à1. En général, si on prend certains nombresa1;a2;:::;arde la liste0;1;2;:::;n1et on les remplace parb1;b2;:::;bravecaibi(modn)pour touti, alors on a toujours un système de représentants modulon.

Théorème 4.2.Soientnetaentiers avecn1.

(a)Sin= 2k+ 1est impair, alorsaest congru modulonà exactement un desnentiers k;:::;1;0;1;:::;k. (b)Sin= 2kest pair, alorsaest congru modulonà exactement un desnentiers (k1);:::;1;0;1;:::;k1;k. Dans les deux casaest congru modulonà exactement un entieravecn2 < n2 Preuve.Le théorème précédent dit que chaque entieraest congru modulonà exactement un entierravec0r < n. Si0rn2 , on pose=r. Sinon, on an2 < r < n, et on pose =rn, et on an2 < <0, et on a toujoursarrn(modn). Doncaest congru modulonà exactement un entier dansn2 ;0[0;n2 =n2 ;n2 Théorème 4.3.Soita1;a2;:::;anune famille denentiers avec la propriété queai6=aj (modn)pour touti6=j. Alorsa1;a2;:::;anest un système de représentants modulon.

Preuve.Considérons l"application

fa1;a2;:::;ang ! f0;1;2;:::;n1g a i7!reste de la division euclidienne deaiparn: Aucun entier parmif0;1;2;:::;n1gn"a plus qu"un antécédent, car siaietajavait le même rester, on auraitairaj(modn), qui est exclu par hypothèse sauf pouri=j. Donc l"application est injective. Une application injective entre deux ensembles du même cardinal fini est toujours bijective. Donc chaque entierkparmif0;1;2;:::;n1ga exactement un antécédent qu"on noteraaik.

30 CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

Maintenant tout entier est congru modulonà exactement un entierkparmif0;1;2;:::;n

1get à exactement un entieraikparmifa1;a2;:::;ang.

5.Les carrés modulon

Chercher les carrés modulonsignifie chercher les nombreskparmi0;1;:::;n1pour lesquels il existe unaaveca2k(modn). Commeab=)a2b2(modn), on peut se restreindre par le théorème 4.2 auxaavecn2 < an2 . Mais comme(a)2a2(modn), on peut même se restreindre auxapositifs dans cette liste, c"est à dire à0;1;:::;n2 .Les carrés modulonsont les restes de la division euclidienne parnde02;12;22;:::;n2

2.Par exemple, modulo10on a

0

20;121;224;329;426;525 (mod 10)

Donc0,1,4,5,6,9sont des carrés modulo10, mais2,3,7,8ne sont pas des carrés modulo

10. La représentation décimale d"un carré termine toujours en0,1,4,5,6ou9.

Modulo4on a020,121, et220 (mod 4). Modulo8on a

0

20;121;224;321;420 (mod 8):

D"où :

Théorème 5.1.(a)Tout carré est congru à0ou1modulo4. (b)Tout carré est congru à0,1, ou4modulo8. Théorème 5.2.(a)Aucun nombre de la forme4k+3n"est la somme de deux carrésa2+b2. (b)Aucun nombre de la forme8k+ 7n"est la somme de trois carrésa2+b2+c2. Preuve du théorème 5.2.(a) L"énoncé est équivalent àa2+b263 (mod 4)pour toutaetb entiers. Mais on aa20ou1, etb20ou1 (mod 4). Donca2+b2est congru à0 + 0ou

0+1ou1+0ou1+1modulo4. Les valeurs possibles sont0,1,2seules. Et3n"est pas atteint

comme une valeur dea2+b2(mod 4). (b) Exercice.

6.Arithmétique modulo un premierp

Théorème 6.1.Soitppremier. Siab0 (modp), alorsa0oub0 (modp). C"est une réécriture du théorème : "Sipest premier etpjab, alorspjaoupjb." Corollaire 6.2.Soitppremier, etc60 (modp). Siacbc(modp), alorsab(modp). Preuve.Siacbc(modp), alors(ab)c0 modp. Par le théorème, on aab0ou c0 (modp). Mais par hypothèse, on ac60 (modp). Donc c"estab0et ensuiteab (mod 0). Corollaire 6.3.Soitppremier. Sia2b2(modp), alorsa b(modp). A noter que si on remplace le premierppar un entier quelconque, les conclusions du théo- rème et du corollaires devient fausses. Par exemple on a420 (mod 8), mais460et260 (mod 8). Et on a123252721 (mod 8), mais16 3 (mod 8). Mais8n"est pas premier. CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE 31 Preuve.Dea2b2(modp)on déduita2b20et(ab)(a+b)0 (modp). Le théorème précédent montre alors queab0oua+b0 (modp). D"oùaboua b(modp). Théorème 6.4.Soitppremier etaentier aveca60 (modp). Alors pour toutcil existequotesdbs_dbs13.pdfusesText_19