Le pgcd et l'algorithme d'Euclide Bezout

Felix Klein

Description

Niveau: Secondaire, Lycée
CHAPITRE IX Le pgcd et l'algorithme d'Euclide-Bezout Unsere Allergroßten, wie Archimedes, Newton, Gauß, haben stets Theorie und Anwendung gleichmaßig umfaßt. Felix Klein, Elementarmathematik vom hoheren Standpunkt aus, 1908 Objectifs Ce chapitre reprend l'arithmetique des nombres entiers, notamment l'algorithme d'Euclide et ses nombreuses ramifications. C'est une relecture de l'arithmetique sous un aspect algorithmique : structures algebriques sous-jacentes, preuve de correction, analyse de complexite. C'est aussi une etape charniere pour l'algebre, dont les chapitres suivants traiteront differents aspects. On parlera plus en detail des anneaux quotients Zn au chapitre X, de la primalite et de la factorisation d'entiers au chapitre XI, on implementera le corps des fractions Q au chapitre XII, suivi de l'anneau Z[i] dans le projet XII et des anneaux des polynomes au chapitre XIII. Implementation. — Afin de realiser des implementations complexes, songez a distribuer le travail en equipe puis a mutualiser vos solutions. Le but sera de reunir les fonctions d'interet general dans le fichier integer.cc commence en chapitre II. Vous obtenez ainsi une mini-bibliotheque portant sur l'arithmetique des entiers. Les implementations continueront tout au long des chapitres suivants. Comme d'habitude il convient de bien tester et commenter vos implementations, d'autant plus en vue d'une reutilisation. Sommaire 1.

• theoreme de dirichlet


• algorithme d'euclide-bezout


• classe integer


• division euclidienne avec reste positif


• integer


• pgcd


• division euclidienne


• algorithme d'euclide


• anneaux z

Sujets

• Mathématiques
• Algèbre
• Théorème de Dirichlet
• Integer
• Division euclidienne
• Algorithme d'Euclide

Informations

• Publié par: sucun
• Nombre de lectures: 237
• Langue: Français

Extrait

Unsere Allergro¨ßten, wie Archimedes, Newton, Gauß, haben stets Theorie und Anwendung gleichma¨ßig umfaßt. Felix Klein,atsuElementkitahmovamramehtndtankpuhe¨onSre, 1908

CHAPITRE IX

Lepgcdetl'algorithmed'Euclide-B ´ ezout

