Chapitre 2 - PGCD et PPCM

495 correspond au plus grand diviseur qui soit commun aux deux nombres 159390 et 49005 Propriété - Définition (voir démonstration 01 ) Soient a et b deux entiers naturels non nuls Un entier naturel qui divise a et qui divise b est appelé diviseur commun à a et b

Plus grand commun diviseur (pgcd) Théorèmes de Bézout et de Gauss

1 PLUS GRAND COMMUN DIVISEUR (PGCD) 1 Plus grand commun diviseur (pgcd) 1 1 Déﬁnition Définition 1 : Soit a et b deux entiers relatifs non tous nuls L’ensemble des diviseurs communs à a et b admet un plus grand élément d, ap-pelé plus grand commun diviseur On note : d =pgcd(a,b) Remarque : On note aussi pgcd(a,b)=a ∧b

PGCD (Plus grand commun diviseur) - lewebpedagogiquecom

PGCD (Plus grand commun diviseur) Dans la notion de PGCD, il y a la notion de diviseur Par exemple : • 15 est un diviseur de 120 parce que la division de 120 par 15 "tombe juste" : 120 = 15×8 • Dans les problèmes concrets, cela reviendra à dire qu'on peut faire un nombre exact de lots, de sachets, de bouquets

Plus grand commun diviseur (pgcd) Théorèmes de Bézout et de Gauss

EXERCICES 8 mars 2021 à 9:16 Plus grand commun diviseur (pgcd) Théorèmes de Bézout et de Gauss PGCD EXERCICE 1 Déterminer les entiers naturels n tels que : 1) n 6200 et pgcd(n,324)=12

Corrigé de l’exercice 1 - alloschoolcom

plus grand un comm diviseur (pgcd) de 19 630 et 2 210 On calcule le pgcd des bres nom 19 630 et 2 210 en t utilisan l'algorithme d'Euclide 19630=2210×8+1950 2210=1950×1+260 1950=260×7+130 260=130×2+0 Donc le pgcd de 19 630 et 2 210 est 130 3 Simpli er la fraction 19630 2210 p our rendre irréductible en t indiquan métho de 19630 2210

Chapitre 2 - PGCD et PPCM

Chapitre 2 - PGCD et PPCM Dans ce chapitre, lorsque nous parlerons de diviseur , cela signiﬁera diviseur positif 1 Plus grand commun diviseur : PGCD 1 1 D´eﬁnition du plus grand commun diviseur Soit a et b deux entiers naturels On note D(a) l’ensemble des diviseurs positifs de a et D(a,b) l’ensemble des diviseurs positifs de a et de b

PGCD et PPCM dans Z Applications - CBMaths

1 PGCD (plus grand commun diviseur) Déﬁnition 1 1(Plus grand commun diviseur) Soient a, bdeux nombres entiers relatifs non nuls L’ensemble des diviseurs communs de aet de badmet un plus grand élément que l’on appelle le plus grand commun diviseur de aet de b Remarques 1 2 1 bjasi et seulement si PGCD(a;b) = b

Calcul du PGCD - Ge

Le PGCD (Plus Grand Diviseur Commun) de deux entiers est le plus grand nombre capable de diviser 2 entiers de manière complète sans laisser de reste et ceci doit être valable pour le premier comme pour le deuxième de ces entiers

exercices de mathématiques 3ème PGCD

Calculer le plus grand commun diviseur (pgcd) de 10 400 et 1 690 On calcule le pgcd des nombres 10 400 et 1 690 en utilisant l’algorithme d’Euclide 10 400 = 1 690 × 6+260 1 690 = 260 × 6 +130 260 = 130 × 2+0 Donc le pgcd de 10 400 et 1 690 est 130 3 Simpliﬁer la fraction 10 400 1 690 pour la rendre irréductible en indiquant la

Division euclidienne PPCM-PGCD - Meilleur en Maths

