Number Theory
Basic

Euclidean Algorithm

Recursively finds the greatest common divisor.

Formula

gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b) = \gcd(b, a \bmod b)

Variables

a, bPositive integers

Example

gcd(48,18)=gcd(18,12)=gcd(12,6)=6

Did You Know?

Euclid's algorithm for the GCD, from 300 BC, is still one of the oldest algorithms in everyday use.

gcdeuclidnumber theory