Calculateur PGCD et PPCM

Comment calculer le PGCD et le PPCM ?

Le PGCD (Plus Grand Commun Diviseur) est le plus grand entier qui divise exactement deux nombres ou plus sans reste. Le PPCM (Plus Petit Commun Multiple) est le plus petit entier positif qui est un multiple commun à tous les nombres. Ces deux notions sont fondamentales en arithmétique, notamment pour simplifier les fractions et résoudre des problèmes de synchronisation.

L'algorithme d'Euclide pour le PGCD

L'algorithme d'Euclide est la méthode la plus efficace pour calculer le PGCD. Pour deux nombres a et b, on divise a par b et on garde le reste r. On remplace ensuite a par b et b par r, et on recommence jusqu'à ce que le reste soit 0. Le dernier reste non nul est le PGCD. Exemple : PGCD(48, 18) → 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0 → PGCD = 6.

Relation entre PGCD et PPCM

Pour deux nombres a et b, la relation est : PGCD(a,b) × PPCM(a,b) = a × b. Donc PPCM(a,b) = (a × b) / PGCD(a,b). Pour plus de deux nombres, le PGCD et le PPCM sont calculés successivement par paires en utilisant l'associativité de ces opérations.