[PDF] Algorithme dEuclide. Calcul de PGCD et de coefficient de Bézout

View - Download Algorithme dEuclide. Calcul de PGCD et de coefficient de Bézout

Previous PDF

Next PDF

Algorithme d'Euclide. Calcul de PGCD et de coecient de Bezout.

Applications

1 PGCD

Denition 1.1Soientn2N,(x1;:::;xn)2Zn. On appelle pgcd dex1;:::;xn, notex1^ ^xnoupgcd(x1;::: ;xn) le nombre deni de la maniere suivante : six1=x2==xn= 0,x1^ ^xn= 0; si lesxine sont pas tous nuls,x1^ ^xnest le plus grand diviseur commun ax1;:::;xn.

Remarque 1.2Si lesxine sont pas tous nuls,x1^ ^xnest bien deni car l'ensemble des diviseurs communs a

x

1:::;xnest une partie non vide deZ(car elle contient 1) et nie (car elle est incluse dans l'ensemble

fk2Z;jkj6max(jx1j;:::;jxnj)g), donc l'ensemble des diviseurs communs ax1;:::;xnadmet un plus grand element. Proposition 1.3Soientn2N,(x1;:::;xn)2Zn,d=x1^ ^xn. AlorsnX k=1x kZ=dZ. Preuve. Soientn2N, (x1;:::;xn)2Zn,d=x1^ ^xn. Si tous lesxisont nuls, alors n X k=1x kZ=nX k=10Z=f0g etd= 0 doncdZ=f0g. On a alors l'egalite de maniere evidente. On suppose maintenant que lesxine sont pas tous nuls. Soitx2nX k=1x kZ. Il existe (a1;:::;an)2Zntel que x=nX k=1x kak. Pour toutk2J1;nK,djxkdonc il existedk2Ztel quexk=ddk. On a alors x=nX k=1dd kak=dnX k=1d kak: n X k=1d kak2Zdoncx2dZ. On a donc l'inclusionnX k=1x kZdZ.

Montrons maintenant l'inclusion inverse.

nX k=1x kZ! \Nest une partie non vide deN(car elle contient jx1j) donc elle admet un plus petit element, note.2nX k=1x kZdoncZnX k=1x kZ. Algorithme d'Euclide. Calcul de PGCD et de coecient de Bezout. Applications

Soitx2nX

k=1x kZ. Eectuons la division euclidienne dexpar: il existe un unique couple (q;r)2Z2tel que x=q+r, avec 06r < . On a alorsr=xq.x2nX k=1x kZet2ZnX k=1x kZ.On a doncr2nX k=1x kZ.

Sir6= 0, on ar2

nX k=1x kZ! \N, avecr < , ce qui contredit la denition de. On a doncr= 0 et donc x=q2Z. On en deduitnX k=1x kZZ. Par suite,Z=nX k=1x kZdZ.

2ZdZdonc il existea2Ztel que=da.2Netd2Ndonca2N. On a vu que tout element denX

k=1x kZadmetcomme diviseur. En particulier,est un diviseur commun dex1;:::;xn. Par denition de d, on a6d, c'est-a-direda6d.d6= 0 donca61.6= 0 donca6= 0. On en deduita= 1 et donc=d.

Par consequent,dZ=nX

k=1x kZ.

Proposition 1.4Soientn2N,2N,x1;:::;xn2Z,a2Z.

(i)pgcd(x1;:::;xn) =jjpgcd(x1;:::;xn); (ii)(8k2J1;nK; ajxk)()ajpgcd(x1;:::;xn).

Preuve. Soientn2N,2N,x1;:::;xn2Z,a2Z.

(i) Soientd= pgcd(x1;:::;xn) etd0= pgcd(x1;:::;xn).nX k=1x kZ=nX k=1x kZ. Or,nX k=1x kZ=d0Zet nX k=1x kZ=dZdoncd0Z=dZ.d02d0Z=dZdonc il existek2Ztel qued0=dk.d2dZ=d0Zdonc il existek02Ztel qued=d0k0. On a alorsd0=d0kk0.d6= 0 donckk0= 1 donc (k;k0)2 f(1;1);(1;1)g et doncd0=d.d;d02Ndonc2Net donc=jj, d'oud0=jjd. (ii) On note toujoursd= pgcd(x1;:::;xn). On suppose que pour toutk2J1;nK,adivisexk. On a alors, pour toutk2J1;nK,xkZaZ. On en deduitnX k=1x kZaZ, c'est-a-diredZaZ.d2dZaZdonca divised. Supposons maintenant queadivised. AlorsdZaZ, c'est-a-direnX k=1x kZaZ. Soitk2J1;nK. x k2xkZPn i=1xiZaZdoncadivisexk.

