PGCD et PPCM - frignanese.free.frfrignanese.free.fr/pages/tsspe/Arithmetique/pgcd.pdf · pgcd et ppcm Lycée Marie Curie de Tarbes 1 PGCD 1.1 Définitions Soient a et b deux entiers

PGCD et PPCM

Table des matieres

1 PGCD 2

1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Proprietes ROC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3.1 Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 Theoreme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Nombres premiers entre eux 4

2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Theoreme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.3 Theoreme de Gauss ROC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.4 Corollaire du theoreme de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.5 Theoreme de Bezout ROC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.6 Corollaire du theoreme de Bezout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 PPCM 5

3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3.2 Theoreme : produit du pgcd et ppcm ROC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Applications 6

4.1 Methode des soustractions successives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4.2 Calcul du pgcd par l’algorithme de l’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.3 Application du theoreme de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.4 Application du theoreme de Bezout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.5 Equation diophantienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1

pgcd et ppcm Lycee Marie Curie de Tarbes

1 PGCD

1.1 Definitions

Soient a et b deux entiers naturels.

• On note D(a) l’ensemble des diviseurs de a ; et D(b) celui de b.

• On note D(a; b) l’ensemble des diviseurs communs a a et a b .

• D(a; b) est un ensemble non vide et fini.

Etant fini, il est borne par son plus petit element qui est 1, et par le plus grand de a et b.

Ce plus grand element est nomme PGCD de a et de b . Il est aussi note pgcd (a; b) ou a ∧ b.

Exemple 1

D(28) = {1; 2; 4; 7; 14; 28} , D(24) = {1; 2; 3; 4; 6; 8; 12; 24} , pgcd (28; 24) = 4

1.2 Proprietes ROC

1. Si b divise a alors pgcd(a; b) = b.

2. Soit r est le reste de la division de a par b. On a D(a; b) = D(b; r), et donc pgcd (a; b) = pgcd (b; r).

3. D(a; 0) = D(a).

Demonstration 1

1. Si b divise a alors b est un diviseur commun a a et b. De plus b est le plus grand diviseur de b. C’est donc le

pgcd de a et b.

2. • On ecrit a = bq + r et donc r = a− bq.

Ainsi tout diviseur de a et de b est un diviseur de r et donc de b et de r . Soit D(a; b) ⊂ D(b; r).

• Reciproquement : si a = bq + r , tout diviseur de b et de r , est un diviseur de a et donc de a et de b .

Soit D(b; r) ⊂ D(a; b).

• La double inclusion D(a; b) ⊂ D(r) et D(b; r) ⊂ D(a; b) nous permet de dire que D(a; b) = D(b; r)

3. Tout nombre non nul divise 0. Et donc les diviseurs commun a 0 et a seront les diviseurs de a.

1.3 Algorithme d’Euclide

1.3.1 Methode

Soit a et b deux entiers naturels tels que a > b et r0 le reste de la division de a par b.

– a = b q0 + r0

Si r0 = 0 alors b divise a et donc pgcd (a; b) = b

Si r0 6= 0 alors on calcule r1 le reste de la division de b par r0.

– b = r0 q1 + r1

Si r1 = 0 alors r0 divise b et donc pgcd (a; b) = pgcd (b; r0) = r0

Si r1 6= 0 alors on calcule r2 le reste de la division de r0 par r1.

Arithmetique 5 Page 2 Francis Rignanese


– r0 = r1 q2 + r2

Si r2 = 0 alors r1 divise r2 et donc pgcd (a; b) = pgcd (b; r0) = pgcd (r0; r1) = r1

Si r2 6= 0 alors on calcule r3 le reste de la division de r2 par r1

..etc, jusqu’au dernier reste non nul et donc le reste precedent rn est le pgcd (a; b).

1.3.2 Algorithme

DEBUT

Lire A,B, (A > B)

R←− Reste(A/B)

Tant que R 6= 0 faire

A←− B : B ←− R

FTQ

Ecrire ”Le PGCD de ” A ”et” B ”est” R

FIN

Exemple 2

pgcd(936; 164)

936 = 164× 5 + 116 pgcd(936; 164) = pgcd(164; 116)

164 = 116× 1 + 48; pgcd(164; 116) = pgce(116; 48)

116 = 48× 2 + 20; pgcd(116; 48) = pgcd(48; 20)

48 = 20× 2 + 8; pgcd(48; 20) = pgcd(20; 8)

20 = 8× 2 + 4; pgcd(20; 8) = pgcd(8; 4)

