GCD Calculator – Greatest Common Divisor

The greatest common divisor is the largest integer dividing both inputs, and Euclid’s algorithm finds it by repeated remainders. For 48 and 18: 48 mod 18 = 12, then 18 mod 12 = 6, then 12 mod 6 = 0 — the last nonzero remainder, 6, is the GCD. The calculator prints this division ladder so each reduction is visible, then lists all common divisors (1, 2, 3, 6) to confirm 6 is the greatest. Special cases fall out of the recursion: gcd(a, 0) = a, so gcd(7,0) = 7, and gcd of equal numbers is the number itself. The result feeds directly into simplifying fractions — 84/126 divides by gcd(84,126) = 42 to give 2/3 — and into LCM via the identity LCM(a,b) = a×b/GCD(a,b) (for 48,18: 864/6 = 144). Coprime pairs like 8 and 15 return GCD 1.

1. 1

   Enter two integers

   Any whole numbers; order does not matter

2. 2

   Apply Euclid’s algorithm

   Each remainder step is displayed: 48,18 → 18,12 → 12,6 → 6,0

3. 3

   Read the GCD

   The last nonzero remainder is the answer: 6

4. 4

   Use the byproducts

   Common divisors, simplified fraction, and LCM appear alongside

• 1

  Euclid: keep replacing (a,b) with (b, a mod b) until zero

• 2

  gcd(a, 0) = a; gcd(a, a) = a

• 3

  LCM(a,b) × GCD(a,b) = a × b

• Stopping at the first common divisor found instead of the greatest

• Computing gcd(48,18) as 48−18 = 30 instead of taking remainders

• Expecting the GCD to exceed the smaller input

• Forgetting gcd with zero: gcd(7,0) = 7, not 0 or undefined