Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Euclidean algorithm

A procedure for computing \gcd(a,b) by repeated division: replace (a,b) with (b,r), the divisor and remainder from dividing a by b, until the remainder reaches 0 -- the last nonzero remainder is the gcd.

Examples

  • Finding \gcd(48,18): 48=2(18)+12, 18=1(12)+6, 12=2(6)+0, so \gcd(48,18)=6.

See also

greatest common divisor relatively prime
Read the full section →
Graph settings

Calculator