3 PGCD et PPMC

8/9/2019 3 PGCD et PPMC

1/11

PGCD_______

1 Diviseurs communs 2 entiersSoit a et b 2 entiers relatifs non nuls.

Lensemble D(a) des diviseurs de a contient 1, il est non vide et fini dans , il en est de mmepour D(b) lensemble des diviseurs de b.

Alors D(a, b) lensemble des diviseurs communs a et b contient 1 et est fini dans :D(a, b) = D(a) D(b) . Cet ensemble D(a, b) admet donc un plus grand lment m et 1m ;m est un entier naturel non nul.De plus on a dj vu que D(a) et D(b) sont aussi respectivement les ensembles des diviseursdes entiers naturels |a| et |b| et ainsi D(a, b) est aussi lensemble des diviseurs communs auxdeux entiers naturels |a| et |b|.

Do le thorme et la dfinition suivante :

a et b tant 2 entiers relatifs non nuls, lensemble des diviseurs communs a et b admet unplus grand lment m qui est un entier naturel non nul.m est appel le PGCD de a et b et on note m=PGCD(a,b).m est aussi le PGCD des deux entiers naturels |a| et |b|.

Pour le reste du chapitre on continue de garder les notations concernant D(a), D(a,b)dsignant respectivement lensemble des diviseurs de a, lensemble des diviseurs communs

a et b

On se ramne la recherche du PGCD de 2 entiers naturels non nuls.

2 Cas particulier Avec a et b entiers naturels non nuls :- Si b divise a, tous les diviseurs de b divisent aussi a : D(b)D(a) et ainsi D(b) estlensemble des diviseurs communs a et b. b tant le plus grand lment de D(b),b = PGCD(a,b).- Si b = PGCD(a,b), b est en particulier un diviseur de a.

Finalement b divise a si et seulement si b= PGCD(a,b).Dans le cas o b divise a, D(b) =D(a, b).

3 Lemme dEuclide ( Lemme : Prliminaire un thorme qui va suivre)nonca et b tant des entiers naturels non nuls, soit rle reste de la division euclidienne de a par b.

Si r= 0, b divise a et dans ce cas : D(a, b)= D(b) et b=PGCD(a,b).

Si r 0, b ne divise pas a et dans ce cas : D(a, b)= D(b, r) et PGCD(a, b) = PGCD(b, r).

Dmonstration

Dans le cas o r=0 : b divise a. On a dj vu que D(b) =D(a, b) et b = PGCD(a,b).

On crit la division euclidienne de a par b : a=bq+r: q et rsont des entiers et 0


2/11

1) Soit dun diviseur de a et b : dest aussi un diviseur de a + (-q)b=ret ainsi dest aussi undiviseur de b et r.

2) Soit dun diviseur de b et r: dest aussi un diviseur de bq+r=a et ainsi dest aussi undiviseur de a et b.

Finalement les diviseurs de a et b sont les mmes que les diviseurs de b et r: D(a, b)= D(b, r).Alors les plus grands lments de ces ensembles sont les mmes : PGCD(a, b) = PGCD(b, r).

Lnonc du lemme a bien t dmontr.


3/11

4 Lalgorithme dEuclide

a et b tant 2 entiers naturels non nuls, pour dterminer PGCD(a, b) on va remplacer (a, b)

par des couples de nombres de plus en plus petits qui ont le mme ensemble de diviseurs

communs et donc le mme PGCD. On utilise lalgorithme dEuclide qui dcoule du lemme

prcdent. Il est dcrit de la manire suivante :

Le problme ne se pose que dans le cas o ab. Pour la suite, on se ramne au cas o a>b.

1re tapeSoit r0 = a et r1= b : r0 > r1.

On a obtenu une suite de 2 entiers naturels non nuls, strictement dcroissante (r0, r1)

tels que PGCD(a, b) = PGCD(r0, r1) et D(a, b) = D(r0, r1).

Processus appliquer (pour passer ltape suivante)

Aprs avoir obtenu une suite de n+1 entiers naturels non nuls,strictement dcroissante

