1. Until remainder zero
Repeat until the second value becomes zero.
while (b !== 0)Typorithm · easy
GCD (Euclid)
▷ Interactive algorithm labgcd-euclideanmatheuclidmodulolcm
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn GCD (Euclid)
Math & Number Theory
Euclid's algorithm: replace (a, b) with (b, a mod b) until b is zero; a is the GCD.
The GCD of two numbers also divides their remainder, so a mod b preserves it.
Each step shrinks the pair quickly, reaching zero in O(log min(a, b)) iterations.
LCM follows directly: a / gcd(a, b) * b, dividing before multiplying to stay safe.
Preparing algorithm lab…
01
Replace (a, b) with (b, a mod b).
02
Stop when b is zero.
03
lcm = a / gcd * b.
function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
function lcm(a, b) {
return (a / gcd(a, b)) * b;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Euclid step
Replace (a, b) with (b, a mod b) — the core of Euclid's algorithm.
[a, b] = [b, a % b]3. GCD is a
When b hits zero, a holds the greatest common divisor.
return a4. LCM via GCD
lcm(a, b) = a / gcd(a, b) * b, dividing first to avoid overflow.
return (a / gcd(a, b)) * bA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.