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

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

Note par nos Maxinautes :  

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.
PGCD de deux nombres entiers positifs 4/5 basé sur 137 votes.
Vous êtes ici :
Accueil > Fiches de cours du CP à la Terminale > cours de Mathématiques > PGCD de deux nombres entiers positifs
Accueil > Fiches de cours du CP à la Terminale > cours de Mathématiques > PGCD de deux nombres entiers positifs
Testez Maxicours premium pour 1€ le premier mois

Pour aider vos enfants à réussir leur scolarité, Primaire, Collège, Lycée, Maxicours vous propose :

Une aide immédiate par des Professeurs en ligne de 17 à 20h et 6/7j

Un accès illimité à tous nos cours, exercices, évaluations et corrections

L'accès illimité aux cours vidéos

laurier

Des parcours de révisions spécialement conçus pour le Brevet et le BAC

Des outils de suivi pour suivre la progression de vos enfants

Inscris-toi gratuitement sur Cours.fr,
tu pourras accéder à toutes les fiches de cours dans toutes les matières.