Cours sur le PGCD et PPCM

Publié par

PGCD - PPCM 1 Plus grand diviseur commun de deux entiers 1.1 DØ?nition - Exemples DØ?nition 1 Soient a et b deux ØlØment deZ. aZ+bZ est un sous-groupe deZ donc il existe 2N tel que aZ+bZ = Z. On appelle le plus grand diviseur commun de a et b et on note = pgcd(a;b) ou = a^b. Exemple 2 On a vu dans le chapitre prØcØdent pgcd(2;3) = 1 et pgcd(10;25) = 5. Remarque 3 Pour tout a et b dansZ, pgcd(a;b) = pgcd(b;a) = pgcd(jaj;jbj). Soient a;b2N alors ajb() pgcd(a;b) = a DØmonstration. Le premier point dØcoule du fait quejaj = aZ. Montrons le second on a ajb() bZ aZ() aZ+bZ = aZ() pgcd (a;b) = a Proposition 4 Soient a et b deux entiers relatifs. Soit 2N. Alors = pgcd(a;b) si et seulement si l?entier divise a et b si d est un diviseur de a et de b alors d divise Cela explique le nom de plus grand diviseur commun pour . DØmonstration. Notons = pgcd(a;b). On a aZ Z donc ja, de mŒme bZ Z donc jb. Donc est un diviseur commun ? a et b. Soit d un diviseur de a et b, alors aZ dZ et bZ dZ donc aZ[bZ dZ donc (par dØ?nition de la somme de deux sous-groupes) aZ+bZ dZ donc Z dZ et donc dj . RØciproquement soit un entier positif vØri?ant : l?entier divise a et b si d est un diviseur de a et de b alors d divise Il faut montrer que = pgcd(a;b). On a aZ Z et bZ Z donc aZ+bZ Z et aZ+bZ = pgcd(a;b)Z donc jpgcd(a;b). D?autre part pgcd(a;b) est un diviseur de a et de b donc par dØ?nition de on a pgcd(a;b)j .
Publié le : jeudi 17 octobre 2013
Lecture(s) : 252
Voir plus Voir moins
Cette publication est accessible gratuitement

1

1.1

Plus grand

PGCD-

PPCM

diviseur commun

Dénition - Exemples

de deux entiers

Dénition 1Soientaetbdeux élément deZ.aZ+bZest un sous-groupe deZdonc il existe2N
tel queaZ+bZ=Z appelle. Onle plus grand diviseur commun deaetbet on note=pgcd(a; b)
ou=a^b.

Exemple 2On a vu dans le chapitre précédent pgcd(2;3) = 1et pgcd(10;25) = 5.

Remarque 3

Pour toutaetbdansZ, pgcd(a; b) =pgcd(b; a) =pgcd(jaj;jbj).

Soienta; b2Nalors

ajb()pgcd(a; b) =a

Démonstration.Le premier point découle du fait quejaj=aZ. Montrons le second on a

ajb()bZaZ()aZ+bZ=aZ()pgcd(a; b) =a

Proposition 4Soientaetb Soitdeux entiers relatifs.2N. Alors=pgcd(a; b)si et seulement
si
snieldtreitesdiviseudnvisieaeutdrbeaet debalorsddivise
Cela explique le nom de plus grand diviseur commun pour.

Démonstration.Notons=pgcd(a; b). On aaZZdoncja, de mêmebZZdoncjb.
Doncest un diviseur commun àaetb.
Soitdun diviseur deaetb, alorsaZdZetbZdZdoncaZ[bZdZdonc (par dénition
de la somme de deux sous-groupes)aZ+bZdZdoncZdZet doncdj.
Réciproquement soitun entier positif vériant :
lentierdiviseaetb
sidest un diviseur deaet debalorsddivise

Il faut montrer que=pgcd(a; b).
On aaZZetbZZdoncaZ+bZZetaZ+bZ=pgcd(a; b)Zdoncjpgcd(a; b).
Dautre partpgcd(a; b)est un diviseur deaet debdonc par dénition deon apgcd(a; b)j.

Exemple 5On a pgcd(4;6) = 2; pgcd(4;7) = 1

pgcd(57;711) = 7
pgcd(312;319) = 312
pgcd(2153852;293207) = 2938

1

1.2

Méthode de calcul : Algorithme dEuclide

Lemme 6Soitaetbdeux entiers naturels non nuls. Soitrle reste de la division euclidienne dea
parb. Alors pgcd(a; b) =pgcd(b; r).

Démonstration.On va montrer que lensemble des diviseurs deaetb:Div(a)\Div(b)et
lensemble des diviseurs debetr:Div(b)\Div(r)sont égaux, ce qui donnera le résultat.
Écrivons la division euclidienne deaparb, donca=bq+ravec0r < b. Comme

r=abq

si un nombreddiviseaetbalorsddiviser. DoncDiv(a)\Div(b)Div(b)\Div(r).
Réciproquement, siddivisebetralorsddivisea=bq+rdoncDiv(b)\Div(r)Div(a)\
Div(b).

Remarque 7Si lon a une expression du typeA=B+CouA+B+C= 0entre trois entiers
A; BetC. Alors tout nombre divisant deux de ces entiers divise automatiquement le troisième.

Proposition 8Algorithme dEuclide. Soitaetb construitdeux entiers naturels non nuls. On
par récurrence une suite dentiers naturels(rn)n2Nde la façon suivante :r0=a,r1=b,r2est le
reste de la division euclidienne der0parr1, et de proche en proche, tant quern6= 0,rn+1est égal
au reste de la division euclidienne dern1parrn. Alors il existe un entierNtel querN6= 0et
rN+1= 0 pgcd. Alors(a; b)est égal au dernier reste non nulrN.

Démonstration.Tant que les restes sont non nuls, on dénit une suite telle que0rn< rn1<
  < r2< r1dtunu.etnobuAroécsaisemcttdenersltsireisranutitedentcdunesunodtigaslI.
nombre ni détapes on obtient alors un reste nul (on aNb utilisant le lemme précédent, on). En
obtient

pgcd(a; b) =pgcd(b; r2) =pgcd(r2; r3) =  =pgcd(rN1; rN) =pgcd(rN;0) =rN

Exemple 9Soienta= 144etb= 84. On calcule

On a donc pgcd(144;84) = 12.

1.3

Relation de Bézout

144 = 184 + 60
84 = 160 + 24
60 = 224 + 12
24 = 212 + 0

r2= 60
r3= 24
r4= 12
r5= 0

Théorème 10Relation de Bézout.
Soientaetb Alorsdeux entiers relatifs. il existe des entiers relatifsuetvtels que

pgcd(a; b) =au+bv

Démonstration.Notons=pgcd(a; b)on a2Z=aZ+bZdonc=x+yoùx2aZet
y2bZ, donc il existeuetvtels que=au+bv.

2

Remarque 11Soit2N venons de montrer que si. Nous=pgcd(a; b)alors il existe un couple
dentiers(u; v)tel que=au+bv. La Par réciproque est fausse dans le cas général. exemple, pour
a= 4,b= 2et= 6, on a6 = 41 + 21et66=pgcd(4;2) = 2. Plus généralement, sil existe un
couple dentiers(u; v)tel qued=au+bvalors pgcd(a; b)divised.

Exemple 12Soienta= 63etb= 37. On calcule

63 = 371 + 26r2= 26
37 = 261 + 11r3= 11
26 = 112 + 4r4= 4
11 = 42 + 3r5= 3
4 = 31 + 1r6= 1

On part de la dernière relation et on remplace les restes en utilisant les formules de bas en haut de
la façon suivante :

1 = 431
1= 4(1142) =11 + 43
1 =11 + (26112)3 =711 + 263
1 =7(37261) + 263 =737 + 2610
1 =737 + (63371)10 =1737 + 1063

Finalement la relation de Bézout est :

10631737 = 1 =pgcd(63;37)

Départ
On a remplacér5
On a remplacér4
On a remplacér3
On a remplacér2

Proposition 13Soientaetb pour tout Alorsdeux entiers relatifs.k2N, pgcd(ka; kb) =kpgcd(a; b).

Démonstration.Sik= 0légalité est vériée. Supposonsk6= 0. SoitD=pgcd(ka; kb)et=
pgcd(a; b). Commediviseaetb,kdivisekaetkbdonckdiviseD.
Par ailleurs,kdivisekaetkbdonckdiviseD. Il existeq2Ztel queD=kq. Commekqdivise
kaetkb,qdiviseaetbdoncqdivise en déduit que. OnDdivisek.
Finalement on a donck=D.

Exemple 14pgcd(42;56) = 7pgcd(6;8) = 72 = 14.

2 Éléments premiers entre eux

Dénition 15On dit que les entiersaetbsont premiers entre eux si et seulement si pgcd(a; b) = 1
(noté aussia^b= 1).

Proposition 16Soientaetbentiers relatifs non tous les deux nuls. Soitdeux un diviseur positif
deaet deb. Il existea02Ztel quea=a0et il existeb02Ztel queb=b0. Alorsest le pgcd de
aetbsi et seulement sia0etb0sont premiers entre eux.

Démonstration.Le diviseur Commeest nécessairement non nul.a=a0etb=b0,

pgcd(a; b) =pgcd(a0; b0) =pgcd(a0; b0)

Par conséquent,pgcd(a; b) =()pgcd(a0; b0) = 1.

Théorème 17Théorème de Bézout.Les entiersaetbsont premiers entre eux si et seulement
sil existe deux entiers relatifsuetvtels que1 =au+bv.

3

Démonstration.Sipgcd(a; b) = 1alors il existe un couple dentiers(u; v)tel que1 =au+bv
(relation de Bézout). Réciproquement, supposons quil existe deux entiersuetvtels que1 =au+bv.
Soitdun diviseur deaet deb. Alorsddivise1doncjdj= 1ùo.Dpgcd(a; b) = 1.

Proposition 18Soitn2N,n2. Soita1; : : : ; andes entiers relatifs. Siaest premier avec chacun
desai(i= 1: : : n)alorsaest premier avec leur produit.

Démonstration.Commepgcd(a; a1) = 1, il existe des entiersu1etv1tels que1 =au1+a1v1.
De même, il existeu2etv2tels que1 =au2+a2v2. En multipliant ces deux termes, on obtient
1 =a(au1u2+u1a2v2+a1v1u2) +a1a2(v1v2)Doù.pgcd(a; a1a2) = 1 propriété est donc. La
vraie pourn= 2.
Supposons la propriété vraie à lordren. Soita1; : : : ; an+1n+ 1entiers premiers séparément avec
a utilisant lhypothèse de récurrence avec. Ena1; : : : ; an, on obtient queaest premier avec le produit
a1  an conclut . Onen utilisant la propriété avec les deux entiersa1  anetan+1.

Exemple 19Comme pgcd(3;5) = 1et pgcd(3;8) = 1, on a pgcd(3;40) = 1.

Corollaire 20Soientaetbdeux entiers relatifs. Siaetbsont premiers entre eux alors pour tout
n2Netp2N,anetbpsont premiers entre eux.

Théorème 21Théorème de Gauss.Soita,betc Sitrois entiers relatifs.adivisebcet siaetb
sont premiers entre eux alorsadivisec.

Démonstration.Commepgcd(a; b) = 1, il existe un couple dentiers(u; v)tels que1 =au+bv.
En multipliant cette égalité parc, on obtientc=a(cu) + (bc)v. Commeadivisebc,adivisec.

Proposition 22Soitn2N,n2. Soita1; : : : ; andes entiers relatifs premiers entre eux deux à
deux. Siaest divisible par chacun desai(i= 1: : : n)alorsaest divisible par leur produit.

Démonstration.La démonstration se fait par récurrence surn. Pourn= 2, il existe deux
entiersq1etq2tels quea=a1q1=a2q2. Donca2divisea1q1 comme. Maispgcd(a2; a1) = 1, on
obtient quea2diviseq1. Il existe doncq32Ztel queq1=a2q3. Par conséquent,a=a1a2q3eta1a2
divisea. La n de la démonstration se fait sans di¢ culté.

Exemple 23Lentier90est divisible par3et par5qui sont premiers entre eux donc est divisible
par15.
Mais bien que20soit divisible par4et par10il nest pas divisible par40(car4et10ne sont pas
premiers entre eux).

Proposition 24Soit_x2Z=nZon a

x_inversible

()x^n= 1

_ _
Démonstration._xest inversible ssi9y_tel que_xy_ = 1ssi9y; ktels quexy += 1knssi
9y; ktels quexykn= 1ssix^n= 1:

Proposition 25Soitla fonction indicatrice dEuler,(n)est égal au nombre de nombres entiers
positifs inférieurs ànet premiers avecn.
En particulier sipest un nombre premier(p) =p1.

4

3

Plus petit multiple commun de deux entiers

Dénition 26Soientaetb2Z, il existe2Ntel queaZ\bZ=Z.
est appelé le plus petit multiple commun dea; b, noté ppcm(a; b)(oua_b).

Exemple 27On a vu dans le chapitre précédent ppcm(2;3) = 6et ppcm(10;25) = 50.

Remarque 28ppcm(0;0) = 0.

Pour touta2Z, on a ppcm(a;0) = 0

Pour toutaetbdansZ, ppcm(a; b) =ppcm(b; a) =ppcm(jaj;jbj).

Soienta; b2Nalors

ajb()ppcm(a; b) =b

Démonstration.On montre le dernier point. On a

Proposition 29
si

ajb()bZaZ()aZ\bZ=bZ()ppcm(a; b) =b

Soientaetb Soitdeux entiers relatifs.2N. Alors=ppcm(a; b)si et seulement
lentierest un multiple deaetb
simest un multiple deaet debalorsdivisem

Cela explique le nom de plus petit multiple commun pour.

Démonstration.Notons=ppcm(a; b). On aZaZdoncaj, de mêmeZbZdoncbj.
Doncest un multiple deaetb.
Soitmun multiple deaetb, alorsmZaZetmZbZdoncmZaZ\bZdoncmZZ
doncjm.
Réciproquement soitun entier positif vériant :

lsienmtieretseledtlpinuumiplemulteunstadeteateedbbalorsdivisem

Il faut montrer que=ppcm(a; b).
On aZaZetZbZdoncZaZ\bZ=ppcm(a; b)Zdoncppcm(a; b)j.
Dautre partppcm(a; b)est un multiple deaet debdonc par dénition deon ajppcm(a; b).

Exemple 30

On a ppcm(4;6) = 12; ppcm(4;7) = 28

ppcm(57;711) = 5711

pgcd(312;319) = 319

pgcd(2153852;293207) = 215320527

Proposition 31

Soientaetbdeux entiers naturels, on a la relation :

pgcd(a; b)ppcm(a; b) =ab

5

Démonstration.Notons=ppcm(a; b)et=pgcd(a; b). Il existea0etb0tel quea=a0et
b=b0On va montrer que=a0b0le résultat en découle immédiatement en multipliant par:
a0b0est un multiple deaet debdonc par dénitiondivisea0b0
.
Réciproquement notonsuetvles entiers tels que=au=bvdonc

et donc

=a0u=b0v

a0u=b0v

doncb0divisea0uora0etb0sont premiers entre eux donc daprès le théorème de Gaussb0diviseu
donc il existeqtel queu=b0qet donc en remplaçant ci dessus

et doncdivisea0b0.

et

Exemple 32Poura= 4
pgcd(4;6)ppcm(4;6) = 24.

b

=a0b0q

= 6ppcm(4;6) = 12.

Par ailleurs, pgcd(4;6) =

Corollaire 33Soitaetbdeux entiers relatifs. Alors pour tout
ppcm(a; b).

Démonstration.la formule précédente donne

pgcd(ka; kb)ppcm(ka; kb) =ka:kb

commepgcd(ka; kb) =kpgcd(a; b)on obtient

4

k

ppcm(ka; kb) =pgckda(bb;a=)kppcm(a; b)

2.

On

2N, ppcm(ka; kb)

Plus grand diviseur commun et plus petit
mun denentiers

multiple

a

=

bien

k

com-

Dénition 34Soitn2N,n3 dénit le plus grand diviseur commun de. Ona1; : : : ; anpar
récurrence surngrâce à la formule suivante :

pgcd(a1; : : : ; an) =pgcd(pgcd(a1; : : : ; an1); an))

Dénition 35Soitn2N,n3. On dénit le plus petit multiple commun dea1; : : : ; anpar
récurrence surngrâce à la formule suivante :

Exemple 36

ppcm(a1; : : : ; an) =ppcm(ppcm(a1; : : : ; an1); an))

pgcd(30;15;12) = 3;pgcd(300;10;60;3) = 1

ppcm(30;15;12) = 60;ppcm(300;10;60;3) = 300

Remarque 37pour calculer le
lordre que lon veut.

pgcd ou le ppcm de plusieurs

6

nombres,

on peut

les

prendre dans

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Lisez à volonté, où que vous soyez
1 mois offert, sans engagement Plus d'infos

Diffusez cette publication

Vous aimerez aussi