Division euclidienne PPCM PGCD Le plus grand diviseur commun de 963 et 153 est 9 4 2 Notation On note pgcd(a;b) ou(a∧b) le plus grand diviseur commun de a et b 4 3 Conséquence L'ensemble des diviseurs communs de a et b est l'ensemble des diviseurs de pgcd(a;b) 4 4 Propriété 1 a et b étant 2 entiers naturels non nuls ou a∧b=b

[PDF] Plus grand diviseur commun (devoir maison)

[PDF] PLUS GRAND DIVISEUR COMMUN ; NOMBRES PREMIERS ET NOMBRES PREMIERS ENTRE EUX

[PDF] plus grand ouragan de l'histoire

[PDF] plus grand roi de france taille

[PDF] plus grande colonie au 19 siecle

[PDF] Plus grande hauteur, avec une feuille CANSON!

[PDF] plus grande zone commerciale d'europe

[PDF] plus gros char d'assaut du monde

[PDF] plus gros compte instagram france

[PDF] plus jeune bachelier du monde

[PDF] plus noir que noir utiliser des matériaux

[PDF] plus on regarde loin dans l espace plus on regarde dans le passé

[PDF] Plus ou moins de la moitié

[PDF] Plus ou moins grand que la moitié dsl je l'ais fermer sen faire exprès

[PDF] plus ou moins value court terme long terme

Chapitre 2 - PGCD et PPCM

Dans ce chapitre, lorsque nous parlerons de diviseur , cela signifiera diviseurpositif.

1 Plus grand commun diviseur : PGCD

1.1 D´efinition du plus grand commun diviseur

Soitaetbdeux entiers naturels.

On noteD(a) l"ensemble des diviseurs positifs deaetD(a,b) l"ensemble des diviseurs positifs deaet deb.

Exemple 1

On aD(10) ={1,2,5,10}etD(11) ={1,11}

D(12) ={1,2,3,4,6,12}etD(28) ={1,2,4,7,14,28}donc on aD(12,28) ={1,2,4}

Remarque 1

Lorsquea >1,D(a)contient toujours 1 eta.

Sia?= 0,D(a)ne contient que des entiers naturels inf´erieurs ou ´egaux `aa

D(0)=N

D(1)={1}

D(a,b)=D(a)∩ D(b)

D(0,b)=D(b)

D(12)

D(28)×7

×14

×28

×1

×2×4

×6×3

×12

D(a,b) est un ensemble non vide car il contient toujours 1 et tous les ´el´ements deD(a,b) sont inf´erieurs

`aasia?= 0 et et `absib?= 0

Donc siaetbsont deux entiers naturels dont l"un d"entre eux est non nul,D(a,b) est un ensemble non vide et

contient un nombre fini d"´el´ements, il admet donc un plus grand ´el´ement.

D´efinition

1 Soitaetbdeux entiers naturels dont l"un est non nul. Le plus grand diviseur commun `aaetbest le plus grand ´el´ement deD(a,b).

On le note en abr´eg´ePGCD(a,b)

Remarque 2

Pour deux entiers relatifs non tous nuls, il faudrait rajouter les diviseurs n´egatifs deaet deben prenant les oppos´es des

´el´ements deD(a)et deD(b). ainsi , le PGCD de deux entiers relatifs se d´etermine de la mˆeme fa¸con et donc le PGCD de deux

entiers relatifs est celui de leur valeur absolue. Chapitre 2 - PGCD et PPCM Page 1/??Terminale S - sp´ecialit´e - M. Schavsinski

A faire : ex .1 p.31 et ex 1,4,8 p.54

D´efinition

2 Deux entiers relatifsaetbsont dits premiers entre eux siPGCD(a,b) = 1

Propri´et´e1

Soitaetbdeux entiers naturels tels quea?= 0.

SiadivisebalorsPGCD(a,b) =a

Preuve :

adivisebdonc tous les diviseurs deasont aussi des diviseurs deb.

DoncD(a)? D(b) et doncD(a)∩ D(b) =D(a)

AinsiD(a,b) =D(a)

doncPGCD(a,b) =a

1.2 Recherche du PGCD : algorithme d"Euclide

Propri´et´e2Lemme d"Euclide

Soientaetbdeux entiers non nuls tels quea?b

