GGT-Rechner — Formel

Greatest Common Divisor (GCD)

Definition

The GCD of two numbers is the largest positive integer that divides both numbers evenly.

Euclidean Algorithm

1. Divide the larger number by the smaller 2. Replace the larger number with the remainder 3. Repeat until the remainder is 0 4. The last nonzero remainder is the GCD

Relationship with LCM

LCM(a, b) = a × b / GCD(a, b)