Le plus grand commun diviseur (PGCD) est le plus grand nombre qui divise deux entiers ou plus sans reste. Pour 12 et 18, les diviseurs sont 1, 2, 3 et 6, donc le PGCD est 6. On l'appelle aussi le plus grand facteur commun.

L'algorithme d'Euclide calcule efficacement le PGCD. Il consiste à diviser le plus grand nombre par le plus petit, puis à remplacer le plus grand par le reste, et à répéter l'opération jusqu'à ce que le reste soit nul. Le dernier reste non nul est le PGCD. Cette méthode, vieille de plus de deux mille ans, est encore utilisée en informatique.

Le PGCD simplifie les fractions. Diviser le numérateur et le dénominateur par leur PGCD réduit une fraction à sa forme irréductible. Il intervient également en arithmétique modulaire, en cryptographie et en théorie des nombres. Le plus petit commun multiple (PPCM) est lié au PGCD par la formule PPCM(a, b) = a × b / PGCD(a, b).

• Plus grand nombre divisant exactement des entiers
• Découvert par l'algorithme d'Euclide
• Utilisé pour simplifier les fractions
• Lié au PPCM par une formule simple