(r0, r1, , rn-1, rn) telle que PGCD(a, b) = PGCD(rn1, rn) et D(a, b) = D(rn1, rn) :On fait la division euclidienne de rn1 par rn , soit rn+1 le reste de cette division euclidienne.

On a la double ingalit 0rn+1


4/11

6. Exemples de calcul du PGCD par lalgorithme dEuclide

Avec lalgorithme dEuclide, calculer le PGCD des entiers a= 6364 et b = 8214.

Rsolution

Lalgorithme dEuclide est donn par le tableau suivant :

Numro nde ltape

de calcul

rn-1 rn rn+1, le reste de la division dern-1 par rn:rn+1 = rn-1rnE(rn1/rn)

1 8214 6364 18502 6364 1850 814

3 1850 814 222

4 814 222 148

5 222 148 74

6 148 74 0

Donc PGCD(6364, 8214) = 74.

1 En utilisant lalgorithme dEuclide, calculer le PGCD des entiers a= 8619 et b= 16167.

2 En dduire les diviseurs entiers naturels communs a et b

Rsolution

1 Lalgorithme dEuclide est donn par le tableau suivant :

Numro n

de ltape

de calcul

rn-1 rnrn+1, le reste de la division de

rn-1 par rn :rn+1 = rn-1rnE(rn1/rn)

1 8619 16167 8619

2 16167 8619 75483 8619 7548 1071

4 7548 1071 51

5 1071 51 0

Donc PGCD(8619, 16167)=51.

2 Les diviseurs entiers naturels communs a et b sont tous les diviseurs entiers naturels de

51. Il sagit des 4 nombres 51, 17, 3 et 1.

1 Avec lalgorithme dEuclide, calculer le PGCD des entiers a=17193 et b = 16302.

2 Trouver tous les entiers n tels que 7 et 8 soient respectivement les reste de la division

euclidienne de 17 200 et de 16 310 par n.Rsolution

1 Lalgorithme dEuclide est donn par le tableau suivant :

Numro n

de ltape

de calcul

rn-1 rn rn+1, le reste de la division dern-1 par rn :

rn+1 = rn-1rnE(rn1/rn)

1 17193 16302 891

2 16302 891 264

3 891 264 99

4 264 99 66

5 99 66 33

6 66 33 0Donc PGCD(17193, 16302) = 33.


5/11

27 et 8 sont respectivement les reste de la division euclidienne de 17 200 et de 16 310 par n

si et seulement si on peut crire

17 200 = nq+ 7 et 16 310 = nq+8 avec q, qentiers et avec 7


6/11

Proprits du PGCD Entiers premiers entre eux

1 Proprit de la multiplication

noncSoit a, b 2 entiers non nuls et kun entiers naturel non nul, PGCD(ka, kb) = kPGCD (a, b).

Dmonstration : Soit = PGCD (a, b) et= PGCD(ka, kb) ; et sont 2 entiers naturelsnon nuls.

k, divisant les 2 entiers ka et kb, divise aussi = PGCD(ka, kb). Soit dans* tel que =k.On va comparer et

Comme= PGCD(ka, kb), =kdivise les 2 entiers naturels ka et kb o kest un entier nonnul, donc divise aussi les entiers a et b ; comme = PGCD (a, b), .Comme = PGCD (a, b), divisechacun des 2 entiers non nuls a et bdonc lentiernaturel non nul kdivise chacun des 2 entiers ka et kb ; comme= PGCD(ka, kb),k=k. Comme 0


7/11

3 Quelques applications

Trouver 2 entiers naturels non nuls a et b tels que PGCD(a, b) =5 et a+b= 20.

Rsolution

a) Si a et b sont 2 entiers tels que PGCD(a, b) =5 et a+b= 20 :

On peut crire a=5aet b= 5bo aet bsont deux entiers naturels non nuls premiers entre

eux et ainsi 20= 5a+ 5bdo a+b= 4.

Les entiers naturels non nuls aet bne peuvent que se trouver dans { 1 ; 2 ; 3 ; 4}.

Avec aet bentiers naturels non nuls premiers entre eux, il ne reste que les 2 possibilits

