Cours sur le PGCD et PPCM

Description

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 .

Sujets

• Plus petit commun multiple
• Plus grand commun diviseur
• cours de math

Informations

• Publié par: Oliv94
• Publié le: 17 octobre 2013
• Nombre de lectures: 318
• Langue: Français

Extrait

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 quea2diviseq