Cours et exercices sur le PPCM et PGCD

Sandrine Dubois

Description

PGCD ET PPCM I. Plus grand commun diviseur Par convention, dans ce paragraphe, lorsque l’on parlera de diviseurs d’un entier naturel, il s’agira toujours des diviseurs positifs. 1. Diviseurs communs à deux entiers positifs Notation : pour tout entier naturel a, on note d(a) l’ensemble des diviseurs de a. Exemple : d(14) = ……………………… d(5) = ………………………. Remarques : • Si a 0 alors d(a) ne contient que des entiers naturels inférieurs ou égaux à a • Si a > 1, alors d(a) contient 1 et a • Le plus grand élément de d(a) est a et le plus petit est 1 • d(1) ne contient que l’élément 1. Notation : d(a ; b) est l’ensemble des diviseurs communs à a et b. Ainsi d(a ; b) = d(a) d(b) Exemple : d(7 ; 14) = ………………….. et d(3 ; 5) = ……………………………… Remarques : • d(a ; b) est un ensemble non vide, il contient toujours 1 • d(a ; b) contient un plus grand élément car il contient tous les nombres inférieurs ou égaux à a et à b si a 0 et si b 0 et inférieur à a si b = 0. Notation : Le plus grand diviseur commun à a et b est noté PGCD Exemple : a = 24 et b = 18. Trouvez les diviseurs communs de a et b et déduisez en leur PGCD 2. Conséquences immédiates Prop : • d(a ; 0) = d(a) pour tout a entier naturel • Si b / a alors PGCD(a ; b) = b Démonstration : Page 1 sur 5 „„„˙ Exemple : PGCD(3 ; 12) = 3.

Sujets

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

Informations

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

Extrait

PGCD ET PPCM

I. Plus grand commun diviseur

Par convention, dans ce paragraphe, lorsque l’on parlera de diviseurs d’un entier naturel, il s’agira toujours des
diviseurs positifs.

1. Diviseurs communs à deux entiers positifs

Notation: pour tout entier naturela, on note(a) l’ensemble des diviseurs dea.

Exemple : (14) = (5) = .


Remarques :
· Sia ¹0 alors(ane contient que des entiers naturels inférieurs ou égaux à) a
· Sia 1, alors(a) contient 1 eta
>
·Le plus grand élément de(a) estaet le plus petit est 1


· (1) ne contient que l’élément 1.

Notation : (a;b) est l’ensemble des diviseurs communs àaetb. Ainsi(a;b) =(a)Ç (b)

Exemple :  et(7 ; 14) = ..(3 ; 5) =

Remarques :
· (a;b) est un ensemble non vide, il contient toujours 1
· (a;bcar il contient tous les nombres inférieurs ou égaux à) contient un plus grand élément aet àbsia ¹
0 et si b¹0 et inférieur àasib= 0.

Notation: Le plus grand diviseur commun àaetbest noté PGCD

Exemple :a= 24 etb= 18. Trouvez les diviseurs communs deaetbet déduisez en leur PGCD








2. Conséquences immédiates

Prop :
· (a; 0) =(a tout) pouraentier naturel
· Sib/a alors PGCD(a;b) =b

Démonstration :

Page1sur5

Exemple :PGCD(3 ; 12) =

3. Calcul du PGCD

Prop :Effectuons la division euclidienne deaparb, on obtienta=bq+r 0 et r<b.
Alors(a;b) =(b;r).

Dém :











Exemple :Calcul PGCD(202 ; 138) par l’Algorithme d’Euclide










Th :L’ensemble des diviseurs communs àaetbdeux entiers positifs est l’ensemble des diviseurs de leur
PGCD.

ApplicationTrouver les diviseurs communs à 5238 et 2037




Remarque :Tout diviseur deaet debest un diviseur de leur PGCD.


II. Propriétés du PGCD

s premier entre eux lorsque leur PGCD vaut 1

Définition :Deux entiers naturels sont dit

Exemple : premier entre eux. sont2 et 3

Page2sur5

Théorème : a,betddes entiers naturels non nuls. Les trois propriétés suivantes sont équivalentes
1. d PGCD(a;b)
=
2. dest un diviseur deaetbet les quotientsnetn’ tels quea=ndetb=n’dsont premiers entre eux.
3. dest un diviseur deaetbet il existe deux entiers relatifsuetvtels queau+bv=d.

Démonstration :









Exemple :20 est-il le PGCD de 240 et 700 ?







Corollaire :Sid= PGCD(a;b) oùaetbdeux entiers naturel, alors quel que soit l’entier naturel non nuln,
dn= PGCD(na;nb)

Démonstration :






III. Théorème de Bezout.

Théorème de Bezout : aetbdeux entiers naturels non nuls.
aetbpremiers entre eux si et seulement si il existe deux entiers relatifssont uetvtel queau+bv= 1.

Démonstration :




Exemple :montrer quea= 47 etv= 35 sont premier entre eux

Méthode : On utilise l’algorithme d’Euclide et à chaque étape on écrit le reste sous formeau+bv

Page3sur5

IV.

Applications

1. Théorème de Gauss

Théorème de Gauss : a,betctrois entiers naturels non nuls tels quesont a/bcetaetbpremier entre eux
alorsa/c.

Dém :







Exemple :
· un nombre est divisible par 2 et 5. Comme 2 et 5 sont premier entre eux alors il est divisible par 10.
· Par contre 60 est divisible par 4 et 6 mais pas par 24. En effet 4 et 6 ne sont pas premier entre eux.

2. Fractions irréductibles

Définition :Soientaetbdeux entiers avecbnon nul. Lorsqueaetbpremier entre eux, on dit alors que lasont
fractionabest irréductible.

Th :fraction est égale à une fraction irréductible.Toute

Dém :

V. Equationax+by=c


Définition :soienta,b,ctrois entiers, l’équationax+by=c,oùxetysont les inconnues de, est appelée
équation diophantienne.

Th :l’équationax+by=cune solution si et seulement si le PGCD(admet a;b) divisec.

Dém :

Page4sur5

Exemples :Méthode de résolution d’une équation diophantien
a) Résoudre dans, l’équation : E1( x # ∗+ y 1 ).
b) Résoudre dans : E, l’équation1( x # ∗+ y 1 −.
























VI. Plus petit commun multiples.

ne

:

Th-Déf: Soientaetbdeux entiers naturels non nuls.Aetbadmettent un plus petit commun multiple positif.
On le note PPCM(a;b).

Th : aetbdeux entiers naturels non nul,d= PGCD(a;b) etm= PPCM(a;b!alors :
1. dm=ab

2. tout multiple commun àaetbest un multiple dem.

Dém :





Th : a,b,mtrios entiers naturels non nul.
Dire quem= PPCM(a;b) équivaut à dire quemest un multiple deaet debtel que les quotients demparaet
bsoient premiers entre eux.

Page5sur5