Méthodes pour déterminer le PGCD de deux entiers naturels non nuls    (4/9)
 

Savoir-faire : déterminer le PGCD de deux entiers naturels non nuls

A l'aide de la décomposition en nombres premiers Soit a et b deux entiers naturels non nuls.   et .   sont des nombres premiers distincts.   et sont des entiers naturels éventuellement nuls.   pour tout indice i vérifiant : . Exemple : déterminer .   et donc .   A l'aide de l'algorithme d'Euclide Soit a et b sont deux entiers naturels non nuls. La suite des divisions euclidiennes : de a par ,                               avec , de b par (si ),              avec , de par (si ),            avec , de par (si ), avec , permet de définir une suite strictement décroissante d'entiers positifs. Le dernier reste non nul est alors le PGCD de a et b (si , alors c'est b). Exemple : déterminer le Donc .