Algorithme d'Euclide pas à pas, décomposition en facteurs premiers et identité de Bézout
Le PGCD (Plus Grand Commun Diviseur) et le PPCM (Plus Petit Commun Multiple) sont deux notions fondamentales de l'arithmétique. Ce calculateur gratuit vous permet de les obtenir instantanément pour 2 à 5 nombres, avec deux méthodes détaillées : l'algorithme d'Euclide pas à pas et la décomposition en facteurs premiers.
L'outil affiche également l'identité de Bézout (coefficients u et v tels que au + bv = PGCD), la liste des diviseurs communs, et vérifie la relation PGCD × PPCM = |a × b|. Chaque étape est expliquée pour faciliter la compréhension et l'apprentissage.
Le PGCD sert notamment à simplifier les fractions, tandis que le PPCM est utilisé pour mettre des fractions au même dénominateur ou synchroniser des cycles périodiques. Ces concepts sont au programme du collège, du lycée et des études supérieures en mathématiques. L'identité de Bézout est essentielle en cryptographie (algorithme RSA) et pour résoudre les équations diophantiennes.
Deux méthodes principales. Algorithme d'Euclide : effectuer des divisions euclidiennes successives (diviser le plus grand par le plus petit, reprendre avec le reste) jusqu'à obtenir un reste nul. Le dernier reste non nul est le PGCD. Exemple : PGCD(48, 18) → 48 = 18×2 + 12, puis 18 = 12×1 + 6, puis 12 = 6×2 + 0 → PGCD = 6. Décomposition en facteurs premiers : décomposer chaque nombre, puis prendre les facteurs communs avec le plus petit exposant.
Pour deux entiers a et b : PGCD(a, b) × PPCM(a, b) = |a × b|. Cette formule permet de calculer le PPCM facilement une fois le PGCD connu : PPCM = |a × b| / PGCD. Par exemple, PGCD(12, 18) = 6, donc PPCM = 12 × 18 / 6 = 36. On peut aussi utiliser la décomposition en facteurs premiers : le PPCM est le produit de tous les facteurs premiers avec le plus grand exposant.
Le théorème de Bézout affirme que pour deux entiers a et b non tous deux nuls, il existe des entiers u et v tels que a × u + b × v = PGCD(a, b). Ces coefficients se calculent en « remontant » l'algorithme d'Euclide étendu. Application majeure : si a et b sont premiers entre eux (PGCD = 1), on obtient au + bv = 1, ce qui permet de trouver l'inverse modulaire utilisé en cryptographie RSA.
On utilise l'associativité : PGCD(a, b, c) = PGCD(PGCD(a, b), c). On calcule d'abord le PGCD des deux premiers nombres, puis le PGCD du résultat avec le troisième, et ainsi de suite. Même principe pour le PPCM. Par exemple : PGCD(24, 36, 60) → PGCD(24, 36) = 12, puis PGCD(12, 60) = 12. Cet outil supporte jusqu'à 5 nombres simultanément.