Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

Plus grand commun diviseur (mathématiques élémentaires)

Cet article fait partie de la série
Mathématiques élémentaires

Le PGCD (ou plus grand diviseur commun) de deux nombres entiers naturels est, comme son nom l’indique, le plus grand nombre entier qui divise nos deux nombres.

Considérons par exemple 30 et 48. 6 divise 30 car 6×5=30 et 6 divise 48 car 6×8=48.
Il n’y a pas de nombre entier supérieur à 6 qui divise à la fois 30 et 48 car sinon il serait divisible par 5.

De la même manière on peut parler de PGCD de plusieurs nombres entiers naturels.

Méthode par décomposition en facteurs premiers

Pour trouver facilement le PGCD de nombres pas trop grands, il est efficace de les décomposer en produits de facteurs premiers.
Reprenons 30 et 48 :

30=2×3×5

48=2×2×2×2×3

On remarque que le produit 2×3 est commun aux deux et est le plus grand produit commun, il est donc le PGCD.

Dans le cas de plus de deux nombres entiers cette méthode est applicable :

56=2×2×2×7

84=2×2×3×3

140=2×2×5×7

Leur PGCD est donc 2×7 soit 14.

Méthode par l’algorithme d’Euclide

Cet algorithme est un peu plus difficile à comprendre, il s’appuie sur le fait que si un nombre entier divise deux autres nombres entiers, alors il divise leur différence (et leur somme). Il divisera donc les différences successives du plus petit ôté du plus grand.

Reprenons l’exemple de 30 et de 48 :

48−30=18

30−18=12

18−12=6

12−2×6=0

Le dernier reste non nul est le PGCD.

Essayons avec 56 et 140 :

140−56=84

84−56=28

56−28=28

28−28=0

Donc le PGCD est 28