PGCD de deux nombres entiers positifs
- Fiche de cours
- Quiz
- Profs en ligne
- Videos
- Application mobile
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 ?
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
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.
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.
Vous avez obtenu75%de bonnes réponses !