[PDF] Algorithme dEuclide Algorithme: Division euclidienne étendue avec

View - Download Algorithme dEuclide

Previous PDF

Next PDF

Algorithme d"Euclide

FrançoisDEMARÇAY

Département de Mathématiques d"Orsay

Université Paris-Sud, France

1. Division euclidienne : École élémentaire

SoitZl"anneau des nombres entiers naturels positifs ou négatifs, et soitN=Z+Zle sous-ensemble des entiers qui sont positifs. Définition 1.1.Diviseravec resteun entiera>1par un entier16b6aqui lui est inférieur, cela consiste à trouver unquotiententierq>0et unresteentierr>0tels que : a=q b+r; le quotientqétant maximal possible, de telle sorte que dans le rester, on ne puisse plus extraire "dub» :

06r6b1:

Il est bien connu que diviser avec reste est toujours possible, le couple(q;r)2NN étant alors déterminé de manière unique en partant dea>1et debavec16b6a quelconques. Exemple 1.2.Comme à l"école élémentaire, soit à divisera= 126parb= 35: 12635
1053

21Mentalement, on essaie de multiplier35successivement par1,2,3,4, et on trouve que

335 = 105est le résultat maximum qui demeure inférieur à126. On reporte alors105

à gauche, on soustrait126105= 21 , et on trouve : 126
|{z} a= 3|{z} q35|{z} b+ 21|{z} r: Cet exemple s"inscrit dans un contexte général, connu depuis la Préhistoire sur Terre, sur Mars, sur Jupiter, sur Vénus, et sans doute aussi sur quelques exoplanètes dotées de mathématiques encore embryonnaires. 1

2 FrançoisDEMARÇAY, Département de Mathématiques d"Orsay, Université Paris-Saclay, FranceThéorème 1.3.[Di visioneuclidienne des entiers] Étant donné deux nombres entiers po-

sitifs quelconquesa2Netb2Navec16b6a, il existe toujours un entier positif uniqueq2Net un entier positif uniquer2N- parfois égal à0- tels que : a=q b+ret06r < b

Exercice 1.En s"inspirant de la figure située à droite du portrait d"Euclide, expliquer en quoi la division

possède un sens géométrique.

2. Division euclidienne : polynômes à coefficients entiers

La division euclidienne fonctionne de manière essentiellement analogue dans l"anneau Z[x]des polynômes à une indéterminéexet à coefficients entiers, sachant queplusieurs opérations de soustraction successives s"avèrent nécessaires.

Exemple 2.1.Soit le polynôme quartique :

A(x) :=3x4+ 2x3+x+ 5;

àdiviser avec restepar le polynôme quadratique (donc de degré inférieur) :

B(x) :=x2+ 2x+ 3;

les deuxmonômes de têtedeAet deBétant placés en première position. On se convainc mentalement que c"est la multiplication par le monôme3x2qui permet de faire monter le monôme de tête deB(x)à ce nouveau niveau de celui deA(x): 3x

4=3 x2x2;

et donc, on est conduit à soustraire :

A(x)3x2B(x)|{z}

3x46x39x2;

procédé que l"on peut aussi représenter agréablement sous forme d"un tableau incomplet qui commence à se remplir :

3x4+ 2x3+ 0 +x+ 5x

2+ 2x+ 33x46x39x23x24x39x2+x+ 5

3. Division euclidienne : polynômes à coefficients dans un anneau 3

De cette manière, on fait apparaître le reste intermédiaire :

4x39x2+x+ 5;

qui possède un nouveau monôme de tête4x3, de telle sorte que c"est maintenant le monôme multiplicateur : 4x qui permet de faire remonter le monôme de têtex2deB(x)au niveau4x3. Après itération et épuisement de ces calculs, le tableau final s"écrit :

3x4+ 2x3+ 0 +x+ 5x

2+ 2x+ 33x46x39x23x24x39x2+x+ 54x3+ 8x2+ 12x4xx2+ 13x+ 5x

2+ 2x+ 3115x+83x

24x1Ce tableau synoptique permet alors de lire instantanément le quotient et le reste dans la

division du polynômeA(x)par le polynômeB(x):

A(x) =Q(x)|{z}

quotientB(x) +R(x)|{z} reste;

