La lecture à portée de main
2
pages
Français
Documents
2013
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
2
pages
Français
Ebook
2013
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Cours S ale eTnimr e tPPMCDCGP
1. Plus grand commun diviseur
1.1 Diviseurs communs à deux entiers positifs
Pour tout entier natureln, on note D(n) l'ensemble des diviseurs den.
On note D(a;b) l'ensemble des diviseurs communs àaetb, c'est-à-dire D(a;b) = D(a)D(b).
Le plus grand élément de D(a;b) est appelé PGCD deaetb, noté PGCD(a;b).
Exemple: Le PGCD de 24 et 36 est 12; celui de 25 et 12 est 1.
Propriétés:
Pour tout entier natureln, D(n; 0) = D(n). En effet, D(n; 0) = D(n) = D(n).
PGCD(a;b) a et PGCD(a;b) b. En effet, les diviseurs deasont inférieurs àa, de même pourb.
Sibdivisea, alors PGCD(a;b) =b. En effet, Sibdivisea, b D(a;b).
PGCD(a;b) = PGCD(b;a).
PGCD(a; 1) = 1.
PGCD(a;a) =a.
Pour toutkentier naturel non nul, PGCD(ka;kb) =k ×PGCD(a;b). Démonstration à l'aide de l'algorithme
d'Euclide, vu juste après.
1.2 Recherche du PGCD : Algorithme d'Euclide:
a) Propriété: Soita=bq + rla division euclidienne deaparb. Alors D(a;b) = D(b;r) .
Sir= 0, alors PGCD(a;b) =b.
Sir 0, alors PGCD(a;b) = PGCD(b;r).
Démonstration: Soitcun diviseur commun deaet deb. Il existe deux entiersa'etb'tels quea = ca'etb = cb'.
Sia = bq + rest la division euclidienne deaparb, alorsr=a – bq = ca' – cb'q = c(a' – b'q), etcdiviser, donc
est un diviseur commun debet der. Ainsi D(a;b)D(b;r).
Réciproquement, soitdun diviseur commun debet der. Il existe deux entiersb'etr'tels queb = db'etr = dr'.
Sia = bq + rest la division euclidienne deaparb, alorsa=db'q + dr' = d(b'q + r'), etddivisea, donc est un
diviseur commun deaet deb. Ainsi D(b;r)D(a;b).
Finalement, D(a;b) = D(b;r), et PGCD(a;b) = PGCD(b;r).
b) Algorithme d'Euclide:
Pour rechercher le PGCD deaet deb, on effectue les divisions euclidiennes successives :
a=bq + ravec 0 r<b; puisb=rq1+ r1avec 0 r1<r; puisr=r1q2+ r2avec 0 r2<r1; etc... jusqu'à ce
que le reste soit nul. Alors le PGCD deaet debest le dernier reste non nul.
Exemple: On cherche PGCD(48; 63) : On a successivement :
63 = 148 + 15, puis 48 = 315 + 3, puis 15 = 53 + 0. Donc PGCD(48; 63) = 3.
c) Propriété: D(a;b) = D(g) oùgest le PGCD deaet deb.
2. Nombres premiers entre eux
Définition: Soientaetbdeux entiers naturels non nuls.
On dit queaetbsont premiers entre eux si PGCD(a;b) = 1.
Propriété: Soitaun entier naturel non nul. Sipest un nombre premier qui ne divise pasa, alorsaetpsont
premiers entre eux.
a b
Soientaetbdeux entiers naturels non nuls etdleur PGCD. Alorsdetdsont premiers entre eux.
3. Théorème de Bezout :
Théorème: Soientaetbdeux entiers relatifs non nuls.
aetbsont premiers entre eux si et seulement si il existe des entiers relatifsuetvtels queau + bv= 1.
Démonstration: Supposonsaetbsont premiers entre eux; considérons l'ensemble E des nombresau + bvavecu
etventiers relatifs. E contient des entiers naturels non nuls : sial'est, E contienta=a×1 +b×0. siaest négatif,
E contient –a=a×(–1) +b×Donc E contient un plus petit entier naturel0. m=au1+ bv1. Montrons quem
diviseaetb: La division deaparmdonnea = mq + r= (au1+ bv1)q+r, avec 0 r<m.
Orr= (au1+ bv1) aq – a =(u1q –1) +b(v1q) de la formeau + bv.om C memest le plus petit entier naturel de la
formeau + bv, alorsr= 0. Doncmdivisea. De la même manière,mdiviseb. Oraetbsont premiers entre eux,
doncm= 1.
Supposons qu'il existe des entiers relatifsuetvtels queau + bv= 1. Le pgcd(a;b) =gdiviseaetbet tout nombre
de la formeau + bv. Doncg= 1, etaetbsont premiers entre eux.
Corollaire:Soientaetbdeux entiers relatifs etdleur PGCD. Alors il existe des entiers relatifsuetvtels que
au + bv=d.
4. Théorème de Gauss :
Théorème: Soientaetbdeux entiers relatifs non nuls etcun entier relatif. Siadivisebcet siaest premier avec
balorsadivisec.
Démonstration: Commeaetbsont premiers entre eux, il existe des entiers relatifsuetvtels queau + bv= 1
.
Doncauc + bvc c.Oradiviseaucet divisebc, doncadiviseauc + bvc = c.
=
Corollaires:
Si un entier relatifcest divisible par deux entiersaetbpremiers entre eux, alorscest divisible par le produit
ab.
Si un nombre premierpdivise le produitab, alors il divise au moins l'un des facteursaetb.
5. Plus petit commun multiple
2.1 Multiples communs à deux entiers positifs
Pour tout entier natureln, on note M(n) l'ensemble des multiples den. M(n) = {k,k=nqavecq }.
On note M(a;b) l'ensemble des multiples communs àaetb, c'est-à-dire M(a;b) = M(a)M(b).
Le plus petit élément de M(a;b) est appelé PPCM deaetb, noté PPCM(a;b).
Exemplecelui de 25 et 12 est 300.: Le PPCM de 24 et 36 est 72;
2.2 Propriétés : Le PGCD(a;b) divise le PPCM(a;b).
PGCD(a;b)×PPCM(a;b) =ab.
Pour toutkentier naturel non nul, PPCM(ka;kb) =k ×PPCM(a;b).
M(a;b) = M( PPCM(a;b)).