Remarque 1.5pgcd(x1;:::;xn)est aussi le plus grand diviseur commun dex1;:::;xnau sens de la relation d'ordre de

divisibilite.

2 L'algorithme d'Euclide

Remarque 2.1Sia;b2Z,a^b=jaj ^ jbjcar l'ensemble des diviseurs dansZdeaest egal a l'ensemble des diviseurs

dansZdejaj. On peut donc se limiter aux entiers naturels.

Proposition 2.2Soient(a;b)2(N)2,qetrle quotient et le reste de la division euclidienne deaparb. Alorsa^b=b^r.S. Duchet-http://epsilon.2000.free.fr2/8

Algorithme d'Euclide. Calcul de PGCD et de coecient de Bezout. Applications Preuve. Soienta;b2N. On noteqle quotient etrle reste de la division euclidienne deaparb. On a a=bq+r. Soitdun diviseur commun aaetb.djaetdjbdoncdjabq=r.dest donc un diviseur commun abetr. Soitdun diviseur commun abetr. Alorsdjbetdjrdoncdjbq+r=a.dest donc un diviseur commun aa etb. L'ensemble des diviseurs communs aaetbest donc egal a l'ensemble des diviseurs communs abetr, d'ou le resultat.

aetbdesignent toujours des entiers naturels non nuls. On eectue la suite de divisions euclidiennes suivantes

jusqu'a obtenir un reste egal a 0 (on noter0=aetr1=b) : r

0=r1q1+r2

r

1=r2q2+r3

r n2=rn1qn1+rn r n1=rnqn

Par construction,r2< r1,r3< r2,:::

On est s^ur qu'il existe un entierN2N,N>2 tel querN= 0, sinon (rn)n2Nserait une suite d'entiers

naturels strictement decroissante a partir du rang 2, ce qui n'a pas de sens. En notantn=N1, on a bien

les egalites ci-dessus. Cette suite d'egalites constitue l'algorithme d'Euclide.

D'apres la proposition precedente, on a :

r

0^r1=r1^r2==rn1^rn:

Orrnjrn1doncrn1^rn=rnet donca^b=rn(a^best donc le dernier reste non nul dans la suite des divisions euclidiennes). Proposition 2.3Pour toutk2J2;n1K, il existe(uk;vk)2Z2tel queauk+bvk=rk. Preuve. Eectuons la preuve par recurrence surk. NotonsH(k) la proposition. Pourk= 2 :r2=abq1=au1+bv1avec (u1;v1) = (1;q1)2Z2doncH(2) est vraie.

Pourk= 3 :

r

3=br2q2=b(abq1)q2=aq2+ (1 +q1q2)b=au2+bv2

avec (u2;v2) = (q2;1 +q1q2)2Z2doncH(3) est vraie. Soitk2Ntel quek>3 etk6n2. SupposonsH(p) vraie pour 36p6k. r k+1=rk1rkqk = (auk1+bvk1)qk(auk+bvk) =a(uk1qkuk) +b(vk1qkvk) =auk+1+bvk+1 avec (uk+1;vk+1) = (uk1qkuk;vk1qkvk)2Z2.H(k+1) est donc vraie. D'apres le principe de recurrence, H(k) est vraie pourk2J2;n1K.S. Duchet-http://epsilon.2000.free.fr3/8 Algorithme d'Euclide. Calcul de PGCD et de coecient de Bezout. Applications

Corollaire 2.4

Sia;b2Zetd=a^b, alors il existe(u;v)2Z2tel queau+bv=d.

Preuve. Soit (a;b)2Z2.