suivantes :

(a=1 et b=3) et (a=3 et b=1) qui donnent (a=5 et b=15) et (a=15 et b=5)

b) Rciproquement si a=5 et b=15 ou si a=15 et b=5 :

1 et 3 sont premiers entre eux, 1= PGCD (1 ;3) do 5= 5PGCD (1 ; 3)= PGCD(5 ; 15).

On a bien 5= PGCD(a ; b) et a+b = 20.Conclusion

Les couples dentiers naturels cherchs sont (5 ; 15) et (15 ; 5).

Avec n entier naturel non nul et distinct de 1, calculer PGCD (n (n+1) ; (n1)(n+2)).

Rsolution n (n+1) et (n1)(n+2)) sont 2 entiers non nuls.

n (n+1)=n2

+ n et (n1)(n+2)= n2

+ n2 et ainsi : (n1)(n+2) = n (n+1) + 2.

Comme pour le Lemme dEuclide d = PGCD ((n1)(n+2), n (n+1))= PGCD (n (n+1), 2) ; d

tant un diviseur entier naturel non nul de 2, d=1 ou d= 2.

n ou n +1 est pair alors n(n+1) et pair et 2 est alors un diviseur de n (n+1). 2 est bien un

diviseur commun n (n+1) et 2 ; par dfinition de PGCD(n (n+1), 2) = d, on a 2d.

Il ne reste que la possibilit 2 = d, soit 2= PGCD (n (n+1) ; (n1)(n+2)).

Soit n entier et les 2 entiers non nulsAn = 5n2 etBn =2n +3.

1 Calculer Cn =An2Bn puisBn2Cn.

2 En dduire les diffrentes valeurs possibles de PGCD (An,Bn).

3 Dterminer lensemble des entiers naturels n tels que PGCD (An,Bn) = 19.

Rsolution

D(a, b) dsigne lensemble des diviseurs communs aux 2 entiers a et b.

Soit d= PGCD (An,Bn) ; dest le plus grand lment de D(An,Bn).

1 Cn = 5n22 (2n+3) do Cn = n8.Bn2Cn = 2n +32(n8) doBn2Cn = 19.

2 On a les galitsAn = 2Bn + Cn etBn = 2Cn +19 .

On applique le lemme dEuclide deux fois pour affirmer que :

D(An,Bn) = D (Bn, Cn) = D( Cn, 19) o Cn = n8.

d D(An,Bn) do d D( Cn, 19). dest ainsi un diviseur de 19, entier naturel. Alors d=1 ou

d=19.


8/11

3 On a affaire 2 cas.

1er

cas : n est congru 8 modulo 19 . 19 divise Cn = n8.

19 est ainsi un diviseur commun Cn et 19 et ainsi 19 D(Cn, 19) soit 19 D(Bn,An).

Alors 19d. Comme d {1 ; 19}, on ne peut quavoird= 19.

2me

cas : nnest pas congru 8 modulo 19 . 19 ne divise pas Cn=n8.

19 D(n8, 19) soit 19 D(Bn,An) do 19 d.

Comme d {1 ; 19}, il ne reste que d= 1. Dans ce cas 1= PGCD (An,Bn).________________________________

Finalement 19 =PGCD (An ;Bn) si et seulement si n 8 modulo 19.

Les entiers 8 + 19k, o kest un entier relatif, sont tous les entiers n tels que :

19 =PGCD (An ;Bn).

Avec nentier naturel non nul, dterminer, suivant les valeurs de lentiern, le PGCD de

15n2

et n(3n+1).

Rsolution

PGCD(15n2; n(3n+1)) = PGCD(n 15n

; n(3n+1))= n PGCD(15n

; 3n+1).

On est ramen la recherche de PGCD(15n; 3n+1).

On pense une division de 15n par 3n+1 en crivant : 15n = 5(3n+1)5 ; comme dans le

Lemme dEuclide on peut prouver que : PGCD(15n; 3n+1)= PGCD(3n +1

; 5).

Soit d= PGCD (3n +1; 5) ; dest dans* un des diviseurs de 5 donc d=1 ou d=5 ; dest