8 = 4× 2 + 0; pgcd(8; 4) = 4

Donc pgcd(936; 164) = 4

1.4 Theoreme

Soit g le pgcd de deux entiers naturels a et b.

1. L’ensemble des diviseurs commun a a et b est egal a l’ensemble des diviseurs de leur pgcd g.

Autrement dit : D(a; b) = D(g).

2. Si l’on multiplie a et b par un entier naturel k, leur pgcd est multiplie par k.

Autrement dit pgcd (ka; kb) = k × pgcd (a; b).

3. Si d est un diviseur commun a a et b alors pgcd

(

a

d;b

d

)

=g

d.

Demonstration 2

1. Dans les restes successifs de l’algorithme d’Euclide on a vu que

D(a; b) = D(b; r0) = ...... = D(rn; 0) = D(rn), et rn = g.

2. Si a = bq0 + r0, alors ka = kbq + kr0 et ceci tout le long de l’algorithme d’Euclide ( kb = kr0 q1 + kr1,

kr0 = kr1q2 + kr2.....) . D’ou le dernier reste non nul qui est le pgcd sera aussi multiplie par k.

3. Si d est un diviseur commun a et b ,c’est aussi un diviseur de leur pgcd g.

On pose a = a′d et b = b′d . On a alors pgcd (a; b) = pgcd (a′d; b′d) = d× pgcd (a′; b′)

Et donc pgcd (a′; b′) =pgcd(a; b)

d, ou encore pgcd

(

a

d;b

d

)

=g

d.



2 Nombres premiers entre eux

2.1 Definitions

1. Deux entiers naturels non nuls sont dits premiers entre eux lorsque leur pgcd est 1.

Autrement dit 1 est le seul diviseur commun deux nombres premiers entre eux.

2. Une fractiona

best irreductible lorsque a et b sont premiers entre eux.

2.2 Theoreme

g = pgcd(a; b) equivaut aa

get

b

gsont premiers entre eux.

Autement dit g = pgcd(a; b) equivaut a dire qu’il existe deux entiers a′ et b′ premiers entre eux tels que a = a′g et

b = b′g.

Demonstration 3

– Montrons que si g = pgcd (a; b) alorsa

get

b


Nous avons pgcd

(

a

g;b

g

)

=pgcd (a; b)

g=

g

g= 1 . Donc

a

get

b


– Montrons que sia

get

b

gsont premiers entre eux alors g = pgcd(a; b).

Nous avons pgcd

(

a

g;b

g

)

= 1 d’oupgcd(a; b)

g= 1 et donc pgcd(a; b) = g.

2.3 Theoreme de Gauss ROC

Si un entier naturel divise un produit de deux facteurs et s’il est premier avec l’un d’eux, alors il divise l’autre.

Autrement dit si a divise bc et si a est premier avec b alors il divise c.

Demonstration 4

Si a et b sont premiers entre eux alors pgcd (a; b) = 1 et pgcd(ac; bc) = c.

De plus si a divise bc , a divisant aussi ac, c’est un diviseur commun ac et bc, c’est donc un diviseur de leur

pgcd donc de c . (On rappelle que l’ensemble des diviseurs communs deux entiers naturels coıncide avec l’ensemble

des diviseurs de leur pgcd).

2.4 Corollaire du theoreme de Gauss

Si a et b premiers entre eux divise c alors ab divise c.

Demonstration 5

Si a divise c alors nous pouvons ecrire que c = ac′ .

Et si b divise aussi c ou ac′ tout en etant premier avec a alors d’apres le theoreme de Gauss il divise c′ .

On a donc c′ = bc′′.

Finalement on obtient c = ac′ = abc′′ et donc ab divise c.



2.5 Theoreme de Bezout ROC

Les entiers naturels a et b sont premiers entre eux, si et seulement si il existe deux entiers relatifs u et v tels

que

a u+ b v = 1

.

Demonstration 6

– Montrons que s’il existent deux entiers relatifs u et v tels que a u+ b v = 1 alors a et b sont

premiers entre eux.

Le pgcd de a et b divise a u + b v donc divise 1. Ce pgcd est donc 1 ou encore a et b sont premiers

entre eux.

– Montrons, que si a et b sont premiers entre eux alors il existe deux entiers relatifs u et v

tels que a u+ b v = 1.

On note E l’ensemble des entiers a u + b v ou u et v sont des elements de Z . Cet ensemble contient des

elements strictement positifs puisque a = a× 1 + b× 0 est un element de E.

Notons m = a u1 + b v1 le plus petit d’entre eux et divisons a par m.

