BeginnerCoder
Donate← Algorithms Foundations
7 / 25
Lesson 7 — GCD (Euclid)
Euclid's algorithm: 2,300 years old and still used
The GCD (greatest common divisor) of two numbers is the biggest number that divides both. Euclid noticed that gcd(a, b) = gcd(b, a % b), where % is the remainder after division. Repeat until b becomes 0; then a is the answer.
# gcd(48, 18) -> gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0) = 6
From the GCD you also get the LCM (least common multiple): a × b // gcd(a, b).
Why it matters: it is fast even for huge numbers and is used inside encryption, fraction simplification and timing problems.
Want it another way?
Task
Write the loop body from the theory: the new a is the old b, and the new b is the remainder of a divided by b. Expected: gcd 6, gcd 1, lcm 12.
Run your code — when the output matches the task, you will see a green check. Then mark the lesson complete.
Test your knowledge
Test your knowledgeA quick 3-question quiz on this lesson — instant feedback.