Effectuons la division euclidienne deaparb: il existe deux entiersqetrtels quea=bq+ro`u0?r < b. AlorsD(a,b) =D(b,r)et en particulier,PGCD(a,b) =PGCD(b,r).

Preuve :

Soitm? D(a,b)

Alorsmdiviseaetbdoncmdivise toute combinaison lin´eaire deaetbdoncmdivisea-bq. mdivise doncr.

Doncm? D(b,r)

On a doncD(a,b)? D(b,r)

R´eciproquement ,soitp? D(b,r)

Alors , de la mˆeme mani`ere,pdivise toute combinaison lin´eaire debetrdoncmdivisebq+r. mdivise donca.

Doncm? D(a,b)

On a doncD(b,r)? D(a,b)

En conclusion, on aD(a,b) =D(b,r)

Les plus grands ´el´ements sont donc ´egaux d"o`uPGCD(a,b) =PGCD(b,r).

Th´eor`eme

1Th´eor`eme de l"algorithme d"Euclide

Soientaetbdeux entiers non nuls tels quea?b

Lorsquebne divise pasa, on effectue la division euclidienne deaparbpuis successivement les divisions du diviseur

pr´ec´edent par le reste pr´ec´edent, lePGCD(a,b)est alors le dernier reste non nul obtenu.

Lorsquebdivisea, on a ´evidemmentPGCD(a,b) =b

Preuve :

Effectuons la division euclidienne deaparb:

Il existeq0etr0tels quea=bq0+r0o`u 0< r0< bet d"apr`es le Lemme d"Euclide, on a doncD(a,b) =D(b,r0) et,

en particulier,PGCD(a,b) =PGCD(b,r0)

Continuons :

Il existeq1etr1tels queb=r0q1+r1o`u 0?r1< r0

Chapitre 2 - PGCD et PPCM Page 2/??Terminale S - sp´ecialit´e - M. Schavsinski Sir1= 0 alorsr0divisebdonc d"apr`es la propri´et´e 1,PGCD(b,r0) =r0. Sir1?= 0, il existeq1etr1tels queb=r0q1+r1o`u 0< r1< r0 et d"apr`es le Lemme d"Euclide, on a doncD(b,r0) =D(r0,r1) c"est-`a-direD(a,b) =D(r0,r1)

Et aussi, en particulier,PGCD(a,b) =PGCD(r0,r1)

On effectue ainsi de suite les divisions euclidiennes successives tant qu"on obtient pas de reste nul.

On obtient une suite (rn) de termes positifs et cette suite est strictement d´ecroissante. On va donc n´ecessairement avoir un reste nul que nous noteronsrn. D"apr`es ce que nous avons vu pr´ec´edemment, on aD(a,b) =D(rn-1,rn)

C"est-`a-direD(a,b) =D(rn-1,0)

doncD(a,b) =D(rn-1) d"apr`es une remarque du 1.1 d"o`uPGCD(a,b) =rn-1qui est bien le dernier reste non nul .

Exemple 2

Cherchons pgcd(27;59), en utilisant l"algorithme d"Euclide :

59 = 27×2 + 5

27 = 5×5 + 2

5 = 2×2 + 1

2 = 1×2 + 0

donc PGCD(29;57)=1

Th´eor`eme

2Cons´equence importante

L"ensemble des diviseurs communs `a deux entiers positifsaetbest l"ensemble des diviseur de leur PGCDd,

autrement ditD(a,b) =D(d) En particulier, tout diviseur deaetbest un diviseur de leur PGCD Preuve :On a vu queD(a,b) =D(rn-1) et quern-1est le Pgcd.

A faire : ex 1 `a 8 p.54

2 Th´eor`eme de Bezout

Th´eor`eme3

Soientaetbdeux entiers naturels non nuls.

aetbsont premiers entre eux si et seulement s"il existe deux entiers relatifsuetvtels queau+bv= 1

Preuve :

Supposons qu"il existe deux entiers relatifsuetvtels queau+bv= 1

Soitg=PGCD(a;b)

gdiviseaetbdoncgdiviseau+bv Doncgdivise 1. D"o`ug= 1 etaetbsont premiers entre eux

