Euclidean Algorithm
Recursively finds the greatest common divisor.
Formula
Variables
Example
gcd(48,18)=gcd(18,12)=gcd(12,6)=6
How it works
The Euclidean Algorithm finds the greatest common divisor by replacing a pair of numbers with a smaller pair that has the same gcd. It works because any number that divides both a and b must also divide the remainder when a is divided by b, so the common divisors do not change when you switch from (a, b) to (b, a mod b). Repeating this step makes the numbers get smaller until the remainder is 0, and the last nonzero number is the gcd.
When to use it
Use this when you need the gcd of two integers quickly, especially for simplifying fractions or solving number theory problems. It is also useful in modular arithmetic, finding coprime numbers, and later topics like linear Diophantine equations.
Worked example, step by step
Find gcd(56, 24) 56 mod 24 = 8, so gcd(56, 24) = gcd(24, 8) 24 mod 8 = 0, so gcd(24, 8) = gcd(8, 0) The last nonzero remainder is 8 Therefore, gcd(56, 24) = 8
Common mistakes to avoid
- Stopping at the first remainder instead of continuing until the remainder is 0
- Using the larger number first in the mod step incorrectly, which can lead to the wrong remainder
- Forgetting that the gcd is the last nonzero number, not the final 0
Did You Know?
Euclid's algorithm for the GCD, from 300 BC, is still one of the oldest algorithms in everyday use.
Share this formula
More in Number Theory
View allModular Congruence
Basica and b have the same remainder when divided by m.
Fermat's Little Theorem
AdvancedHolds when p is prime and gcd(a,p)=1.
Euler's Totient
AdvancedCounts integers up to n coprime to n.
Prime Number Theorem
AdvancedApproximates the number of primes below x.
LCM from GCD
BasicLeast common multiple via the greatest common divisor.
Sum of First n Integers
BasicClosed form for the sum of the first n natural numbers.