Euclidean Algorithm Calculator

Find the GCD using the Euclidean algorithm with step-by-step division, plus the Extended Euclidean algorithm.

Select Mode & Enter Values

Result

GCD(252, 105)
21
greatest common divisor
Input Values252 and 105
GCD21
Division Steps4
a / GCD12
b / GCD5

Step-by-Step Solution

GCD(252, 105) = 21

Understanding the Euclidean Algorithm

The Euclidean algorithm is one of the oldest algorithms still in common use, dating back to around 300 BC from Euclid's Elements. It is an efficient method for computing the Greatest Common Divisor (GCD) of two integers, which is the largest number that divides both of them without leaving a remainder.

The algorithm is based on the principle that GCD(a, b) = GCD(b, a mod b), and it repeatedly applies this until the remainder is zero. The last non-zero remainder is the GCD.

Algorithm Variants

Standard Euclidean

Repeatedly divide and take remainders until remainder is 0.

a = bq + r, then GCD(a,b) = GCD(b,r)

Extended Euclidean

Also finds integers x, y satisfying Bezout's identity.

ax + by = GCD(a, b)

LCM via GCD

The Least Common Multiple can be computed using the GCD.

LCM(a, b) = |a * b| / GCD(a, b)

Multiple Numbers

GCD of multiple numbers computed pairwise: GCD(a, b, c) = GCD(GCD(a, b), c).

GCD(a, b, c) = GCD(GCD(a,b), c)

Applications of the Euclidean Algorithm

The Euclidean algorithm has wide applications in mathematics and computer science. It is fundamental in number theory, used in RSA cryptography for computing modular inverses, essential in simplifying fractions, and used in solving linear Diophantine equations. The Extended Euclidean algorithm is particularly important in cryptographic systems.

Key Properties

  • The algorithm always terminates because the remainder strictly decreases at each step.
  • Time complexity is O(log(min(a, b))), making it very efficient.
  • GCD(a, 0) = a for any integer a.
  • GCD(a, b) = GCD(b, a mod b) is the fundamental recurrence.
  • The Extended Euclidean algorithm can find modular multiplicative inverses.
  • Bezout's identity guarantees that integers x, y exist such that ax + by = GCD(a, b).