Calculatrice PGCD et PPCM

Calculez le plus grand commun diviseur (PGCD) et le plus petit commun multiple (PPCM) avec étapes complètes.

Qu'est-ce que Calculatrice PGCD et PPCM ?

Le plus grand commun diviseur (PGCD) et le plus petit commun multiple (PPCM) sont deux des concepts les plus importants en théorie élémentaire des nombres, avec des applications allant de la simplification de fractions au collège aux algorithmes cryptographiques qui sécurisent internet.

L'algorithme d'Euclide, décrit par Euclide vers 300 av. J.-C., est l'un des algorithmes les plus anciens et les plus efficaces en mathématiques. Il calcule le PGCD en O(log(min(a,b))) étapes, se terminant rapidement même pour de très grands nombres. L'algorithme applique l'identité : PGCD(a, b) = PGCD(b, a mod b) jusqu'à ce que le reste soit nul.

Cette calculatrice montre l'algorithme d'Euclide complet étape par étape pour deux nombres, et calcule aussi le PGCD et le PPCM pour des listes de plusieurs nombres en utilisant la généralisation : PGCD(a, b, c) = PGCD(PGCD(a, b), c).

Formule

Algorithme d'Euclide :

PGCD(a, b) = PGCD(b, a mod b) jusqu'à b = 0

PPCM à partir du PGCD :

PPCM(a, b) = |a × b| / PGCD(a, b)

Pour plusieurs nombres :

PGCD(a, b, c) = PGCD(PGCD(a, b), c)

PPCM(a, b, c) = PPCM(PPCM(a, b), c)

Comment calculer

Entrez deux entiers positifs a et b.
Appliquez la division entière : a = q×b + r.
Remplacez a par b et b par r. Répétez jusqu'à r = 0.
Le dernier reste non nul est le PGCD.
Calculez PPCM = |a × b| / PGCD à l'aide de l'identité fondamentale.
Utilisez le mode "Plusieurs nombres" pour trois nombres ou plus.

Exemple

Trouvez PGCD(48, 18) : 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. PGCD = 6. PPCM = |48×18|/6 = 864/6 = 144. Vérification : 144/48 = 3 ✓, 144/18 = 8 ✓.

Termes Clés Expliqués

PGCD: Plus grand entier divisant les deux nombres sans reste
PPCM: Plus petit entier positif divisible par les deux nombres
Premiers entre eux: Deux nombres avec PGCD = 1, sans facteurs premiers communs
Algorithme d'Euclide: Algorithme antique calculant le PGCD par divisions successives
Opération modulo: a mod b est le reste de la division de a par b
Divisibilité: a divise b si b/a n'a pas de reste

Cas d'utilisation courants

Simplifier des fractions : réduire a/b en divisant les deux par PGCD(a, b)
Additionner des fractions avec des dénominateurs différents : trouver le PPCM des dénominateurs
Ordonnancement : trouver quand deux événements récurrents coïncideront
Génération de clés RSA : vérifier que l'exposant e est premier avec φ(n)
Problèmes de rapports d'engrenages en génie mécanique
Conception de motifs de carrelage : trouver la plus petite unité répétitive

Questions fréquentes

Qu'est-ce que le PGCD et comment est-il calculé ?

Le plus grand commun diviseur (PGCD) est le plus grand entier positif qui divise a et b sans reste. L'algorithme d'Euclide le calcule efficacement : remplacez (a, b) par (b, a mod b) jusqu'à ce que b = 0. La dernière valeur non nulle est le PGCD.

Qu'est-ce que le PPCM et à quoi sert-il ?

Le plus petit commun multiple (PPCM) est le plus petit entier positif divisible par a et b. Il sert à additionner des fractions avec des dénominateurs différents, aux problèmes d'ordonnancement et à la théorie musicale.

Quelle est la relation entre PGCD et PPCM ?

PGCD(a, b) × PPCM(a, b) = |a × b|. Une fois le PGCD connu, le PPCM est simplement |a × b| / PGCD(a, b). C'est plus efficace que d'énumérer les multiples.

Que signifie que deux nombres sont premiers entre eux ?

Deux nombres sont premiers entre eux (relativement premiers) si leur PGCD est 1 — ils n'ont aucun facteur premier commun. La primalité relative est fondamentale en arithmétique modulaire, en cryptographie et dans le théorème chinois des restes.

Outils connexes