Objectifs Ce chapitre reprend l'arithme´tique des nombres entiers, n otamment l'algorithme d'Euclide et ses nombreuses ramications. C'est une relecture de l'arithm´etique sous un aspect algorithmique : structures alge´briques sous-jacentes, preuve de correction, analyse de complexite´. C'est aussi une e´tape charniere pour l'algebre, dont leschapitres suivants traiteront diffe´rents aspects. Onparleraplusend´etaildesanneauxquotientsZ n prlaalim´eitdeetafalrotctasinoiuahcpatier,Xed d'entiers au chapitre XI, on imple´mentera le corps des fractionsQau chapitre XII, suivi de l'anneauZ[i] dans le projet XII et des anneaux des polyn ˆomes au chapitre XIII. Imple´mentation. —lpe´semitaoiemtnder´Anserdealitravailenazetsidubirelreconslemps,xengso ´equipepuisamutualiservossolutions.Lebutseradere´unirlesfonctionsd'int´erˆetge´n´eraldanslechier integer.ccontshiuenqeumeibntie-nbeizblaiirIuI'Vl.ruaotoisohpctprantaisetrncemeen´e´ehmqoumtic desentiers.Lesimpl´ementationscontinueronttoutaulongdeschapitressuivants.Commed'habitudeil convientdebientesteretcommentervosimple´mentations,d'autantplusenvued'uner´eutilisation. Sommaire 1. Structure de l'anneauZ.1.1. Structure d'anneau factoriel. 1.2. euclidien. Structure d'annea u 2. Le pgcd et l'algorithme d'Euclide.2.1. De´nition du pgcd. L'algorithme d'Euclide. 2.2. 2.3.Analysedecomplexite´.2.4.B´ezoutouEuclide´etendu. 3. Premieres  applications.3.1. Inversion dans l'anneau quotientZ n restedesr.Leetmh.´3e.o2se chinois. 3.3. Un de´veloppement plus efcace. Approfondissement. —evtlabocevienemnnasxuaeialuederL'ae´usemrbnnxeIerXtutaocmmiufiqs seraessentielpourlasuite.Onsaisitl'occasiondesoulignerquelquesaspectsalgorithmiquesetdepr´eparer ainsinosfuturesimple´mentationsd'anneauxplusge´ne´raux.LeprojetIXpr´esentel'algorithmedeGauss- Be´zoutpourlare´solutiondesystemesd'´equationsline´airessurZ. On en de´duit le the´oreme des diviseurs ´el´ementairesetlaclassicationdesgroupesab´eliensnimentengendr´es. 1. Structure de l'anneauZ 1.1. Structure d'anneau factoriel.ofemmadnatneledlLe´etheorottuqteureneitthm´'ariuedietiq positifas'exprime de maniere unique comme produit de nombres premiers positifs : a=2 Η 2 3 Η 3 5 Η 5 7 Η 7   = Õ p Η p pempreir avec des exposantsΗ p =Η p (a)∈Ndont tous sauf un nombre ni sont nuls. Pour le plus grand commun diviseur (pgcd) et le plus petit commun multiple (ppcm) on obtient alors pgcd(a,b) = Õ p min(Η p (a),Η p (b)) et ppcm(a,b) = Õ p max(Η p (a),Η p (b))  premierppreimerp Bienquecesdeuxformulessoientimportantesd'unpointdevueth´eorique,ellesn'offrentpasde solution efcace pour le calcul du pgcd ou du ppcm : pour ce faire il faudrait d'abord factoriseraetb. Or,pourlesgrandsentiers,lafactorisationestunproblemetresdur,dontonneconnaˆtpasdem´ethode rapide(nousyreviendronsauchapitreXI).Heureusementpourlepgcdilexisteunalgorithmetresefcace, l'algorithme d'Euclide, qui e´vite entierement le probleme de factorisation. 151

152

ChapitreIX—Lepgcdetl'algorithmed'Euclide-B´ezout

