La réussite scolaire pour tous !
  • CP
  • CE1
  • CE2
  • CM1
  • CM2
  • 6e
  • 5e
  • 4e
  • 3e
  • 2e
  • Première
  • Terminale

Cours de mathématiques - PGCD de deux nombres entiers positifs

Objectifs
Parmi les diviseurs de deux nombres entiers, on s’intéressera à ceux qui sont communs à ces deux nombres, et tout particulièrement au plus grand d’entre eux.
Pour déterminer ce diviseur, on pourra utiliser plusieurs méthodes dont l’algorithme d’Euclide.

Qu’est-ce-qu’un multiple et un diviseur d’un nombre donné ? Qu’est-ce-que le PGCD de deux nombres entiers ? Comment déterminer le PGCD de deux nombres ? Que signifie que deux nombres entiers sont premiers entre eux ?
1. Multiples et diviseurs
Soient a et b deux nombres entiers.
Un nombre entier a est divisible par un nombre entier b si le reste de la division euclidienne de a par b est nul.
Dans ce cas, il existe un nombre entier k tel que : a = k × b

a est un multiple de b
b est un diviseur de a

Exemple :   238 est divisible par 14   car 238 : 14 = 17
En effet, la division euclidienne de 238 par 14 donne un reste nul :

Dans ce cas, on dit que 238 est un multiple de 14 et de 17 car 238 = 14 x 17
De même, on dit que 14 est un diviseur de 238.

Remarques : 17 est aussi un diviseur de 238 car 238 : 17 = 14

Conséquence : Chaque nombre a pour diviseurs 1 et lui-même.
Dans l'exemple précédent, 1 et 17 sont des diviseurs de 17, car 17 : 17 = 1 et 17 : 1 = 17
2. PGCD de deux nombres entiers
Soient a et b deux nombres entiers.
Un nombre entier c est un diviseur commun de a et de b, si c est à la fois un diviseur de a et un diviseur de b.

Conséquence : 1 est toujours un diviseur commun pour deux nombres entiers donnés.

Exemples :
3 est un diviseur commun de 12 et de 18, car   12 : 3 = 4   et   18 : 3 = 6
15 est un diviseur commun de 345 et 570, car   345 : 15 = 23   et   570 : 15 = 38

Le plus grand des diviseurs communs de deux nombres a et b est appelé le PGCD (Plus Grand Commun Diviseur) de ces deux nombres.
On le note PGCD (a ; b)


Recherche du PGCD de deux nombres entiers :
Méthode: on fait la liste de tous les diviseurs de chaque nombre, puis parmi ceux qui sont communs aux deux nombres, on prend le plus grand.

Exemple :
Donner le PGCD de 60 et 84
- Les diviseurs de 60 sont : 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 10 ; 12 ; 15 ; 20 ; 30 ; 60.
- Les diviseurs de 84 sont : 1 ; 2 ; 3 ; 4 ; 6 ; 7 ; 12 ; 14 ; 21 ; 28 ; 42 ; 84

1 ; 2 ; 3 ; 4 ; 6 ; 12 sont des diviseurs communs de 60 et 84.
12 est le plus grand nombre de cette liste. Donc le PGCD (60 ; 84) = 12.
3. Algorithme d'Euclide
Propriété : Soient a et b deux nombres entiers tel que a > b , et r le reste de la division euclidienne de a par b. On a : PGCD (a ; b) = PGCD (b ; r)

Exemple :

PGCD (35595 ; 6885)  =  PGCD (6885 ; 1170)
car le reste de la division de 35595 par 6885 est 1170

Application : Recherche du PGCD par l’algorithme d’Euclide

La propriété précédente peut être appliquée de manière successive aux différentes divisions euclidiennes de a par b puis de b par r, etc…
Par cette méthode, appelée "algorithme d’Euclide", le dernier reste non nul est le PGCD des deux nombres de départ.

Exemples : Calculer le PGCD de 35595 et de 6885
• On effectue la division de 35595 par 6885:
35595 = 5 × 6885 + 1170. Le reste de la division est 1170

• Puis on effectue la division de 6885 par 1170:
6885 = 5 × 1170 + 1035. Le reste de la division est 1035

• Puis on effectue la division de 1170 par 1035:
1170 = 1 × 1035 + 135. Le reste de la division est 135

• Puis on effectue la division de 1035 par 135:
1035 = 7 × 135 + 90. Le reste de la division est 90

• Puis on effectue la division de 135 par 90:
135 = 1 × 90 + 45. Le reste de la division est 45

• Puis on effectue la division de 90 par 45:
90 = 2 × 45 + 0. Le reste de la division est 0.

D’après la propriété vue plus haut :
PGCD(35595 ; 6885) = PGCD(6885 ; 1170) = PGCD(1170 ; 1035) = PGCD(1035 ; 135) = PGCD(135 ; 90) = PGCD(90 ; 45) = 45

Conclusion: Le PGCD de 35595 et 6885 est 45.

Remarque : Cet algorithme permet de déterminer le PGCD de deux grands nombres de manière plus rapide qu'en établissant la liste de leurs diviseurs.
4. Nombres premiers entre eux
Deux nombres entiers a et b sont premiers entre eux si leur plus grand diviseur commun est 1, autrement dit si PGCD (a ; b) = 1

Exemples :
- PGCD (23 ; 48) = 1 donc 23 et 48 sont premiers entre eux
- PGCD (35595  ;6885) = 45 donc 35595 et 6885 ne sont pas premiers entre eux.
Note par nos Maxinautes :  

PGCD de deux nombres entiers positifs 4/5 basé sur 119 votes.
Vous êtes ici :

Retrouve toutes tes fiches de cours sur COURS.FR

J'accède aux fiches  3e

Accède à l'intégralité de nos ressources sur MAXICOURS.COM

J'accède aux fiches  3e

Le meilleur soutien scolaire
pour vos enfants !

des élèves ont gagné
en autonomie dans
leur apprentissage.
des élèves ont
amélioré leurs notes
en cours.

Découvrez les contenus par classe

3e

Offre spéciale
révision BAC

Accède gratuitement
aux contenus de terminale
jusqu'au 12 juillet !

J'en profite

Le bon plan pour réviser
tes cours !

J'accède gratuitement aux fiches

3e