Exo7 - Cours de mathématiques

1 Arithm tiqueVid o partie 1. Division euclidienne et pgcdVid o partie 2. Th or me de B zoutVid o partie 3. Nombres premiersVid o partie 4. CongruencesFiche d exercices Arithm tique dansZPr ambuleUne motivation : l arithm tique est au c ur du cryptage des communications. Pour crypter un message on commencepar le transformer en un ou plusieurs nombres. Le processus de codage et d codage fait appel plusieurs notionsde ce chapitre : On choisit deuxnombres premierspetqque l on garde secrets et on posen=p q. Le principe tant que m meconnaissantnil est tr s difficile de retrouverpetq(qui sont des nombres ayant des centaines de chiffres). La cl secr te et la cl publique se calculent l aide de l algorithme d Euclideet descoefficients de B zout. Les calculs de cryptage se ferontmodulon. Le d codage fonctionne gr ce une variante dupetit th or me de Division euclidienne et Divisibilit et division euclidienneD finition ,b Z.

2 On dit quebdiviseaet on noteb|as il existeq Ztel quea= 1. 7|21 ; 6|48 ;aest pair si et seulement si 2|a. Pour touta Zon aa|0 et aussi 1|a. Sia|1 alorsa=+1 oua= 1. (a|betb|a)= b= a (a|betb|c)= a|c (a|beta|c)= a|b+cTh or me 1(Division euclidienne).Soit a Zet b N\{0}. Ilexistedes entiers q,r Ztels quea=bq+ret06r<bDe plus q et r TIQUE1. DIVISION EUCLIDIENNE ET PGCD2 Terminologie :qest lequotientetrest avons donc l quivalence :r=0 si et seulement calculerqetron pose la division classique . Sia=6789 etb=34 alors6789=34 199+23On a bien 0623<34 (sinon c est que l on n a pas t assez loin dans les calculs).6 7 8 9341993 43 3 83 0 63 2 93 0 62 3dividendediviseurquotientresteD peut supposera>0 pour simplifier. SoitN= n N|bn6a . C est un ensemble non vide carn=0 N. De plus pourn N, on an6a. Il y a donc un nombre fini d l ments dansN, notonsq=maxNleplus grand l b6acarq N, et(q+1)b>acarq+1/ N, doncq b6a<(q+1)b=q b+ d finit alorsr=a q b,rv rifie alors 06r=a q b<.

3 Supposons queq ,r soient deux entiers qui v rifient les conditions du th or me. Tout d aborda=bq+r=bq +r et doncb(q q )=r r. D autre part06r <bet 06r<bdonc b<r r<b(notez au passage lamanipulation des in galit s). Maisr r=b(q q )donc on obtient b<b(q q )<b. On peut diviser parb>0pour avoir 1<q q <1. Commeq q est un entier, la seule possibilit estq q =0 et doncq=q . Repartant der r=b(q q )on obtient maintenantr=r . pgcd de deux entiersD finition ,b Zdeux entiers, non tous les deux nuls. Le plus grand entier qui divise la foisaetbs appelle leplusgrand diviseur commundea,bet se note pgcd (a,b).Exemple 3. pgcd (21, 14)=7, pgcd (12, 32)=4, pgcd (21, 26)=1. pgcd (a,ka)=a, pour toutk Zeta>0. Cas particuliers. Pour touta>0 : pgcd (a, 0)=aet pgcd (a, 1)= Algorithme d EuclideLemme a,b N . crivons la division euclidienne a=bq+r. Alorspgcd(a,b)= pgcd (b,r)En fait on a m mepgcd(a,b)= pgcd (b,a q b)pour toutq Z.

4 Mais pour optimiser l algorithme d Euclide onapplique le lemme avecqle allons montrer que les diviseurs deaet debsont exactement les m mes que les diviseurs debetr. Cela impliquera le r sultat car les plus grands diviseurs seront bien s r les m mes. Soitdun diviseur deaet deb. Alorsddivisebdonc aussibq, en plusddiviseadoncddivisea bq= TIQUE1. DIVISION EUCLIDIENNE ET PGCD3 Soitdun diviseur debet der. Alorsddivise aussibq+r= d souhaite calculer le pgcd dea,b N . On peut supposera>b. On calcule des divisions euclidiennes pgcd sera le dernier reste non nul. division deaparb,a=bq1+r1. Par le lemme 1, pgcd (a,b)= pgcd (b,r1)et sir1=0 alorspgcd(a,b)=bsinonon continue : b=r1q2+r2, pgcd (a,b)= pgcd (b,r1)= pgcd (r1,r 2), r1=r2q3+r3, pgcd (a,b)= pgcd (r2,r3), .. rk 2=rk 1qk+rk, pgcd (a,b)= pgcd (rk 1,rk), rk 1=rkqk+0. pgcd (a,b)= pgcd (rk, 0)= chaque tape le reste est plus petit que le quotient on sait que06ri+1<ri.

