DEV Community

MultiCalify
MultiCalify

Posted on Edited on

Euclid's Algorithm, Explained by Computing a GCF by Hand

The greatest common factor (GCF) of two integers is the largest positive integer that divides both of them. The same quantity is also called the greatest common divisor (GCD) or the highest common factor (HCF). You need it whenever you reduce a fraction, find a common tile size, schedule two repeating jobs so they coincide, or compute a least common multiple.

The school method is prime factorisation: break each number into primes, then multiply the shared primes. That works beautifully for 48 and 18, and it becomes unpleasant for 1,071 and 462, or for 64-bit integers. Euclid's algorithm, written down more than two thousand years ago, replaces factorisation with a short remainder loop. It is also the algorithm most calculator implementations actually run.

The rule

For integers a ≥ b > 0:

gcd(a, b) = gcd(b, a mod b)

When the remainder becomes 0, the current divisor is the GCF. The same recurrence is often written with subtraction instead of modulo — repeatedly replace the larger number with the difference of the two — but modulo simply subtracts as many times as it can in one step.

Why this is valid: any common divisor of a and b also divides a − qb, and a mod b is exactly that remainder. So the set of common divisors is preserved at every step, and the greatest one cannot change.

A worked example: gcd(252, 105)

252 = 2 × 105 + 42
105 = 2 ×  42 + 21
 42 = 2 ×  21 +  0
Enter fullscreen mode Exit fullscreen mode

The last non-zero remainder is 21. Check: 252 = 12 × 21 and 105 = 5 × 21, and 12 and 5 share no further factor, so 21 is the GCF.

A second pair, so the pattern is obvious:

1071 = 2 × 462 + 147
 462 = 3 × 147 +  21
 147 = 7 ×  21 +   0
Enter fullscreen mode Exit fullscreen mode

Again the GCF is 21. Prime factorisation would have required splitting 1,071 (3 × 3 × 7 × 17) and 462 (2 × 3 × 7 × 11) and then collecting the shared 3 × 7. Euclid never needed those primes.

Python

def gcd(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a  # gcd(n, 0) == n, and gcd(0, 0) is defined here as 0

assert gcd(252, 105) == 21
assert gcd(1071, 462) == 21
assert gcd(48, 18) == 6
Enter fullscreen mode Exit fullscreen mode

Python already exposes this as math.gcd, and from 3.9 onwards math.gcd accepts more than two arguments. The loop above is what that function is doing.

JavaScript

function gcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

console.log(gcd(252, 105)); // 21
Enter fullscreen mode Exit fullscreen mode

Two practical caveats in JavaScript: % preserves the sign of the dividend, which is why the inputs are forced through Math.abs first, and Number is a IEEE-754 double, so this version is only safe for integers up to 2^53. For larger integers, use BigInt and the same loop.

How fast is it?

Each remainder is strictly smaller than the previous divisor, so the loop must finish. The worst-case inputs are consecutive Fibonacci numbers; the number of division steps is then Θ(log n). For 64-bit inputs that is a handful of iterations, which is why the algorithm is the default in almost every standard library.

A close cousin, Stein's (binary) GCD, replaces division with bit shifts, subtracting when both numbers are odd. It is attractive in hardware and in languages where modulo on big integers is expensive. For ordinary application code, the modulo form is clearer and already fast.

LCM for free

Once you have the GCF, the least common multiple follows from a one-line identity:

lcm(a, b) = |a · b| / gcd(a, b)

For 252 and 105, lcm = 252 × 105 / 21 = 1,260. Multiply first in an arbitrary-precision type, or divide before you multiply, so the intermediate product cannot overflow a fixed-width integer:

def lcm(a: int, b: int) -> int:
    if a == 0 or b == 0:
        return 0
    return abs(a // gcd(a, b) * b)
Enter fullscreen mode Exit fullscreen mode

For three or more integers, fold the same functions: gcd(a, b, c) = gcd(gcd(a, b), c), and likewise for lcm. That is how you reduce a three-term fraction or find a common period for three repeating timers.

Edge cases worth testing

  • gcd(0, n) is |n|, and gcd(0, 0) is conventionally 0 in most libraries.
  • Signs should not affect the result: gcd(-252, 105) is still 21.
  • If you need the GCF of more than two numbers, reduce left to right; order does not change the answer.
  • For a fraction a/b in lowest terms, divide both parts by gcd(a, b).

If you want to confirm a pair, or see the prime-factor path next to the Euclidean steps, this step-by-step greatest-common-factor tool runs both views on the same inputs. The value of Euclid's algorithm is that you can also do it on paper, or in ten lines of code, and get the same 21.


Muhammad Rashid is the founder of Multicalify, where he publishes free calculators for everyday finance, math and time problems.

Top comments (0)