SoitFl"ensemble des nombresau+bvo`uuetvsont dansZ

Fest non vide et contient des nombres strictement positifs ( en prenantuetvdansN) Notons alorsF+les ´el´ements strictement positifs deF

Cet ensembleF+est un sous ensemble deNet non vide donc il admet un plus petit ´el´ementm. Notonsm=au1+bv1

D´emontrons quemdiviseaetb( doncm? D(a;b) )

Effectuons la division euclidienne deaparm:

Il existe deux entiersqetrtels quea=mq+ret avec 0?r < m Chapitre 2 - PGCD et PPCM Page 3/??Terminale S - sp´ecialit´e - M. Schavsinski

Doncr=a-mqc"est-`a-direr=a-(au1+bv1)q

puisr=a-aqu1+bqv1et doncr=a(1-qu1) +bqv1 Donc ,sir?= 0 ,r? F+maisr < mce qui est impossible puisquemest le plus petit ´el´ement deF+.

Doncr= 0, c"est-`a-dire quemdivisea.

De mˆeme, on pourrait montrer quemdiviseb.

Doncm? D(a;b) maisaetbsont premiers entre eux doncm= 1 D"o`u il existe deux entiersu1etv1tels queau1+bv1= 1

M´ethode :

Pour trouver les deux entiersuetvdu th´eor`eme, on remonte l"algorithme d"Euclide. Cela revient `a r´esoudre une ´equation dite "diophantienne" que nous verrons au V)

Exemple 3

Nous avons vu que pgcd(27;59)=1 en utilisant l"algorithme d"Euclide. Cherchonsuetvpour que27u+ 59v= 1`a l"aide

ces op´erations, en isolant `a chaque fois le reste, en partant de la fin et en remontant afin d"obtenir le dernier reste non nul en

fonction de 27 et 59 :

5-2×2 = 1

27-5×5 = 2donc5-(27-5×5)×2 = 1

Ce qui donne donc5-27×2 + 10×5 = 1

Puis on a11×5-27×2 = 1

59-27×2 = 5donc11×(59-27×2)-27×2 = 1

Ce qui donne59×11-27×22-27×2 = 1

Et donc59×11-27×24 = 1

3 Caract´erisation et propri´et´e du PGCD

3.1 Caract´erisation du PGCD

Th´eor`eme4

Soienta,b,dtrois entiers strictement positifs. Les trois propositions suivantes sont ´equivalentes :

1.PGCD(a;b) =d

2. soita?etb?tels quea=da?etb=db?alorsPGCD(a?;b?) = 1

3.dest un diviseur deaetbet il existe deux entiersuetvtels queau+bv=d

Preuve :

(1)?(2) SoitPGCD(a;b) =dalorsddiviseaetbet il existea?etb?tels quea=da?etb=db?.

Soitδun diviseur commun dea?etb?.

Il existe donca??etb??tels quea?=δa??etb?=δb?? Alors on peut ´ecrirea=dδa??etb=dδb??doncdδest un diviseur commun deaetb. Siδ >1, on a un diviseur commun `aaetbqui est plus grand que lepgcd(a;b) ce qui est impossible. Donc le seul diviseur commun possible poura?etb?est 1

D"o`upgcd(a?;b?) = 1

(2)?(3) soita?etb?tels quea=da?etb=db?alorsPGCD(a?;b?) = 1 Donc, d"apr`es le th´eor`eme de Bezout, il existe deux entiersuetvtels quea?u+b?v= 1

Multiplions pard:da?u+db?v=dpuis,au+bv=d

Donc il existe deux entiersuetvtels queau+bv=d

(3)?(1) Soitdun diviseur deaetbet supposons qu"il existe deux entiersuetvtels queau+bv=d Chapitre 2 - PGCD et PPCM Page 4/??Terminale S - sp´ecialit´e - M. Schavsinski

Soitgle pgcd deaetb.

Maisddiviseaetbdoncddivisegd"apr`es le th´eor`eme 2.