5 Ainsi l algorithme se terminecar nous sommes s rs d obtenir un reste nul, les restes formant une suite d croissante d entiers positifs ou nuls :b>r1>r2> > le pgcd dea=600 etb= 4+104124=104 1+20104=20 5+420=4 5+0 Ainsi pgcd (600, 124)= un exemple plus compliqu :Exemple pgcd (9945, 3003).9945=3003 3+9363003=936 3+195936=195 4+156195=156 1+39156=39 4+0 Ainsi pgcd (9945, 3003)= Nombres premiers entre euxD finition entiersa,bsontpremiers entre euxsi pgcd (a,b)= touta Z,aeta+1 sont premiers entre eux. En effet soitdun diviseur commun aet a+1. Alorsddiviseaussia+1 a. Doncddivise1 mais alorsd= 1 oud=+1. Le plus grand diviseur deaeta+1 est donc1. Et doncpgcd(a,a+1)= deux entiers ne sont pas premiers entre eux, on peut s y ramener en divisant par leur pgcd :Exemple deux entiers quelconquesa,b Z, notonsd= pgcd (a,b). La d composition suivante est souvent utile : a=a db=b daveca ,b Zet pgcd (a ,b )= crire la division euclidienne de 111 111 par 20x x, o 20x xest l ann e en Montrer qu un diviseur positif de 10 008 et de 10 014 appartient n cessairement {1, 2, 3, 6}.

6 ARITHM TIQUE2. TH OR ME DEB ZOUT43. Calculer pgcd (560, 133), pgcd (12 121, 789), pgcd (99 999, 1110).4. Trouver tous les entiers 16a650 tels queaet 50 soient premiers entre eux. M me question avec Th or me de B Th or me de B zoutTh or me 2(Th or me de B zout).Soient a,b des entiers. Il existe des entiers u,v Ztels queau+bv= pgcd (a,b)La preuve d coule de l algorithme d Euclide. Les entiersu,vne sont pas uniques. Les entiersu,vsont descoefficientsde B zout. Ils s obtiennent en remontant l algorithme d les coefficients de B zout poura=600etb=124. Nous reprenons les calculs effectu s pour trouverpgcd(600,124)=4. La partie gauche est l algorithme d Euclide. La partie droite s obtient debas en haut. On exprimelepgcd l aide de la derni re ligne o le reste est non nul. Puis on remplace le reste de la ligne pr c dente, et ainside suite jusqu arriver la premi re 4+1044= 600 6+124 ( 29)124 ( 5)+(600 124 4) 6124=104 1+204= 124 ( 5)+104 6104 (124 104 1) 5104=20 5+44= 104 20 520=4 5+0 Ainsi pouru=6 etv= 29 alors 600 6+124 ( 29)= Soignez vos calculs et leur pr sentation.

7 C est un algorithme : vous devez aboutir au bon r sultat ! Dans la partiedroite, il faut chaque ligne bien la reformater. Par exemple104 (124 104 1) 5 se r crit en124 ( 5)+104 6afin de pouvoir remplacer ensuite 104. N oubliez pas de v rifier vos calculs ! C est rapide et vous serez certains que vos calculs sont exacts. Ici on v rifie la fin que 600 6+124 ( 29)= les coefficients de B zout correspondant pgcd (9945, 3003)= 3+93639=9945 ( 16)+3003 533003=936 3+19539= 936=195 4+15639= 195=156 1+3939=195 156 1156=39 4+0 vous de finir les calculs. On obtient 9945 ( 16)+3003 53= Corollaires du th or me de B zoutCorollaire d|a et d|b alors d| pgcd (a,b).Exemple : 4|16 et 4|24 donc 4 doit diviser pgcd (16, 24)qui effectivement vaut TIQUE2. TH OR ME DEB ZOUT5D |auetd|bvdoncd|au+bv. Par le th or me de B zoutd| pgcd (a,b).Corollaire a,b deux entiers.