Si (a;b) = (0;0), alorsd= 0 donc tout couple d'entiers relatifs (u;v) convient. Sia= 0 etb6= 0, alorsd=jbjdonc sib >0, tout couple de la forme (u;1) avecu2Zconvient et sib <0 tout couple de la forme (u;1) avecu2Zconvient. M^eme raisonnement sib= 0 eta6= 0. On suppose maintenanta6= 0 etb6= 0. Sia;b2N, en reprenant les notations precedentes aveck=n, on a au n+bvn=rn, avecun2Z,vn2Zetrn=a^b. Sia <0, alorsa >0 donc il existe (u0;v0)2Z2tels que (a)u0+bv0= (a)^b. Or, (a)^b=a^b. En posant (u;v) = (u0;v0), on obtient le resultat cherche. On fait le m^eme raisonnement sib <0 ou siaetbsont tous les deux strictement negatifs. Remarque 2.5Les coecientsuetvpeuvent ^etre calcules a l'aide de l'algorithme d'Euclideetendu :

Entree :a;b2N.

Sortie :r2N,u;v2Ztels quer=a^betau+bv=r.

r a,u 1,v 0,r0 b,u0 0,v0 1 tant quer06= 0faire q quotient de la division euclidienne derparr0 r aux r,uaux u,vaux v r r0,u u0,v v0 r

0 rauxqr0,u0 uauxqu0,v0 vauxqv0

n tant que retournerr,u,v.

Theoreme 2.6 (de Lame)Soienta;b2N, tels que16b6a. Le nombre de divisions necessaires pour calculera^ba l'aide de

l'algorithme d'Euclideest inferieur ou egal alnbln+1, ouest le nombre d'or, c'est-a-dire=1 +p5 2 Preuve. Soienta;b2N, tels que 16b6a. On note (Fn)n2Nla suite deFibonacci, c'est-a-dire la suite recurrente lineaire denie par : F

0= 0; F1= 1;8n2N;Fn+2=Fn+1+Fn:

Montrons par reccurrence que pour toutn2N,Fn>n2. Pourn2N, on noteH(n) l'inegaliteFn>n2.

Pourn= 1 :F1= 1 et1=21 +

p5 donc16F1et doncH(1) est vraie.

Soitk2N,k>3. SupposonsH(p) vraie pour 16p6k.

F k+1=Fk+Fk1>k2+k3=k3(+ 1): Or,est une racine de l'equationx2=x+ 1 donc+ 1 =2. Par suite,k3(+ 1) =k1et donc F

k+1>k1doncH(k+ 1) est vraie. D'apres le principe de recurrence,H(k) est vraie pour toutk2N.S. Duchet-http://epsilon.2000.free.fr4/8

Algorithme d'Euclide. Calcul de PGCD et de coecient de Bezout. Applications On considere l'algorithme d'Euclidedecrit au debut du paragraphe : r

0=r1q1+r2

r

1=r2q2+r3

r n2=rn1qn1+rn r n1=rnqn Montrons par recurrence que pour toutk2J1;nK,rnk>Fk+2. Pourk2J1;nK, notonsH(k) l'inegalite r nk>Fk+2. Pourk= 1 :rn1=rnqn.rn< rn1doncqn>1.qn6= 1 sinonrn1=rndoncqn>2. On a donc r n1=rnqn>qn>2 =F3doncH(1) est vraie. Soitk2J1;n1K. SupposonsH(p) vraie pour toutp2J1;kK. r n(k+1)=rnk1=rnkqnk+rnk+1 q nk6= 0 sinonrnk1=rnk+1ce qui est impossible doncqnk>1. On en deduitrn(k+1)>rnk+rnk+1. Orrnk>Fk+2etrnk+1>Fk+1d'apres l'hypothese de recurrence donc r nk+rnk+1>Fk+2+Fk+1=Fk+3: Par suite,rn(k+1)>Fk+3doncH(k+ 1) est vraie. D'apres le principe de recurrence,H(k) est vraie pour toutk2J1;nK. En particulier,r1>Fn+1. CommeFn+1>n1etr1=b, on en deduitb>n1, puis lnb>(n1)ln. >1 donc ln >0, d'ou : n6lnbln+ 1: Theoreme 2.7 (de Bezout)Soienta;b2Z. Alorsa^b= 1si et seulement si il existe(u;v)2Z2tel queau+bv= 1. Preuve. Soienta;b2Z. Supposonsa^b= 1. AlorsaZ+bZ=Z. 12Zdonc 12aZ+bZdonc il existe (u;v)2Z2tel queau+bv= 1. Suppons maintenant qu'il existe (u;v)2Z2tel queau+bv= 1. Soitdun diviseur commun aaetb.dja doncdjau.djbdoncdjbv. On en deduitdjau+bv= 1 doncd2 f1;1get donca^b= 1.

