AccueilAccueil
Maxicours.com, Le N°1 du soutien scolaire sur Internet

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

 

Toutes les matières 

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.
Cette fiche de cours t'intéresse ?
N'attends plus pour en voir d'autres !
PGCD de deux nombres entiers positifs 4/5 basé sur 101 votes.
Vous êtes ici :
Première visite
Je m'abonne !