[PDF] Algorithme dEuclide Tout anneau euclidien est principal

View - Download Algorithme dEuclide

Previous PDF

Next PDF

Université de BordeauxPréparation à l"agrégation

Mathématiques2021-2022

Algorithme d"Euclide

1.Rappels

SoitAun anneau euclidien. C"est donc queAest commutatif unitaire, intègre, et qu"il existe une application?:A→Nappelée stathme euclidien, telle que (1)?(a) = 0 si et seulement sia= 0 (2) Siaetbsont des éléments deA, avecb?= 0, il existe des éléments retqdeAtels quea=bq+ret?(r)< ?(b). Les élémentsret qsont respectivement appelés reste et quotient de la division dea parb; on n"impose pas qu"ils soient uniques. Par exemple, siA=Z, on peut prendre?(n) =|n|. Ici, il n"y a pas unicité de l"écriturea=bq+r, où?(r)< ?(b); on impose traditionnellement

0?r < bce qui garantit l"unicité, mais c"est un choix arbitraire : on pourait

tout aussi bien imposer-b/2< r?b/2 par exemple. SiA=K[X], oùK est un corps, on peut choisir?(P) = degP+ 1 siP?= 0 et?(0) = 0. Enfin, pourA=Z[i], on peut prendre comme stathme?(a+ib) =a2+b2. Tout anneau euclidien est principal, et tout anneau principal est factoriel (tout élément non nul se décompose en produit fini d"irréductibles et cette décomposition est unique, à multiplication des facteurs par des inversibles près). SiAest un anneau principal, soientaetbdeux éléments deAtels que (a,b)?= (0,0), il existeddansAtel que (1)d|aetd|b (2) Sie|aete|b, alorse|d. Cet élémentd, unique à multiplication près par un élément inversible de A, est appelé le pgcd deaetb, et noté pgcd(a,b), ou parfois (a,b) si le contexte ne permet pas d"ambiguïté avec l"élément (a,b) deA2. On a alors aA+bA=dA. En particulier, il existeuetvdansAtels queau+bv=d (identité de Bézout). Ceci donne une définition légèrement plus générale : on appelle pgcd de (a,b) tout générateur de l"idéalaA+bAdeAengendré paraetb; cette définition est équivalente à la précédente quand (a,b)?= 0 et définit pgcd(0,0) = 0. Une dernière définition, encore plus générale puisqu"elle est valable si l"anneauAest factoriel. SiAest factoriel,a?A\{0}, etpirréductible dans A, on définitvp(a) la plus grande puissance depqui divisea: siv=vp(a), on apv|amaispv+1?a. On définit pgcd(0,b) =bpuis, pour toutb?Aet poura,btous deux non nuls, on pose pgcd(a,b) =? ppmin(vp(a),vp(b)) 1

2oùpparcourt un système de représentants des éléments irréductibles deA

modulo les unités. Cette définition généralise les deux précédentes et permet de calculer le pgcddquand la factorisation dansAest effective. SiAest de plus euclidien, l"algorithme d"Euclide permet aussice calcul, en général à bien moindre coût que celui d"une factorisation. L"algorithme d"Euclide étendu calcule, en même temps qued, des élémentsuetvsatis- faisant l"identité de Bézout. Rappelons finalement que dans un anneau principalA, siaetbsont deux éléments deA, il existe un élémentcdansA, unique à multiplication près par un inversible deA, tel que (1)a|cetb|c (2) Sia|eetb|e, alorsc|e. C"est le ppcm deaetb, noté ppcm(a,b), ou encore [a,b]. On a aA+bA= (a,b)A, aA∩bA= [a,b]AetabA= (a,b)[a,b]A.

2.Algorithme d"Euclide

Algorithme 2.1(Algorithme d"Euclide)

Entrée:a,bdansA

Sortie:pgcd(a,b)

(1) Sib= 0, retournera. (2) Soitrle reste de de la division euclidienne deaparb. Posera←b, b←ret revenir à l"étape(1). Preuve.Le cas (a,b) = (0,0) est clair puisque l"algorithme retourne direc- tement 0 à l"étape (1). Le cas général vient du fait que (a,b) = (a+bk,b) pour toutk?A(exercice). L"algorithme se termine car la valeur de?(b) décroit strictement tant queb?= 0. Comme?prend ses valeur dansN, on finit par arriver à?(b) = 0, doncb= 0.?

3.Algorithme d"Euclide étendu

Algorithme 3.1(Algorithme d"Euclide étendu)

Entrée:aetbdansA,(a,b)?= (0,0).

Sortie: Le pgcdddeaetb, et un couple(u,v)deA2tel queau+bv=d. (1) Sia= 0, sortird=b,u= 0,v= 1. (3) Tant quey?= 0 (4) Calculer le quotientqet le resterde la division euclidienne de xpary. (5)(ux,uy)←(uy,ux-quy). (6)(vx,vy)←(vy,vx-qvy). (7)(x,y)←(y,r). (8) Sortird=x,u=ux,v=vx. 3 Preuve.Comme dans l"algorithme précédent, l"algorithme se termine, et l"on calcule biendun pgcd deaetb. On posex0=a,v0= 0,u0= 1,x1=b,v1= 1 etu1= 0. Pouri?1, on écrit la division euclidiennexi-1=qixi+xi+1, où?(xi+1)< ?(xi), et on posevi+1=vi-1-qivietui+1=ui-1-qiui. C"est donc que ?uivi u i+1vi+1? =?0 11-qi?? ui-1vi-1 u ivi?

Donc si

?uivi u i+1vi+1?? a b? =?xi-1 x i? ce qui est vrai pouri= 1, alors ?uivi u i+1vi+1?? a b? =?0 11-qi?? xi-1 x i? =?xi x i+1? Soitll"entier tel quexl+1= 0. On a bien alorsula+vlb=xl=d.?

4.Complexité dansK[X]

SoitKun corps. AlorsK[X] est un anneau euclidien. On veut majorer le nombre d"opérations dansKnécessaire à l"exécution des algorithmes d"Eu- clide en fonction du degré des polynômes concernés. On gardeles notations du paragraphe précédent.

4.1.Algorithme d"Euclide.Soientaetbdeux polynômes deK[x], de

degrés respectifsnetm. On suppose quem?n. Le nombre d"itérationsl est borné par?(b), donc icim+ 1. Pour touti, on noteni= degxi. On peut diviser le polynômexi-1parxi en utilisant au plus (2ni+ 1)(ni-1-ni+ 1) additions et multiplications, et une inversion dansK. Donc le coût total est inférieur à C=l? i=1(2ni+ 1)(ni-1-ni+ 1) additions et multiplications, pluslinversions dansK. On voit alors que

C?(2m+1)l?

On a donc prouvé le résultat suivant.

Théorème 4.1.SoitN?1. On peut exécuter l"algorithme d"Euclide pour deux polynômes de degré inférieur ou égal àNenO(N2)opérations sur le corps de base. On peut donner une majoration plus précise deC. Pour cela, on évalueC dans le cas où le degré décroît exactement de 1 à chaque pas, eton montre ensuite que c"est le cas le pire. 4 Dans ce cas,l=m+ 1,n0=n,n1=met pouridans{2...,m+ 1}, n i=m-i+ 1. On trouve alors que

C= (2m+ 1)(n-m+ 1) + 2m+1?

i=2?

2(m-i+ 1) + 1?

= 2mn+n+m+ 1. Pour montrer que c"est le cas le pire, on pose, pourn0?n1> n2>···> n l?0,

σ(n0,...,nl) =l?

i=1(2ni+ 1)(ni-1-ni+ 1). Montrons queσcroît, si l"on insère un entierkentrenj-1et unnj, ou bien si l"on ajoutekaprèsnl. Soit donckun entier tel quenj-1> k > nj. = (2k+ 1)(nj-1-k+ 1) + (2nj+ 1)(k-nj+ 1)-(2nj+ 1)(nj-1-nj+ 1) = (2k+ 1)(nj-1-k+ 1) + (2nj+ 1)(k-nj-1) = 2(nj-1-k)(k-nj) + 2k+ 1>0 On montrerait le méme résultat, en ajoutant un entierkaprèsnl. On en déduit par récurrence queσ(n0,...,nl)?σ(n0,n1,n1-1,n1-2,...,1), et donc que le cas où le degré baisse de 1 à chaque pas est le cas le pire. Théorème 4.2.L"algorithme d"Euclide, appliqué à des polynômesaetbde degrés respectifsnetm(n?m), utilise au plus2mn+m+n+1additions et multiplications, plusm+ 1inversions dansK.

4.2.Algorithme d"Euclide étendu.Pour évaluer la complexité de l"al-

gorithme d"Euclide étendu, il nous faut majorer le degré despolynômesui etvi.

Proposition 4.3.On a

degvi=?

1?j degui=?

2?j Preuve.Par récurrence. On av0= 0,v1= 1,v2=v0-q1v1=-q1. Ainsi, degv2= degq1=n-m=n0-n1. Soiti?1. On suppose que pour tout j? {1,...,i}, on a degvj=?j-1 k=1degqk. Ainsi, degvj-11?k?idegqi.

L"égalité pour le degré deuise prouve de la même façon.? 5 Le calcul devi+1=vi-1-qividemande au plus 2degqidegvi+ degqi+ degvi+1 opérations dansKpour le produit et au plus degvi+1+1 opérations pour la soustraction, c"est-à-dire en tout 2(ni-1-ni)(n0-ni-1+n0-ni+1), sauf pouri= 1 : le calcul dev2=-q1demanden-m+ 1 changements de signe. On obtient que le nombre d"opérations dansKpour calculer lesvi est majoré par C v=n-m+ 1 + 2l? i=2((ni-1-ni)(n0-ni-1) +n0-ni+ 1) ?n-m+ 1 + 2nl? i=2(ni-1-ni) + 2(l-1)(n+ 1) ?n-m+ 1 + 2n(n1-nl) + 2(l-1)(n+ 1) ?n-m+ 1 + 2mn+ 2m(n+ 1) ?4mn+n+m+ 1. On montrerait de même que le nombre d"opérations dansKnécessaires au calcul desuiest inférieur ou égal à 4m2+m. On peut améliorer ces majorations, en calculant le nombre d"opérations nécessaires au calcul desuiet desvidans le cas où le degré du reste baisse de 1 à chaque étape, puis en montrant que c"est le cas le pire. On obtient alors C v=n-m+ 1 + 2m+1? i=2((n-(m-i+ 2)) +n-(m-i+ 1) + 1)) = 4mn-2m2+n+m+ 1 C u= 2 + 2m+1? i=3((m-(m-i+ 2)) +m-(m-i+ 1) + 1) = 2(m2+m). On peut aussi noter que l"algorithme d"Euclide étendu calcule inutilement la suite desvi: on peut entièrement supprimer ces calculs, sans affecter le calcul deuetd. Sib?= 0, on peut alors poserv= (d-au)/b. Théorème 4.4.L"algorithme d"Euclide étendu, appliqué à des polynômes aetbde degrés respectifsnetm(n?m), utilise6mn+O(n)additions et multiplications, plusm+ 1inversions dansK.

5.Complexité dansZ

5.1.Algorithme d"Euclide.On applique l"algorithme d"Euclide à deux

entiersaetbpositifs. Le nombre d"itérations est inférieur ou égal àb, mais on peut trouver une bien meilleure majoration : Théorème 5.1.Soitnun entier naturel non nul, et soientaetbdeux entiers tels quea > bet tels que l"algorithme d"Euclide appliqué àaet

6bnécessite exactementndivisions, et tels queasoit minimal pour cette

propriété. Alorsa=Fn+1etb=Fn, où(Fn)est la suite de Fibonacci définie parF0= 0,F1= 1,Fi+2=Fi+1+Fipouri?0. Preuve.Si on applique l"algorithme d"Euclide àFn+1etFn, on obtient (Fn+1,Fn) = (Fn,Fn-1) =···= (F1,F0) = 1.

On a donc exactementndivisions.

Réciproquement, on suppose queaetbsatisfont les conditions de l"énoncé. Soientxn+1=a,xn=b, et pouri < n, soitxile reste de la division dexi+2 parxi+1, jusqu"àx0= 0. Alors pour touti,xi+1> xi. On noteqila partie entière dexi+1/xi. Commexi+1=xi-1+qixi?xi-1+xipour toutiet commex0=F0= 0 etx1?F1= 1, on obtient par récurrence quexi?Fi pour touti. Donca?Fn+1. La minimalité deamontre alors quea=Fn+1. De plus,xn-1?Fn-1=Fn+1-Fn?a-b, puisqueFn?b. Comme en outrexn-1?xn+1-xn=a-b, les inégalités ci-dessus sont des égalités et F n=b.? Le cas le pire est donc atteint pour deux éléments consécutifs de la suite de Fibonacci. On peut écrireFnde façon explicite. Soient ?=1 +⎷ 5

2etψ=1-⎷

5 2 les racines dex2-x-1, alorsFn⎷

5 =?n-ψn. Ainsi, si l"algorithme

d"Euclide appliqué àaetbdemanden-1 divisions, alorsa⎷

5??n-ψn.

Donca⎷

5> ?n-1 et

n < log(1 +a⎷ 5) log?. On en déduit que le nombre de divisions est majoré par log ?(1 +a⎷ 5)? -2. Donc, siaetbsont inférieurs àN, alors le nombre d"opérations élémentaires dans l"algorithme d"Euclide est enO((logN)3+1). Mais on peut faire mieux : Théorème 5.2.Siaetbsont inférieurs àN, le coût du calcul de(a,b)par l"algorithme d"Euclide est enO((logN)2+ 1). Preuve.On suppose quea > b >0, et que l"algorithme d"Euclide pouraet bdemande exactementndivisions. On notex0=a,x1=b,x2,...xn+1= 0 la suite des restes successifs, et pouridans{1,...,n}, on noteqile quotient dexi-1parxi. Doncxi-1=qixi+xi+1. Le coût des divisions est inférieur

à une constante multipliée par

n? i=1(logxi+ 1)(logqi+ 1)?(loga+ 1)n? i=1(logqi+ 1) ?(logN+ 1)(n+ logn? i=1q i). 7 Comme n? i=1q i?n? i=1x i-1 xi=a(a,b)?N, le coût est bien enO((logN)2+ 1).?

5.2.Coût de l"algorithme d"Euclide étendu.On reprend les notations

du §3. Doncx0=a,v0= 0,u0= 1,x1=b,v1= 1 etu1= 0. Pouri?1, x i-1=qixi+xi+1, où?(xi+1)< ?(xi), et on pose?uivi u i+1vi+1? =?0 11-qi?? ui-1vi-1 u ivi? Proposition 5.3.Pour touti, on a les inégalités|ui|?b/xi-1et|vi|? a/x i-1.

Preuve.On a?uivi

u i+1vi+1? =?0 11-qi?

···?0 11-q1?

ainsi det?uivi u i+1vi+1? = (-1)i etquotesdbs_dbs13.pdfusesText_19

[PDF] exercice relation métrique

[PDF] structure géométrique des molécules

[PDF] conflits entre parents et adolescent

[PDF] theorie de vsepr pdf

[PDF] géométrie des molécules exercices

[PDF] relation parents adolescent aujourd'hui

[PDF] structure électronique des molécules mpsi

[PDF] communiquer avec un adolescent

[PDF] communication parents adolescent

[PDF] comment structurer un service communication

[PDF] l'importance des parents dans la famille

[PDF] quel est le role des parents dans la famille

[PDF] la parentalité définition

[PDF] qu'est ce que la parentalité aujourd'hui

[PDF] qu'est ce que la parentalité