équation qui s"écrit donc explicitement :

3x4+ 2x3+x+ 5 =3x24x1x2+ 3x+ 3+15x+8:

Bien entendu, ce deuxième exemple simple suggère aussi un procédé général, probable-

ment déjà connu du lecteur-étudiant.

3. Division euclidienne : polynômes à coefficients dans un anneau

rons maintenant avec unanneau commutatif :A;+;; possédant un élément unité12Apour la multiplication :

1r=r1 =r(8r2A);

la multiplication étant souvent notée "» à la place de "», voire même sous-entendue en

omettant tout symbole. Définition 3.1.Un élémentu2Aest appelé uneunités"il existeu02Atel que : uu

0=u0u= 1;

et le groupe (multiplicatif, commutatif) des unités deAest alors notéA.

4 FrançoisDEMARÇAY, Département de Mathématiques d"Orsay, Université Paris-Saclay, FranceSoit maintenantxun symbole qui désigne une indéterminée. L"espace vectoriel des

polynômes à coefficients dansA:

A[x] :=n

a nxn+an1xn1++a1x+a0:n2N; an;an1;:::;a1;a02Ao est à nouveau un anneau commutatif possédant la même unité12A(exercice de révision mentale). Supposons temporairement pour simplifier que les polynômes :

B(x) =bmxm+bm1xm1++b0(m>0);

par lesquels on cherche à diviser d"autres polynômes :

A(x) =anxn+an1xn1++a0(n>0);;

de degré supérieurn>mont toujours un coefficient de têtebm2Aqui est uneunité. Définition 3.2.Étant donné un polynôme de degrék>0:

P(x) =ckxk+ck1xk1++c0(ck6=0);

on appellemonôme de têtedePson terme de plus haut degré et on le note : TeteP(x)=ckxk:Algorithme: Division polynomiale avec reste

Entrées :Deux polynômes

A(x) =X

06i6na

ixietB(x) =X

06j6mb

jxj à coefficientsai2Aetbj2Ade degrés respectifsn>m>1tels que le coefficientbm2Adu monôme de têtebmxmdeB(x)est uneunitéde l"anneau A. Sorties :Un polynôme-quotientQ2A[x]et un polynôme-resteR2A[x]satis- faisant :

A=QB+R;

le degré deRétant strictement inférieur à celui deB:

06degR < m:

Algorithme :