Doncd=gc"est-`a-dired=pgcd(a;b)

3.2 propri´et´e du PGCD

Propri´et´e3

Soita,betktrois entiers naturels non nuls.

AlorsPGCD(ka,kb) =k×PGCD(a,b)

Preuve :

Soitd=PGCD(a,b)

Nous voulons utiliser le th 4 :

ddiviseaetbdonckddivisekaetkb Montrons maintenant qu"il existe deux entiersuetvtels quekau+kbv=kd D"apr`es le th 4, commed=PGCD(a,b), il existe deux entiersuetvtels queau+bv=d. En effectuant le produit park, on a donckau+kbv=kd Donckdest un diviseur dekaetkbet il existe deux entiersuetvtels quekau+kbv=kd doncpgcd(ka;kb) =kdc"est-`a-direpgcd(ka;kb) =k×pgcd(a,b)

Exemple 4

PGCD(45;120) = 15×PGCD(3;8)doncPGCD(45;120) = 15

4 Applications

4.1 Th´eor`eme de Gauss

Th´eor`eme5de Gauss

Soienta,betctrois entiers strictement positifs.

Siadivisebcet siaest premier avecbalorsadivisec

Preuve :

aest premier avecbdonc, d"apr`es le th´eor`eme de Bezout, il existe deux entiersuetvtels queau+bv= 1

En effectuant le produit parc, on aacu+bcv=c

Oradiviseacuetadivisebcpar hypoth`ese, doncadivisec.

Propri´et´e

4corollaire du th. de Gauss

Si un entiernest divisible par deux entiers naturelsaetbpremiers entre eux, alors il est divisible para×b

Exemple 5

Trouvons les couples d"entiers(x;y)tels que11x= 6yet0?x <25

6 divise11xet 6 et 11 sont premiers entre eux donc, d"apr`es le th´eor`eme de Gauss, 6 divisex

doncxpeut prendre les valeurs 0, 6, 12 ,18 ou 24 Les couples possibles sont donc ( 0,0 ); ( 6,11); ( 12,22); ( 18,33) et ( 24,44 ) Chapitre 2 - PGCD et PPCM Page 5/??Terminale S - sp´ecialit´e - M. Schavsinski

4.2 Fractions irr´eductibles

D´efinition3

Une fractiona

best dite irr´eductible siaetbsont premiers entre eux.

Th´eor`eme6

On peut toujours rendre une fraction irr´eductible

Preuve :

Si elle n"est pas irr´eductible, il suffit de la simplifier par le pgcd du num´erateur et du d´enominateur pour obtenir une fraction

irr´eductible.

5 Equations diophantiennes

Diophante d"Alexandrie, parfois appel´e le?p`ere de l"alg`ebre?, est connu par son ouvrage les Arithm´etiques, qui traite des

solutions des ´equations alg´ebriques.

On ne sait pratiquement rien de sa vie et ses dates de naissance et de mort sont tr`es controvers´ees.

Les Arithm´etiques sont une collection de solutions num´eriques de 130 ´equations.

La m´ethode de r´esolution des ´equations ind´etermin´ees constitue ce qu"on a appel´e l"analyse diophantienne.

Diophante consid`ere des ´equations lin´eaires et du second degr´e, mais ne retient queles solutions rationnelles positives.

Nous allons donc chercher `a r´esoudre des ´equations du typeax+by=co`ua,b,csont dansZet o`u les solutions sont dansZ.

Ce sont des ´equations diophantiennes.

Th´eor`eme

7 L"´equationax+by=cadmet des solutions si et seulement si lePGCD(a;b)divisec

Preuve :

Supposons queax+by=cadmet une solution.

Notons cette solution (xo;yo), on a doncaxo+byo=c. pgcd(a;b) diviseaetbdoncpgcd(a;b) diviseaxo+byo

Doncpgcd(a;b) divisec.

Supposons quePGCD(a;b) divisec.

Cela signifie que , si on noted=PGCD(a;b), on addivisec.

Doncddivise,a,betc.

On a alors l"existence de 3 entiersa?,b?etc?tels quea=da?,b=db?etc=dc? Et, de plus, d"apr`es le th´eor`eme 4,PGCD(a?;b?) = 1 D"apr`es le th´eor`eme de Bezout, il existe deux entiersuetvtels quea?u+b?v= 1

Effectuons le produit parc?:

a ?uc?+b?vc?=c? puis le produit pard: auc ?+bvc?=c Donc il existe une solution (uc?;vc?) `a l"´equationax+by=c. M´ethode pour r´esoudre une ´equation diophantienneax+by=c:

