MathMathematical Algorithms

Euclidean Algorithm (GCD)

Compute the greatest common divisor by repeatedly replacing (a, b) with (b, a mod b); the extended form also finds x, y with ax + by = gcd.

Learn GCD (Euclidean Algorithm) →

a | b — Two positive integers up to 9999, e.g. "252 | 105"

a	b	q = a div b	r = a mod b
252	105	·	·

1/8gcd(252, 105): Euclid's insight is gcd(a, b) = gcd(b, a mod b), because any common divisor of a and b also divides a - q·b. We also track coefficients s, t with s·252 + t·105 = current a (extended Euclid).

Current division a = q·b + rValues that become the next (a, b)Finished rowsGCD

PseudocodeLearn GCD (Euclidean Algorithm) →

1(s0, s1), (t0, t1) = (1, 0), (0, 1)   # a = s0·A + t0·B, b = s1·A + t1·B
2while b != 0:
3  q = a div b; r = a mod b
4  a, b = b, r
5  s0, s1 = s1, s0 - q·s1;  t0, t1 = t1, t0 - q·t1
6return a  # gcd; and s0·A + t0·B == gcd

Variables

a252

b105

Complexity

best O(1)

avg O(log min(a, b))

worst O(log min(a, b))

space O(1)

Speed