Plus Grand Commun Diviseur
En mathématiques, le PGCD est le Plus Grand Commun Diviseur de deux nombres.
Il s'utilise seulement en arithmétique, avec des nombres entiers, jamais avec des nombres décimaux.
Le PGCD sert notamment à simplifier des fractions.
Pour trouver le PGCD de deux petits nombres on peut faire la liste de tous leurs diviseurs. Prenons par exemple 18 et 27 :
- Les diviseurs de 18 sont : 1, 2, 3, 6, 9, 18
- Les diviseurs de 27 sont : 1, 3, 9, 27
On cherche alors le plus grand diviseur commun aux deux, c'est ici 9, donc le PGCD de 18 et 27 est 9. On peut noter .
Note : l'ordre des nombres n'a pas d'importance :
Si , on dit que et sont premiers entre eux.
Algorithme des différences
Calculons avec l'algorithme des différences :
On soustrait le plus petit nombre au plus grand :
On s'intéresse au diminuteur (70) et au reste (98) et on soustrait le plus petit au plus grand :
On s'intéresse au diminuteur (70) et au reste (28) et on soustrait le plus petit au plus grand :
On s'intéresse au diminuteur (28) et au reste (42) et on soustrait le plus petit au plus grand :
On s'intéresse au diminuteur (28) et au reste (14) et on soustrait le plus petit au plus grand :
On s'intéresse au diminuteur (14) et au reste (14) et on soustrait le plus petit au plus grand :
On finit par avoir un résultat nul. Le PGCD est le dernier reste non nul, deux lignes au dessus : .
Algorithme d'Euclide
Calculons avec l'algorithme d'Euclide:
On divise le plus grand nombre par le plus petit :
On divise le diviseur par le reste :
On divise le diviseur par le reste : .
Le PGCD correspond au dernier reste non nul qui est .
Simplifier une fraction
Voir l'article fractions.
|