1. V´erifier si elle a des solutions `a l"aide du th´eor`eme pr´ec´edent

2. R´esoudre l"´equationax+by=pgcd(a;b) avec la m´ethode vue au II)

3. Trouver une solution particuli`ere `aax+by=cen mutipliant parc?o`uc?est tel quec=c?×pgcd(a;b)

4. Trouver toutes les solutions `aax+by=c`a l"aide du th´eor`eme de Gauss comme dans l"exemple 5

Chapitre 2 - PGCD et PPCM Page 6/??Terminale S - sp´ecialit´e - M. Schavsinski

Exemple 6

R´esoudre175x+ 129y= 4

1. V´erifions s"il y a des solutions :

Calculons le PGCD(175;129) `a l"aide de l"algorithme d"Euclide :

175 = 129×1 + 46

129 = 46×2 + 37

46 = 37×1 + 9

37 = 9×4 + 1

9 = 1×9 + 0

donc PGCD(175;129)=1 et donc PGCD(175;129) divise 4 donc ilexiste des solutions

2. Utilisons le th´eor`eme de Bezout pour trouver une solution particuli`ere `a l"´equation175x+ 129y= 1:

37-9×4 = 1

puis46-37×1 = 9donc37-(46-37×1)×4 = 1

Ce qui donne37×5-46×4 = 1

Puis129-46×2 = 37donc(129-46×2)×5-46×4 = 1

Ce qui donne129×5-46×14 = 1

Puis175-129×1 = 46donc129×5-(175-129×1)×14 = 1

Ce qui donne129×19-175×14 = 1

Donc , en posantxo=-14etyo= 19, on a175xo+ 129yo= 1

3. Trouvons une solution particuli`ere de175x+ 129y= 4en multipliant par 4 :

Comme175xo+ 129yo= 1, on a175×4xo+ 129×4yo= 4. Donc (-56,76) est solution particuli`ere de l"´equation175x+ 129y= 4.

4. D´eduisons en toutes les solutions de175x+ 129y= 4`a l"aide du th´eor`eme de Gauss :

Nous cherchons les couples(x,y)tels que175x+ 129y= 4

Nous avons175× -56 + 129×76 = 4

En soustrayant ces deux ´equations, nous avons donc175(x+ 56) + 129(y-76) = 0

D"o`u175(x+ 56) =-129(y-76)

129 divise175(x+ 56)

129 et 175 sont premiers entre eux?

?129 divisex+ 56d"apr`es le th´eor`eme de Gauss

Doncx+ 56 = 129kaveck?Z

D"o`ux=-56 + 129k

En rempla¸cant , on obtienty= 76 + 175k

En conclusion, les solutions de cette ´equation sont les couples(-56 + 129k;76 + 175k)aveck?Z

Exemple 7

R´esoudre4x+ 8y= 10

1. pgcd(4;8)=4.

Or 4 ne divise pas 10 donc il n"y a pas de solution. Chapitre 2 - PGCD et PPCM Page 7/??Terminale S - sp´ecialit´e - M. Schavsinski

6 Plus Petit Commun Multiple

Deux entiers positifs ont des multiples communs ( par exemple le produit de ces deux entiers ).

L"ensemble des multiples communs est un sous ensemble non vide deNdonc il admet un plus petit ´el´ement.

D´efinition

4 On appelle PPCM deaetbet on notePPCM(a;b)le plus petit multiple commun `aaetb

Propri´et´e5

Soientaetbdeux entiers naturels non nuls.

Soitm=PPCM(a;b)

Sicest un multiple commun deaetbalorsmdivisec.

Propri´et´e6

Soienta,betktrois entiers naturels non nuls.

AlorsPPCM(ka;kb) =k×PPCM(a;b)

Th´eor`eme8