8 A et b sont premiers entre euxsi et seulement siil existe u,v Ztels queau+bv=1D sens est une cons quence du th or me de B le sens on suppose qu il existeu,vtels queau+bv=1. Commepgcd(a,b)|aalorspgcd(a,b)|au. De m mepgcd(a,b)|bv. Donc pgcd (a,b)|au+bv=1. Donc pgcd (a,b)= on trouve deux entiersu ,v tels queau +bv =d, cela n impliquepasqued= pgcd (a,b). On sait seulement alorsque pgcd (a,b)|d. Par exemplea=12,b=8 ; 12 1+8 3=36 et pgcd (a,b)= 3(Lemme de Gauss).Soient a,b,c a|bc etpgcd(a,b)=1alors a|cExemple : si 4|7 c, et comme 4 et 7 sont premiers entre eux, alors 4| (a,b)=1 alors il existeu,v Ztels queau+bv=1. On multiplie cette galit parcpour obteniracu+bc v=c. Maisa|acuet par hypoth sea|bc vdoncadiviseacu+bc v= quationsa x+b y=cProposition rons l quationa x+b y=c(E)o a,b,c L quation (E) poss de des solutions(x,y) Z2si et seulement sipgcd(a,b)| (a,b)|calors il existe m me une infinit de solutions enti res et elles sont exactement les(x,y)=(x0+ k,y0+ k)avec x0,y0, , Zfix s et k premier point est une cons quence du th or me de B zout.

9 Nous allons voir sur un exemple comment prouverle second point et calculer explicitement les solutions. Il est bon de refaire toutes les tapes de la d monstration chaque les solutions enti res de161x+368y=115(E) Premi re tape. Y a-t-il des solutions ? L algorithme d effectue l algorithme d Euclide pour calculerle pgcd dea=161 etb= 2+46161=46 3+2346=23 2+0 Doncpgcd(368,161)=23. Comme115=5 23alorspgcd(368,161)|115. Par le th or me de B zout, l quation(E) admet des solutions enti res. Deuxi me tape. Trouver une solution particuli re : la remont e de l algorithme d effectue laremont e de l algorithme d Euclide pour calculer les coefficients de B 2+46161=46 3+2346=23 2+023= 161 7+368 ( 3)161+(368 2 161) ( 3)23=161 3 46 ARITHM TIQUE2. TH OR ME DEB ZOUT6On trouve donc 161 7+368 ( 3)=23. Comme 115=5 23 en multipliant par 5 on obtient :161 35+368 ( 15)=115 Ainsi(x0,y0)=(35, 15)est unesolution particuli rede (E).

10 Troisi me tape. Recherche de toutes les (x,y) Z2une solution de (E). Nous savons que(x0,y0)est aussi solution. Ainsi :161x+368y=115et161x0+368y0=115(on n a aucun int r t remplacerx0ety0par leurs valeurs). La diff rence de ces deux galit s conduit 161 (x x0)+368 (y y0)=0= 23 7 (x x0)+23 16 (y y0)=0= 7(x x0)= 16(y y0)( )Nous avons simplifi par23qui est le pgcd de161et 368. (Attention, n oubliez surtout pas cette simplification,sinon la suite du raisonnement serait fausse.)Ainsi7|16(y y0), orpgcd(7,16)=1 donc par le lemme de Gauss7|y y0. Il existe donck Ztel quey y0=7 de l quation( ): 7(x x0)= 16(y y0). On obtient maintenant7(x x0)= 16 7 k. D o x x0= 16k. (C est le m mekpourxet poury.) Nous avons donc(x,y)=(x0 16k,y0+7k). Il n est pas durde voir que tout couple de cette forme est solution de l quation (E). Il reste donc juste substituer(x0,y0)par savaleur et nous obtenons :Les solutions enti res de 161x+368y=115 sont les(x,y)=(35 16k, 15+7k), se rassurer, prenez une valeur dekau hasard et v rifiez que vous obtenez bien une solution de l ppcmD finition ppcm(a,b)(plus petit multiple commun) est le plus petit entier>0 divisible paraet exemple ppcm(12, 9)= pgcd et le ppcm sont li s par la formule suivante :Proposition a,b sont des entiers (non tous les deux nuls) alorspgcd(a,b) ppcm(a,b)=|a b|D (a,b)etm=|a b| pgcd (a,b).