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

View - Download CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

Previous PDF

Next PDF

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 existe une solutionxde la congruenceaxc(modp), et cette solution est unique modulop. Preuve.Pourppremier, la conditiona60 (modp)implique queaetpsont premiers entre eux. Donc le théorème actuel est le cas particulier du théorème 2.1 avecn=pun premier. On a dit que0;1;2;:::;p1forment un système de représentants modulop. Si on supprime le0et on prend le produit des autres on trouve123(p1)60 (modp)par le théorème

6.1 car aucun des facteurs n"est congru à0.

Soit0;a1;a2;:::;ap1un autre système de représentants modulopcontenant0. Alors pour

chaquekparmi1;:::;p1il y a exactement unikparmi1;2;:::;p1tel quekaik(modp). De plusik6=ijpourk6=j. Donc on a

a

1a2a3ap1ai1ai2ai3aip1on permute les facteurs

123(p1) (modp)carai11,ai22, etc.

On a montré

Lemme 6.5.Soitppremier et0;a1;:::;ap1un système de représentants modulopcontenant

0. Le produit de ses membres non nuls vérifiea1a2ap112(p1)(p1)! (modp).

Théorème 6.6.Soitppremier eta60 (modp). Alors on aap11 (modp). Par exemple, modulo7on a161,26= 641,36= 7291,4640961, 5

6= 156251,66= 466561 (mod 7).

Preuve.Considérons lespentiers

a0 = 0; a1; a2; ::: ; a(p1): Dans cette liste on aai6aj(modp)pouri6=j, car on ai6j(modp)pouri6=j(vu que0;1;:::;p1est un systéme de représentants modulop) et on a le corollaire 6.2. Donc c"est un système de représentants modulop(théorème 4.3). Par le lemme, on a donc (a1)(a2)(a(p1))12(p1) (modp):

En regroupant cela donne

a p1(p1)!(p1)!1(p1)! (modp): Or(p1)!60 (modp)car aucun de ses facteurs n"est pas0et on a le théorème 6.1. Donc on peut simplifier par(p1)!dans la congruence (corollaire 6.2) et trouverap11 (modp). Théorème de Fermat.Soitppremier etaentier. Alorsapa(modp). Preuve.On deux cas : soita60 (modp), soita0 (modp). Dans le premier cas, on applique le théorème précédent et on trouveap11etap aap1a1a(modp).

Dans le second cas, on aap0p0a(modp).

32 CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

Soit maintenantppremier. On veut évaluer(p1)!modulopcomme suit. Par par le théorème 6.4, associé à chaque entierx2 f1;2;:::;p1gest un entieryavec xy1 (modp), et cetyest unique modulop. On peut prendre cetydansf1;2;:::;p1g. (On appelle cetyl"inverse dexmodulop.) Si àxon associeypar cette procédure, alors àyon associexcarxy1 (modp)se lit aussiyx1 (modp). Donc on peut diviser f1;2;:::;p1gen des sous-ensemblesfxi;yigdisjoints avecxiyi1. Par exemple, pourquotesdbs_dbs35.pdfusesText_40

[PDF] calcul modulo 23

[PDF] clé de contrôle sécurité sociale

[PDF] 11 modulo 10

[PDF] calcul modulo 97

[PDF] personnage du livre moi boy

[PDF] escadrille 80 questionnaire de lecture

[PDF] controle de lecture moi boy

[PDF] moi boy roald dahl pdf entier

[PDF] moi boy roald dahl résumé

[PDF] moi boy roald dahl pdf gratuit

[PDF] séquence pluriel des noms ce2

[PDF] no et moi telecharger pdf

[PDF] leçon pluriel des noms ce2 lutin bazar

[PDF] no et moi avis argumenté

[PDF] séquence pluriel des noms ce1