Soientaetbdes entiers strictement positifs.

PGCD(a;b)×PPCM(a;b) =a×b

Chapitre 2 - PGCD et PPCM Page 8/??Terminale S - sp´ecialit´e - M. Schavsinskiquotesdbs_dbs48.pdfusesText_48

[PDF] Chapitre 2 - PGCD et PPCM

Chapitre 2 - PGCD et PPCM

1 Plus grand commun diviseur : PGCD

1.1 D´efinition du plus grand commun diviseur

Soitaetbdeux entiers naturels.

Exemple 1

On aD(10) ={1,2,5,10}etD(11) ={1,11}

Remarque 1

Lorsquea >1,D(a)contient toujours 1 eta.

 D(0)=N

 D(1)={1}

 D(a,b)=D(a)∩ D(b)

 D(0,b)=D(b)

D(28)×7

×14

×28

×2×4

×6×3

×12

D´efinition

On le note en abr´eg´ePGCD(a,b)

Remarque 2

A faire : ex .1 p.31 et ex 1,4,8 p.54

D´efinition

Propri´et´e1

Soitaetbdeux entiers naturels tels quea?= 0.

SiadivisebalorsPGCD(a,b) =a

Preuve :

DoncD(a)? D(b) et doncD(a)∩ D(b) =D(a)

AinsiD(a,b) =D(a)

1.2 Recherche du PGCD : algorithme d"Euclide

Propri´et´e2Lemme d"Euclide

Soientaetbdeux entiers non nuls tels quea?b

Preuve :

Soitm? D(a,b)

Doncm? D(b,r)

On a doncD(a,b)? D(b,r)

R´eciproquement ,soitp? D(b,r)

Doncm? D(a,b)

On a doncD(b,r)? D(a,b)

En conclusion, on aD(a,b) =D(b,r)

Th´eor`eme

1Th´eor`eme de l"algorithme d"Euclide

Soientaetbdeux entiers non nuls tels quea?b

Lorsquebdivisea, on a ´evidemmentPGCD(a,b) =b

Preuve :

Effectuons la division euclidienne deaparb:

Continuons :

Il existeq1etr1tels queb=r0q1+r1o`u 0?r1< r0

Et aussi, en particulier,PGCD(a,b) =PGCD(r0,r1)

C"est-`a-direD(a,b) =D(rn-1,0)

Exemple 2

59 = 27×2 + 5

27 = 5×5 + 2

5 = 2×2 + 1

2 = 1×2 + 0

Th´eor`eme

2Cons´equence importante

A faire : ex 1 `a 8 p.54

2 Th´eor`eme de Bezout

Th´eor`eme3

Soientaetbdeux entiers naturels non nuls.

Preuve :

Soitg=PGCD(a;b)

SoitFl"ensemble des nombresau+bvo`uuetvsont dansZ

D´emontrons quemdiviseaetb( doncm? D(a;b) )

Effectuons la division euclidienne deaparm:

Doncr=a-mqc"est-`a-direr=a-(au1+bv1)q

Doncr= 0, c"est-`a-dire quemdivisea.

De mˆeme, on pourrait montrer quemdiviseb.

M´ethode :

Exemple 3

5-2×2 = 1

27-5×5 = 2donc5-(27-5×5)×2 = 1

Ce qui donne donc5-27×2 + 10×5 = 1

Puis on a11×5-27×2 = 1

59-27×2 = 5donc11×(59-27×2)-27×2 = 1

Ce qui donne59×11-27×22-27×2 = 1

Et donc59×11-27×24 = 1

3 Caract´erisation et propri´et´e du PGCD

Lorsquea >1,D(a)contient toujours 1 eta.

D(0)=N

D(1)={1}

D(a,b)=D(a)∩ D(b)

D(0,b)=D(b)

Soitm? D(a,b)

R´eciproquement ,soitp? D(b,r)