aussi un diviseur de 3n+1.

On cherche quand 3n +1 est divisible par 5.

Soit rle reste de la division euclidienne de n par 5 etR le reste de la division euclidienne de

3r+ 1 par 5.

nrmodulo 5 donne 3n 3rmodulo 5 do 3n +1 3r+ 1 modulo 5 ; cela justifie queR est

aussi le reste de la division euclidienne de 3n +1 par 5.

On a donc le tableau suivant qui prsente toutes les possibilits :

r 0 1 2 3 4

3r+1 1 4 7 10 13

R 1 4 7 0 3

On a affaire lun des 2 cas qui suivent.

1er

cas : nnest pas congru 3 modulo 5.r 3 etR 0 alors 5 ne divise pas 3n + 1, do

d 5.

Il ne reste que 1= d= PGCD(15n; 3n+1) et ainsi PGCD(15n

2; n(3n+1))= nddonne :

PGCD(15n2

; n(3n+1))= n.

2me

cas : n est congru 3 modulo 5. r=3 etR = 0 alors 5 divise 3n+1.

5 est ainsi un diviseur commun 3n+1 et 5 do 5d. Il ne reste que la seule possibilit d= 5 .

PGCD(15n2

; n(3n+1))= nddonne PGCD(15n2

; n(3n+1))= 5n .


9/11

PPCM de 2 entiers

________________

1 Multiples communs 2 entiers

On a dj vu que les multiples dun entiernon nul a sont les mmes que les multiples de

lentier naturel non nul |a|, de plus |a| est un multiple de a dans *

Ainsi les multiples communs de 2 entiers relatifs non nuls a et b sont les multiples communs

des 2 entiers naturels non nuls | a| et |b|. De plus | a| |b| est un multiple commun dans * aux

2 entiers a et b.

Do la dfinition et la remarque suivante :

Lensemble des multiples communs dans * des 2 entiers relatifs non nuls a et b est donc non

vide et admet ainsi dans * un plus petit lment appel le PPCM de a et b. On le notePPCM(a, b).

De plus PPCM(a, b) = PPCM(|a|, |b|).

On se ramne au PPCM de deux entiers naturels non nuls.

2 Proprit multiplicative du PPCM

Thorme

a, b, ktant 3 entiers naturels non nuls, PPCM(ka, kb) = kPPCM(a, b).

Dmonstration

PPCM(a, b) est un multiple dans * de a et b. Alors kPPCM(a, b)est un multiple dans

* de ka et kb.

Soit

Mun multiple dans

* de

kaet

kb.ka

etkb

tant des multiples dek,M

est aussi unmultiple de k. Soit donc Mdans * tel que M=kM.

M=kMest un multiple dans * de ka et kb, comme kest dans *, Mest alors dans * un

multiple de a et b.

Par dfinition du PPCM, PPCM (a, b) Met en multipliant par kpositif, on a :

kPPCM (a, b) kMsoit : kPPCM (a, b) M.

Finalement kPPCM(a, b) est dans * le plus petit des multiples communs ka et kb :

PPCM(ka, kb) = kPPCM(a, b).


10/11

3 Les multiples du PPCM

Soit a et b 2 entiers naturels non nuls. Les multiples de a et b sont les multiples du PPCM de a

et b.

Dmonstration

Soit m = PPCM(a, b). m est un entier naturel non nul.

Soit un multiple de m. a et b divisent m et m divise alors a et b divisent .est ainsi un multiple de a et b.

Rciproquement, soit un multiple de a et b.

On fait la division euclidienne de par m : = mq + ro q et rsont des entiers tels que

0r


11/11

6 Une application

Soient des entiers naturels non nuls a, b et c.

Si a et b divisent c et si a et b sont premiers entre eux, alors ab divise c.

Dmonstration :

Par hypothse c est un multiple de a et b, donc c est un multiple de PPCM(a, b).Comme a et b sont premiers entre eux, PPCM (a, b) = ab et c est alors un multiple de ab.

Finalement ab divise c.

Documents

3 PGCD et PPMC