AlgoScope

Euclidean Algorithm

Replace (a, b) with (b, a mod b) until b is 0. The last non-zero value is the gcd.

Mathematics, algorithm, beginner
48 modulo 18 is 12. The pair is now 18 and 12.480181122i
48 modulo 18 is 12. The pair is now 18 and 12.480181122i

Number Theory Basics: gcd(48, 18) by Euclid

Step, step 2 of 5

48 mod 18 = 12. Any divisor of 48 and 18 divides 12 too, so the pair becomes (18, 12).

Cost

Best
O(1)
Average
O(log min(a, b))
Worst
O(log min(a, b))
Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Number Theory Basics covers these too, in the same run.