R [A. pouri=nm,nm1, ...,0, faire : sidegR=m+ialorsQi [Tete(R)bm

R [RQiB

sinonQi [0

RetournerQ=P

06i6nmQietR.Ici, le lecteur-étudiant est invité à déchiffrer soigneusement les instructions de cet algo-

rithme, afin premièrement de se convaincre par la réflexion qu"il correspond bien à la si-

tuation générale exemplifiée ci-dessus, et deuxièmement, afin de reconstituer par lui-même

4. Anneaux intègres euclidiens 5

les arguments qui démontrent le caractère bien-fondé des calculs, et notamment, de vérifier

quel"algorithme termine en temps fini. Contentons-nous de détailler la démonstration d"un lemme plus simple.

Lemme 3.3.

[Unicité du quotient et du r este]Lorsque le coefficientbm2 mathcalA du monôme de têtebmxmdeB(x)est une unité, le polynôme-quotientQ(x) et le polynôme-resteR(x)dans la division deA(x)parB(x):

A=QB+R;

sont déterminés de manière unique. Démonstration.En effet, une autre équation :

A=Q0B+R0;

soustraite àA=QB+Rdonne après réorganisation :Q0QB=RR0; et comme le membre de droite est de degré6degB1, le membre de gauche ne peut qu"être identiquement nul, d"oùQ0=QpuisR0=R.

4. Anneaux intègres euclidiens

Pourrait-on, par une conceptualisation adéquate, capturer dans un seul filet les deux situations analogues classiques que sont : la division euclidienne dansNou dansZ; la division euclidienne dansZ[x]ou dansQ[x]? Dans les deux cas, ce qui compte, c"est l"existence d"une fonction naturelle qui mesure

l"abaissement de la complexité ou de la taille des objets après une division élémentaire.

Définition 4.1.

[Anneaux euclidiens] Un anneau commutatif intègreAmuni d"une unité

12Aest appelé unanneau euclidiens"il existe une fonction :

:Anf0g !N; (0) :=1; telle que, pour tousa;b2Aavecb6= 0, il est possible de diviseraparbavec un reste -inférieur au sens précis où : il existeq; r2Aavec(r)< (b)satisfaisanta=q b+r: Bien que l"unicité deqet celle derne soient pas requises dans cette définition, on dit souvent queqest lequotientdans la division deaparb, et queren est lereste. Noter que la fonctionest soumise à la seule condition de diriger les "abaissements de complexité»(r)< (b). Terminologie 4.2.On dira queest lafonction euclidiennede l"anneau euclidien(A;). Avec la fonction valeur absolue(a) :=jaj, il est bien connu que l"anneau des entiers naturelsZest un anneau euclidien, et d"ailleurs, l"unicité du quotientqet du restersont garanties dès lors qu"on demande quer>0, ce qu"il est raisonnable de faire.

6 FrançoisDEMARÇAY, Département de Mathématiques d"Orsay, Université Paris-Saclay, FranceLorsqueA=K[x]est l"anneau des polynômes sur un corps, la fonction degré

d(a) :=dega, avecdeg(0) :=1, est la fonction naturelle qui munitK[x]d"une structure d"anneau euclidien, l"unicité du quotient et du reste étant faciles à vérifier. Rappelons qu"un élémentp2Adiviseun autre élémentq2As"il exister2A satisfaisant : p=rq:

Définition 4.3.

[Plus grand commun di viseur]SoitAun anneau commutatif quelconque et soient deux élémentsa;b2A. On dit qu"un élémentc2Aestunplus grand commun diviseur entreaetb, ce qu"on notec=pgcd(a;b), lorsque : cdiviseaetcdiviseb; si un élémentd2Adivise simultanémentaetb, alors en fait,ddivisec Classiquement, le fait qu"un élémentp2Adivise un autre élémentq2Ase note : pjq:

Définition 4.4.

[Plus petit commun multiple] SoitAun anneau quelconque et soient deux élémentsa;b2A. On dit qu"un élémente2Aestunplus petit commun multiple entreaetb, ce qu"on notee=ppcm(a;b), lorsque : ajeetbje; si un élémentf2Aest divisible simultanément paraet parb, alors en fait,ejf. Certes en général,pgcdetppcmne sont pas, strictement parlant, uniques. Toutefois, il est aisé, surA=Zet surA=Z[x]d"assurer leur unicité (voirinfra). Comme on le sait, entre deux nombres quelconquesa;b2Z, lepgcdestuniquedès lors qu"on demande qu"il appartienne àN. Alors le lecteur-étudiant reconstituera sans difficulté la démonstration des propriétés élémentaires dupgcd. Lemme 4.5.Sur l"anneauZdes entiers naturels, la fonction à deux argumentspgcd(;) possède les cinq propriétés suivantes : (i)pgcd(a;b) =jaj ()ajb; (ii)pgcd(a;b) =pgcd(b;a); (iii)pgcda;pgcd(b;c)=pgcdpgcd(a;b);c. (iv)pgcd(ca; cb) =jcjpgcd(a;b). (v)jaj=jbj=)pgcd(a;c) =pgcd(b;c). Notons "pour le fun» que l"associativité générale s"écrit : pgcd(a1;:::;an) =pgcda1;pgcd(a2; :::;pgcd(an1;an):::): Les anneaux euclidiens sont exactement ceux dans lesquels des divisions euclidiennes successives sont possibles, notamment pour trouver unpgcdentre deux éléments quel- conques donnés.

4. Anneaux intègres euclidiens 7

En partant de deux élémentsa;b2Aque l"on renommer0;r12Aavec(r0)>(r1), une première division euclidienne : r

0=q1r1+r2;

suivie de divisions successives entre les restes nouveauxr2;r3;r4;:::qui appaissent, peut être représentée synoptiquement comme suit : (r0)>(r1)r

0=q1r1+r2

(r1)>(r2)r

1=q2r2+r3

(r2)>(r3)r

2=q3r3+r4

(r3)>(r4)r

3=q4r4+0

où l"on suppose ici que le procédé termine à la quatrième division, à savoir quer5= 0.

LorsqueA=Z, il est bien connu alors que lepgcdest le dernier reste non nul, icir4, et on

démontre en cours d"Algèbre que cela est encore vrai dans tout anneau euclidien(A;).Algorithme: Division euclidienne classique

Entrées :Deux élémentsa;b2(A;)d"un anneau commutatif intègre euclidien

Amuni d"une fonction euclidienne.

Sortie :Un plus grand commun diviseurh2Aentreaetb. r0 [a,r1 [b. i [1 tant queri6= 0faireri+1 [Resteri1divisé parri i [i+ 1

Retournerri1.Comme cela a déjà été illustré sur l"exemple qui le précède, cet algorithme (antique)

divise les restes successifs : (ri1)>(ri)r i1=qiri+ri+1; remplace à chaque étape les couples : [ri; ri+1] [[ri1; ri]; puis recommence à diviser : (ri)>(ri+1)r i=qi+1ri+1+ri+2;

8 FrançoisDEMARÇAY, Département de Mathématiques d"Orsay, Université Paris-Saclay, Franceet ainsi de suite.

Sans utiliser d"indices, l"algorithme de division euclidienne classique peut aussi être

représenté sous la forme d"une carte d"instructions en boucle :Exemple 4.6.Il est avisé de représenter synoptiquement la recherche, déjà entaméesupra,

dupgcdentre126et35:

126>35126 = 335 + 21

35>2135 = 121 + 14

21>1421 = 114 + 7

14>7

14 = 27+0;

et ici, puisque le cinquième rester5= 0est nul, l"avant-dernier rester4= 7est un (le) pgcdrecherché. Exemple 4.7.De manière alternative, on peut représenter sous forme d"un tableau le calcul

qui montre que315et307sont premiers entre eux.5. Croissance des expressions intermédiaires et normalisations

Les calculs avec des polynômes, des fractions rationnelles, ou des matrices à coefficients entiers souffrent souvent d"une "maladie» propre au calcul numérique ou symbolique :la croissance parfois débridée des expressions.

5. Croissance des expressions intermédiaires et normalisations 9

Exemple 5.1.Voici le déroulement du calcul du plus grand commun diviseur entre les deux polynômes à coefficients entiers :

A=7x522x4+ 55x3+ 94x287x+ 56

=:R0;

B=62x497x3+ 73x2+ 4x+ 83

=:R1; au moyen de l"algorithme d"Euclide; à cause notamment du fait que les deux coefficients de tête7et62deAet deBne sont pas des unités, les polynômes-restes dans les divisions successives :R2:=reste dans la division deR0parR1; R

3:=reste dans la division deR1parR2;

R

4:=reste dans la division deR2parR3;

R

5:=reste dans la division deR3parR4;

possèdent des coefficients rationnels qui "explosent» de manière assez surprenante : R

2=1132933844

x3+4096053844 x21838551922 x+2721193844 R

3=1842328292309212835303849

x21523917079036812835303849 x+1096636125825612835303849 R R Afin de remédier - au moins en partie - à ce phénomène, il est avisé denormaliser

systématiquementles polynômes intermédiaires de manière à ce que le coefficient de leur

terme de tête soit toujours égal à1. Terminologie 5.2.Étant donné un polynôme de degrék>0:

P(x) =ckxk+ck1xk1++ +c0(ck6=0);

on appellecoefficient de têtele nombre : c k2A; et on dit quePunitairelorsque : c k= 1: Par exemple, dans l"anneauA=Q[x]des polynômes à coefficients dans lecorpsdes nombres rationnels, on peut toujoursdiviserP(x)par son coefficient de tête de manière à le rendreunitaire :1c kP(x) =xk+ck1c kxk1++c0c k:

Une expérience renouvelée des calculs à la main ou sur ordinateur a montré que dans l"al-

gorithme d"Euclide, il est avisé derendre unitaires tous les restes intermédiairesafin de

rabaisser la complexité des coefficients rationnels des polynômes. Au final, après exécu-

tion de toutes les divisions euclidiennes requises, le polynômepgcdentre deux polynômes donnésA;B2Q[x]: pgcd(A;B)2Q[x];

10 FrançoisDEMARÇAY, Département de Mathématiques d"Orsay, Université Paris-Saclay, Francesera connu à un facteur rationnel non nul près.

Bien entendu, ce qui est vrai ici pourQ[x]est vrai aussi pour tout anneau de polynômes

K[x]à coefficients dans un corps commutatifK.

Mais comment s"y prendre si l"on désire travailler, plus généralement, avec l"anneau des polynômes à coefficients dans un anneau euclidienAqui n"est pas forcément un corps? Il suffit - certes un peu artificiellement - de demander l"existence de formes nor- males au sens précis qui suit. Définition 5.3.Un anneau euclidien est ditnormalsi tout élémenta2Apossède une forme normale unique :

Normal(a)2A

qui diffère deasimplement par une unité : a=uNormal(a)(u2A); la forme normale d"un produit quelconque entre deux élémentsa;b2Aétant égale au produit des formes normales :

Normal(ab) =Normal(a)Normal(b);

deux élémentsa2Aeta02Aayant la même forme normale :

Normal(a) =Normal(a0)

lorsque, et seulement lorsque, ils diffèrent d"une unité : a

0=ua(u2A):

Il est avisé d"introduire une notation pour l"unité dont un élémenta2Aet sa forme normale diffèrent :

Unite(a) :=aNormal(a):

Dans un anneau euclidien normal,pgcdetppcmentre deux éléments quelconques sont alors définis de manière unique, simplement en prenant les formes normales. Exercice 2.Justifer l"affirmation qui précède.

Exercice 3.

(a) SurA=Z, déterminer la forme normale naturelle d"un entier. (b)Faire de même surA=K[x], oùKest un corps.

(c)En utilisant la normalisation de(a), traiter l"algorithme d"Euclide qui permet de calculer lepgcdentre

deux entiers relatifs quelconquesa;b2Z.

6. Algorithme d"Euclide étendu

Soit(A;)un anneau commutatif unitaire euclidien normal. L"idée pour raffiner l"al-

gorithme d"Euclide, simple et déjà comprise plus haut, consiste, lorsqu"on divise itérative-

ment, à normaliser les restes à chaque étape. En tout cas, sans remplacer les restes intermé-

diaires par leurs formes normales, en partant de deux élémentsa;b2Aavec(b)6(a) que l"on renomme : r

0:=aetr1:=b;

6. Algorithme d"Euclide étendu 11

rappelons que l"algorithme de divisions successives jusqu"à épuisement se représente comme suit : r

0=q1r1+r2;

r

1=q2r2+r3;

r i1=qiri+ri+1; r `2=q`1r`1+r`; r `1=q`r`+0; le dernier reste non nul valant : r `=pgcd(r0;r1) =pgcd(a;b): Maintenant, si l"on souhaite faire voir que les restes intermédiaires doivent être norma- lisés, on les représentera sous la forme : iriaveci=Uniteiri; r i=Normal(iri); et en supposant pour simplifier que l"on a déjà normalisé au départ : r

0:=Normal(a); 0:=Unite(a); a=0r0;

r

1:=Normal(b); 1:=Unite(b); b=1r1;

de telle sorte les nouveaux restes intermédiaires avec spécification de normalisation s"écri-

ront :

2r2; 3r3; ::::::; `r`;

on obtiendra la représentation synoptique : r

0=q1r1+2r2;

r

1=q2r2+3r3;

r i1=qiri+i+1ri+1; r `2=q`1r`1+`r`; r `1=q`r`+0: De plus, il s"avère dans certaines applications arithmétiques du calcul depgcdquetous

les résultats intermédiaires possèdent une utilité. Si donc l"on part de deux éléments quel-

conquesa;b2Ad"un anneau euclidien normalA, une organisation systématique (voir ce qui va suivre) des calculs donnera au final l"identité de Bézout : s `a+t`b=pgcd(a;b); mais à chaque étape intermédiaire, on devra aussi écrire : s ia+tib=ri(06i6`):()

12 FrançoisDEMARÇAY, Département de Mathématiques d"Orsay, Université Paris-Saclay, FranceEn fait, il est aisé d"expliquer comment construire par récurrence de tels élémentssi,ti.

Pouri= 0et pouri= 1, on a tout d"abord :

1

0a+0b=r0=:s0a+t0b;

0a+1

1b=r1=:s1a+t1b;

ce qui donne sans difficulté des couples(s0;t0)et(s1;t1)qui conviennent. En raisonnant par récurrence, supposons pour un certain entieriavec16i6`1, on ait déjà obtenu aux deux niveauxieti1: s i1a+ti1b=ri1; s ia+tib=ri: Alors en partant de l"identité de division euclidienne dans laquelle naît le(i+1)-ème reste (normalisé) : r i1=qiri+i+1ri+1;

en réécrivant cette identité et en y insérant les deux identités admises par récurrence :

i+1ri+1=ri1qiri =si1a+ti1bqisia+tib si1qisia+ti1qitib; d"où après division par l"unitéi+1: r i+1=si1qisi i+1 a+ti1qiti i+1 b =:si+1a+ti+1b; ce qui donne les relations de récurrence : s i+1:=si1qisi i+1etti+1:=ti1tisi i+1: Nous pouvons maintenant formuler l"énoncé des instructions avant de démontrer qu"elles sont correctes.Algorithme: Division euclidienne étendue avec mémorisations Entrées :Deux élémentsa;b2Ad"un anneau euclidien normal. Sorties :Un entier d"arrêt`2N, une collection d"élémentsi;ri;si;ti2Apour

06i6`+ 1, et des quotientsqi2Apour06i6`, calculés comme suit.

Algorithme :

0 [Unite(a),r0 [Normal(a),s0 [1=0,t0 [0.

1 [Unite(b),r1 [Normal(b),s1 [0,t1 [1=1.

i [1 tant queri6= 0faire q i [quotientri1divisé parri i+1 [UniteReste(ri1divisé parri) r i+1 [NormalReste(ri1divisé parri)

6. Algorithme d"Euclide étendu 13

s i+1 [si1qisii+1 t i+1 [ti1qitii+1 i [i+ 1 ` [i1

Retourner`,i;ri;si;tipour06i6`+ 1, etqipour16i6`Démonstration.On commence donc par normaliseraetben introduisant :

r 0:=a

0=Normal(a) =Normal(r0);

r 1:=b

1=Normal(b) =Normal(r1):

Comme cela vient d"être implicitement décrit dans la formulation de cet algorithme d"Euclide étendu, les calculs fournissent les relations suivantes entre les quantitésri,si,ti:

2r2=r0q1r1; 2s2=s0q1s1; 2t2=t0q1t1;

i+1ri+1=ri1qiri; i+1si+1=si1qisi; i+1ti+1=ti1qiti;

0 =r`1q`r`; `+1s`+1=s`1q`s`; `+1t`+1=t`1q`t`;

la première colonne ayant déjà été vue, tandis que la seconde et la troisième, en partant de :

s 0:=1

0; t0:= 0;

s

1:= 0; t1:=1

1; définissent par inductionles quantités : s

2;:::;s`+1ett2;:::;t`+1;

dont la nature s"éclaircira dans un instant,cf.l"équation () ci-dessus. Sachant que les deux multiplicateurs de Bézoutsiettise transforment simultanément à chaque étape de l"algorithme, il est naturel de raisonner en termes de matrices22, et plus précisément, il est naturel d"introduire la matrice : R

0:=s0t0

s 1t1 1 00 0 1 1 accompagnée des`matrices : Q i:=0 1 1 i+1qi i+1 (16i6`); et enfin, d"introduire aussi les`produits de matrices : R i:=QiQ1R0(16i6`):

14 FrançoisDEMARÇAY, Département de Mathématiques d"Orsay, Université Paris-Saclay, FranceLemme.Pour tout entier intermédiaireiavec06i6`, on a :

R ia bquotesdbs_dbs21.pdfusesText_27

[PDF] algorithme de dijkstra python

[PDF] algoritmo de dijkstra java

[PDF] aliexpress france avis

[PDF] alkyl and aryl halides notes pdf

[PDF] alkyl halides notes pdf

[PDF] all google sites list

[PDF] all html5 tags list with examples pdf

[PDF] all police codes mn

[PDF] all the methods in the interface are internally

[PDF] allan_and_barbara_pease_ _body_language_the_definitive_book.pdf

[PDF] allemand langage familier

[PDF] aller + infinitif exercices

[PDF] aller retour paris ajaccio air france

[PDF] aller retour paris nice avion

[PDF] alliance gradebook pinnacle