On ecrit a = mq + r avec 0 ≤ r < m ou a = (a u1 + b v1)q + r avec 0 ≤ r < au1 + b v1.

Mais si a = (a u1 + b v1)q + r alors a = a u1q + bv1q + r ou a− a u1q − bv1q = r .

On obtient a(1− u1q) + b(−v1q) = r . Donc r est un element de E.

Mais si r , element de E verifiant 0 ≤ r < au1 + b v1 , est non nul alors il est plus petit que a u1 + b v1 ce

qui est contradictoire.

Donc r = 0 . Autrement dit m divise a .

De la meme maniere on montrerait que m divise b.

Ainsi m est un diviseur commun a et b qui sont premiers entre eux. D’ou m = 1.

2.6 Corollaire du theoreme de Bezout

g est le pgcd (a; b) signifie qu’il existe un couple d’entiers relatifs (u; v) tel que a u+ b v = g.

Demonstration 7

On sait quea

get

b

gsont premiers entre eux. Et donc d’apres le theoerme de Bezout il existe un couple d’entiers

relatifs (u; v) tel quea

gu+

b

gv = 1.

Autrement dit il existe un couple d’entiers relatifs (u; v) tel que a u+ b v = g.

3 PPCM

3.1 Definitions

Soit a et b deux entiers naturels non nuls.

• On note M(a) l’ensemble des multiples de a strictement positifs et M(b) ceux de b.

Les elements communs ces deux ensembles constitue un ensemble note M(a; b) , ensemble des multiples communs



a et b.

Cet ensemble est non vide car il contient ab et tous ses multiples.

• Le plus petit element de M(a; b) est le plus petit commun multiple de a et de b . Il est not ppcm (a; b) ou a∨ b.

3.2 Theoreme : produit du pgcd et ppcm ROC

Soit a et b deux entiers naturels non nuls.

On a pgcd (a; b)× ppcm(a; b) = a× b.

Si l’on note g = pgcd (a; b) et m = ppcm (a; b) . On a alors a× b = m× g .

Demonstration 8

– On sait qu’il existe deux entiers, a′ et b′, premiers entre eux tels que a = a′g et b = b′g

– m est un multiple commun a a et b. On sait alors qu’il existe deux entiers p et q tels que m = pa et

m = qb.

On a alors pa = qb ou bien pa′g = qb′g . Autrement dit pa′ = qb′.

– Si pa′ = qb′ alors a′ divise qb′ tout en etant premier avec b′ .

Et donc d’apres le theoreme de Gauss a′ divise q . D’ou il existe un entier k tel que q = ka′.

Ainsi l’egalite pa′ = qb′ donne pa′ = ka′b′ . D’ou p = kb′.

– Nous avons donc m = pa′g = qb′g soit m = kb′a′g = ka′b′g.

Nous avons montre que si m est un multiple commun a et b il est multiple de a′b′g.

– Montrons aussi que tout multiple de a′b′g est un multiple commun a et b.

Un multiple de a′b′g est un multiple de (a′g)b′ = ab′ab′ donc multiple de a.

De meme un multiple de a′b′g est un multiple de a′(b′g) = a′b donc multiple de b.

D’ou tout multiple de a′b′g est un multiple commun a et b .

– Nous avons montre que l’ensemble des multiples communs a et b est egal a l’ensemble des multiples de a′b′g .

Le plus petit element du premier ensemble est m et celui du second est a′b′g.

On a donc m = a′b′g . D’ou m× g = (a′ × g)× (b′ × g) . Ou bien m× g = a× b.

4 Applications

4.1 Methode des soustractions successives

1. Soit a et b deux entiers naturels tels que a ≥ b.

Montrons que l’ensemble des diviseurs communs a et b est egal a l’ensemble des diviseurs communs

a a et a− b.

2. Appliquez successivement ce resultat pour determiner les diviseurs communs a 168 et 264.

1. On doit montrer une double inclusion : D(a; b) ⊂ D(a− b; b) et D(a− b; b) ⊂ D(a; b).

Pour montrer la premiere inclusion on montre qu’un element quelconque deD(a; b) est aussi element deD(a−b; b).

– Soit d un diviseur commun a et b. Alors d divise a− b et donc a et a− b.

D’ou D(a; b) ⊂ D(a− b; b)



– Soit d un diviseur commun a et a− b. Alors d divise la somme , soit b et donc d divise a et b.

D’ou D(a− b; b) ⊂ D(a; b)

– Conclusion D(a− b; b) = D(a; b)

2. Nous deduisons du resultat precedent que

