Le pgcd et l'algorithme d'Euclide Bezout
24
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
24
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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.
Voir
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
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 charni ere pour l'alg ebre, dont leschapitres suivants traiteront diffe´rents aspects. Onparleraplusend´etaildesanneauxquotientsZnprlaalim´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´Anserdealitravailena zetsidubirelreconslemps,xengso ´equipepuis amutualiservossolutions.Lebutseradere´unirlesfonctionsd'int´erˆetge´n´eraldanslechier integer.ccontshi uenqeumeibntie-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. Premie res applications.3.1. Inversion dans l'anneau quotientZnrestedesr.L eetmh.´3e.o2se chinois. 3.3. Un de´veloppement plus efcace. Approfondissement. evtlabocevi enemnnasxuaeialuederL'ae´usemrbnnxeIerXtutaocmmiufiqs seraessentielpourlasuite.Onsaisitl'occasiondesoulignerquelquesaspectsalgorithmiquesetdepr´eparer ainsinosfuturesimple´mentationsd'anneauxplusge´ne´raux.LeprojetIXpr´esentel'algorithmedeGauss-Be´zoutpourlare´solutiondesyst emesd'´equationsline´airessurZ. On en de´duit le the´or eme des diviseurs ´el´ementairesetlaclassicationdesgroupesab´eliensnimentengendr´es. 1. Structure de l'anneauZ 1.1. Structure d'anneau factoriel.ofemmadnatneledlLe´eth eorottuqteureneitthm´'ariuedietiq positifas'exprime de mani ere unique comme produit de nombres premiers positifs : a=2Η23Η35Η57Η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) =Õpmin(Ηp(a),Ηp(b))et ppcm(a,b) =Õpmax(Η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,lafactorisationestunprobl emetr esdur,dontonneconnaˆtpasdem´ethode rapide(nousyreviendronsauchapitreXI).Heureusementpourlepgcdilexisteunalgorithmetr esefcace, l'algorithme d'Euclide, qui e´vite enti erement le proble me de factorisation. 151
152
ChapitreIXLepgcdetl'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=ba, l'autre avecq=abscleel;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 int egre et admet une division euclidienne. D'apr es ce qui pre´c ede,Zest euclidien par rapport au stathmeΗ(a) =|a|. Quant a la division eucli-dienne≅seiles:ellesplusutlbmeltnenavissetiontsunsscLeveonixpoecholes.ssibnuieo,an´tdenin choisissent les quotientsq=ab,q=ba,q=ba, etq=ba.emtntivespecre Exercice/P 1.3.uolrPepesseytrsenntie'op´C++lnoitarea/bdonneab, la partie enti ere 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. Tr es 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´eniOnpeme ivideenurxueddilineenioisucneoenchissant 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ˆememani ereonpourrad´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 biblioth eque GMP. Exercice/P 1.5.´eonnoconeUc¸fasiohriuqimcede(q,r)est d'exigera=bq+ravec|r| ≤21|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´daL usob=2netr=±n. An de re´soudre cettederni ereambigu¨t´e,onpourrachoisirl'uniquecuople(q,r)avecqpair. MAE22 juin 2009