´ 1.2. Structure d'anneau euclidien.Etant donnesa∈Zetb∈Z ∗ il existeq,r∈Ztels quea=bq+r ´ et|r|<|b|.Cecnaeppeil´eesutdivision euclidienneavec quotientqet rester. Le couple(q,r)n'est en g´ene´ralpasunique:poura=22 etb=9, par exemple, on aa=2b+4=3b−5. (On a toujours deux solutions : l'une avecq=  b a  , l'autre avecq=  a b  scleel;ulementsi¨onicedtnisteesbdiviseadans Zavec rester=.)0ttCembeau¨igque,matith´euemanueopruamsiengˆastpesn'´etvedtniopnu'detna imple´mentationsurordinateurilfautbienxerunchoix.Pr´ecisonsd'abordlesexigencesge´ne´rales. D ´ enition1.1.SoitAun anneau commutatif. Unedivision euclidiennesurAest la donne´e – d'une fonctionΗ:A→Nv´eriantΗ(a) =0 si et seulement sia=0, et – d'une application≅:A×A ∗ →A×A,(a,b)7→(q,r)telle quea=bq+retΗ(r)<Η(b). Dans ce cas on appelleΗunstathme euclidien, et≅unedivision euclidiennepar rapport au stathmeΗ. De´nition 1.2. Un anneauAest diteuclidiens'il est integre et admet une division euclidienne. D'apres ce qui pre´cede,Zest euclidien par rapport au stathmeΗ(a) =|a|. Quant a la division eucli- dienne≅seiles:ellesplusutlbmeltnenavissetiontsunsscLeveonixpoecholes.ssibnuieo,an´tdenin choisissent les quotientsq=  a b  ,q=  b a  ,q=  b a  , etq=  b a  .emtntivespecre Exercice/P 1.3.uolrPepesseytrsenntie'op´C++lnoitarea/bdonne  a b  , la partie entiere du quotient, appel´equotient«tronque´», ou encore«roarndroeriv´esz». Par exemple5/3vaut1et5%3vaut2, ainsi que(-5)/3vaut-1et(-5)%3vaut-2ons´eque.Parcetnelertsa%bseotmˆduesem´euzouroengieuq a pour la classe. Cette convention a e´te´ adopt´ ´galementIntegersedrmexeselp.Lev´.ersueri ee e Optimisation. —Tres souvent on veut calculer le quotientqet le rester on ˆuren mˆeme temps. Bien s pourrait´ecrireq=a/bpuisr=a%b, mais ceci effectue deux fois la mˆeme division (expliquer pourquoi). Dans ce cas il est plus efcace de n'effectuer qu'une seule di vision euclidienne(a,b)7→(q,r)comme suit : void tdiv( const Integer& a, const Integer& b, Integer& q, Integer& r ) {mpz_tdiv_qr( q.get_mpz_t(), r.get_mpz_t(), a.get_mpz_t(), b.get_mpz_t() );} Integer tdiv( const Integer& a, const Integer& b ) {return a/b;} Integer tmod( const Integer& a, const Integer& b ) {if( b == 0 ) return a; else return a%b;} Aulieudesop´erateurs/et%on peut aussi utiliser deux fonctionstdivettmod. Ceci permet derectierunpetitd´efautdel'ope´rateur%, a savoir quetmod(a,0)est toujours bien de´ni, bien que tdiv(a,0)ne le soit pas. (Expliquer pourquoi c'est mathe´matiquemen t raisonnable.) Exercice/P 1.4.utd´eniOnpemeivideenurxueddilineenioisucneoenchissant l'unique couple(q,r) aveca=bq+ret 0≤r<|b|. Dans ce cas nous ecrivonsq=adivbetr=amodb; c'est la division ´ euclidienne avecreste positif, usuelle en mathe´matique. L'imple´menter sous la forme void pdiv( const Integer& a, const Integer& b, Integer& q, Integer& r ); Integer pdiv( const Integer& a, const Integer& b ); Integer pmod( const Integer& a, const Integer& b ); Delamˆememaniereonpourrad´eniretimpl´ementerladivisnouelcdieinnaeevcesten ´ egatifr: void ndiv( const Integer& a, const Integer& b, Integer& q, Integer& r ); Integer ndiv( const Integer& a, const Integer& b ); Integer nmod( const Integer& a, const Integer& b ); Indication. —le souci d'efcacite´ on pourra commencer parDans tdiv(a,b,q,r)puis corrigerqetr. Vous pouvez aussi consulter la documentation viainfo gmppour vous informer sur les fonctionsfdiv etcdivde la bibliotheque GMP. Exercice/P 1.5.´eonnoconeUc¸fasiohriuqimcede(q,r)est d'exigera=bq+ravec|r| ≤ 2 1 |b|: c'est la division avecreste syme´trique. Ve´rier qu'elleminimise|r|aforouslmepm´lL.i'etsrmene void sdiv( const Integer& a, const Integer& b, Integer& q, Integer& r ); Integer sdiv( const Integer& a, const Integer& b ); Integer smod( const Integer& a, const Integer& b ); Remarque. —adsnelacueelemtnunchoixsonlaisseitine´daLusob=2netr=±n. An de re´soudre cettederniereambigu¨t´e,onpourrachoisirl'uniquecuople(q,r)avecqpair. MAE22 juin 2009