D(264; 168) = D(168; 96) = D(96; 72) = D(72; 24) = D(48; 24) = D(24; 24) = D(24).

Donc D(264; 168) = {1; 2; 3; 4; 6; 8; 12; 24}.

4.2 Calcul du pgcd par l’algorithme de l’Euclide

Dterminer le pgcd de 138807 et 52089.

138807 = 52089× 2 + 34629, pgcd(13807; 52089) = pgcd(52089; 34629)

52089 = 34629× 1 + 17460, pgcd(52089; 34629) = pgcd(34629; 17460)

34629 = 17460× 1 + 17169, pgcd(34629; 17460) = pgcd(17460; 17169)

17460 = 17169× 1 + 291, pgcd(17460; 17169) = pgcd(17169; 291)

17169 = 291× 59 + 0, pgcd(17169; 291) = 291

Conclusion pgcd(13807; 52089) = 291 dernier reste non nul.

4.3 Application du theoreme de Gauss

Determiner les couples d’entiers (x; y) solutions de l’equation : 55x = 16y.

55 = 16× 4 + 7; 16 = 7× 2 + 4; 7 = 2× 3 + 1

pgcd(55; 16) = pgcd(16; 7) = pgcd(7; 2) = pgcd(2; 1) = 1. Donc 55 et 16 sont premiers entre eux.

D’autre part, si 55x = 16y alors 16 divise 55x et etant premier avec 55 il divise x, d’apres le theoreme de Gauss.

Donc x = 16k.

Si on remplace dans 55x = 16y on obtient 55× 16k = 16y. Autrement dit y = 55k.

Les couples solutions sont donc (16k; 55k) ou k ∈ Z.

4.4 Application du theoreme de Bezout

Dmontrez que pour tout entier naturel n, les nombres a = 2n + 1 et b = 3n+ 2 sont premiers entre

eux.

On cherche deux entiers u et v tels que a u+ b v = 1.

On a : −3(2n+ 1) + 2(3n+ 2) = −6n− 3 + 6n+ 4 = 1. Donc a et b sont premiers entre eux.

4.5 Equation diophantienne

Resoudre dans Z× Z l’equation 62 x+ 43 y = 3

1. On trouve une solution particuliere de l’equation 62 x+43 y = 1 en utilisant l’algorithme d’Euclide. (Il est vident

que 62 et 43 doivent etre premiers entre eux)



(1) 62 = 43× 1 + 19

(2) 43 = 19× 2 + 5

(3) 19 = 5× 3 + 4

(4) 5 = 4× 1 + 1

En remontant on obtient :

(4)⇔ 5− 4 = 1

(3)⇔ 4 = 19− 5× 3 ; 5− 4 = 1⇔ 5− (19− 5× 3)× 1 = 1⇔ −19 + 5× 4 = 1

(2)⇔ 5 = 43− 19× 2 ; −19 + 5× 4 = 1⇔ −19 + (43− 19× 2)× 4 = 1⇔ −9× 19 + 43× 4 = 1

(1)⇔ 19 = 62− 43 ; −9× 19 + 43× 4 = 1⇔ −9(62− 43) + 43× 4 = 1⇔ −9× 62 + 13× 43 = 1

Une solution particuliere de l’equation 62 x+ 43 y = 1 est (−9; 13)

2. Une solution particuliere de l’equation 62 x+ 43 y = 3 est (−27; 39)

3. Recherche des solutions de 62 x+ 43 y = 3

On a

62 x+ 43 y = 3

62× (−27) + 43× 39 = 3

Par soustraction on obtient 62(x+ 27) + 43(y − 39) = 0 ou encore 62(x+ 27) = 43(39− y)

Ainsi 43 divise 62(x+ 27) tout en tant premier avec 62. D’ou d’apres le theoreme de Gauss il divise x+ 27

Et donc x+ 27 = 43k, k ∈ Z, ou x = −27 + 43k.

Si on remplace dans 62(x+ 27) = 43(39− y), x+ 27 par 43k on obtient 62× 43k = 43(39− y).

Autrement dit 62k = 39− y ou y = 39− 62k.

4. L’ensemble des solutions de l’equation 62 x+ 43 y = 1 est S = {(−27 + 43k ; 39− 62k); k ∈ Z}.


Documents

PGCD et PPCM - frignanese.free.frfrignanese.free.fr/pages/tsspe/Arithmetique/pgcd.pdf · pgcd et ppcm Lycée Marie Curie de Tarbes 1 PGCD 1.1 Définitions Soient a et b deux entiers