3 Applications

3.1 Les inversibles de Z/nZ

Proposition 3.1Soitk2Z.kest inversible dansZ=nZsi et seulement sik^n= 1. Preuve. Soitk2Z. Supposonskinversible dansZ=nZ. Il existea2Ztel queka=1 doncndiviseka1. Il existeb2Ztel queka1 =nb. Alorska+(b)n= 1, avec (a;b)2Z2. D'apres le theoreme deBezout, k^n= 1.S. Duchet-http://epsilon.2000.free.fr5/8 Algorithme d'Euclide. Calcul de PGCD et de coecient de Bezout. Applications Supposons maintenantk^n= 1. Il existe (u;v)2Z2tel queku+nv= 1. Alorsku+nv=1. Or, ku+nv=ku+nvetn=0 doncku=1 et donckest inversible dansZ=nZ. Corollaire 3.2Z=nZest un corps si et seulement sinest premier. Preuve. Supposons queZ=nZest un corps. AlorsZ=nZest integre. Supposonsnnon premier. Il existe p;q2N f0;1gtel quen=pq.n=0 doncpq=0, avecp;q2J2;n1K(et doncp6=0 etq6=0), ce qui contredit le fait queZ=nZest integre.nest donc un nombre premier. Supposons maintenantnpremier. Soita2J1;n1K. Alorsa^n= 1 et doncaest inversible dansZ=nZ. Tout element non nul deZ=nZest donc inversible doncZ=nZest un corps. Exemple 3.3(Z=nZ)=f1;3;7;9;11;13;17;19g. Calculons17

1. Pour cela, on applique l'algorithme d'euclideetendu

20 = 171 + 3

17 = 35 + 2

3 = 21 + 1

2 = 12 + 0

De ces egalites, on deduit successivement :

3 = 20171

2 = 1735 = 175(20171) = 176 + 20(5)

1 = 321 = 20171176 + 205 = 206 + 17(7)

On en deduit206 +177 =1. Or20 =0 donc17

1=7 =13.

3.2 Theoreme des restes chinois et systemes de congruences

Theoreme 3.4Soientp2N,n1;:::;npdes entiers naturels deux a deux premiers entre eux et(a1;:::;ap)2Zp. Alors

le systeme de congruences deni par :8k2J1;pK;xak(modnk)admet une unique solution modulo

N=n1:::np, donnee parxpP

k=1u kNkak, ou pour toutk2J1;pK,Nk=Nn ketukN1 k(modnk). Preuve. Soientp2N,n1;:::;npdes entiers deux a deux premiers entre eux et (a1;:::;ap)2Zp. Notons (S) le systeme de congruences deni par :

8k2J1;pK;xak(modnk):

Pour toutk2J1;pK, on noteNkl'entierNN

k. Les entiersnketant deux a deux premiers entre eux, il en resulte que pour tout entierk2J1;pK,Nketnksont premiers entre eux et doncNkest inversible modulonk. Pour toutk2J1;pK, notonsukN1 k(modnk). Soitx=pP k=1u kNkak. Soiti2J1;pK. Sik2J1;pKetk6=i, alors N i0 (modnk). On a alorsxuiNiai(modni). OruiNi1 (modni) par denition deuidoncxai

(modni). Ceci etant vrai pour tout entieri2J1;pK,xest une solution du systeme (S). D'ou l'existence.S. Duchet-http://epsilon.2000.free.fr6/8

Algorithme d'Euclide. Calcul de PGCD et de coecient de Bezout. Applicationsquotesdbs_dbs17.pdfusesText_23

[PDF] algorithme d'euclide casio

[PDF] algorithme d'euclide étendu python

[PDF] algorithme d'euclide pgcd

[PDF] algorithme deuclide pgcd python

[PDF] algorithme d'euclide polynome

[PDF] algorithme de dijkstra arduino

[PDF] algorithme de dijkstra c++

[PDF] algorithme de dijkstra en ligne

[PDF] algorithme de dijkstra java

[PDF] algorithme de dijkstra javascript

[PDF] algorithme dichotomie python

[PDF] algorithme factorielle boucle pour

[PDF] algorithme factorielle en c

[PDF] algorithme factorielle n

[PDF] algorithme factorielle pascal