GCD Calculator

Definition

The greatest common divisor of two integers a and b (written GCD(a, b), also HCF) is the largest positive integer d such that d | a and d | b. Equivalently, d is the largest positive common divisor of the absolute values |a| and |b|. When a = b = 0 the notion is not defined here — the calculator rejects that pair. When exactly one number is zero, GCD(0, b) = |b| for b ≠ 0.

This calculator implements Euclid’s algorithm: on absolute values it repeats (x, y) → (y, x mod y) until y = 0; then x is the GCD. Computation: repeatedly replace the pair (a, b) with (b, a mod b) until b = 0; the last non-zero a is the GCD. Mathematical model: Euclid’s algorithm / Euclidean algorithm. Descriptive sources: Euclid, Elements (Book VII); Wikipedia — Greatest common divisor; MathWorld — Greatest Common Divisor; Hardy & Wright, An Introduction to the Theory of Numbers.

In teaching practice it helps to separate the number-theoretic definition from computer-arithmetic limits: the calculator requires finite integers and shows the result of that computation, not a symbolic proof on paper. Bézout’s identity (integers x, y with ax + by = GCD) is true, but this form does not hunt Bézout coefficients — only d itself.

Historical and conceptual context

Euclid’s algorithm is among the oldest described computational procedures. In Euclid’s Elements (c. 3rd century BCE), especially Book VII on the arithmetic of integers, a geometric and arithmetic form of repeated subtraction / division with remainder leads to a common measure. Modern a mod b notation and the remainder loop are the same core: common divisors of a and b are also common to b and a mod b.

Coprimality (GCD = 1) runs through number theory, cryptography (RSA exponents coprime to φ(n)), and fraction reduction. LCM ties to GCD by LCM(a, b)·GCD(a, b) = |a·b| for nonzero a, b. In school, GCD appears when reducing fractions, building common denominators, and simplifying ratios.

Conceptually, GCD is not a single-division remainder (modulo), not LCM, and not the quotient a/b. Modulo supplies the remainder used in Euclid’s steps; LCM seeks a common multiple; a ratio divides both parts by the GCD. Here the only question is: what is the largest d dividing both numbers.

Formal properties

Domain of this calculator: a, b ∈ ℤ, not both zero. GCD(a, b) = GCD(|a|, |b|) = GCD(b, a). GCD(a, 0) = |a| when a ≠ 0. GCD(ka, kb) = |k|·GCD(a, b) for integer k. If d = GCD(a, b), then GCD(a/d, b/d) = 1.

Euclid invariant: the set of common divisors of a and b equals that of b and a mod b (when b ≠ 0). Hence correctness: each remainder preserves common divisors, and when the remainder vanishes the previous divisor is the greatest common one.

Complexity: the number of steps is O(log min(|a|, |b|)) in the typical case; worst-case behavior links to Fibonacci numbers (slow remainder decay). School examples (48, 18, 84, 36) need only three or four steps.

In teaching practice it helps to separate the mathematical identity from floating-point limits: above 2⁵³ not every integer is exactly representable in floating-point arithmetic. Typical school examples fit with room to spare.

Full derivation

Step 1. Enter two integers a and b. The parser accepts comma or period, but the value must come out integer. An empty field does not substitute zero for a missing entry.

Step 2. Reject the pair 0, 0. Take A = |a|, B = |b|.

Step 3. While B ≠ 0: R = A % B; A ← B; B ← R. Record each step in the panel as A = q·B + R.

Step 4. When B = 0, GCD = A. For 48 and 18: (48, 18) → (18, 12) → (12, 6) → (6, 0), so GCD = 6.

Step 5. Optionally: a/d and b/d give a reduced pair (ratio preview); LCM = |a·b|/d when a ≠ 0 and b ≠ 0.

Step 6. The chip figure shows a, b → remainder chain → GCD. That is the same path, not a separate model.

Special cases

GCD(48, 18) = 6; GCD(17, 13) = 1; GCD(0, 25) = 25; GCD(100, 100) = 100; GCD(84, 36) = 12; GCD(144, 96) = 48; GCD(270, 192) = 6; GCD(35, 49) = 7; GCD(−48, 18) = 6.

Fraction 12.5 with 8: “not integer” error. 0 with 0: domain error. Field order does not change the GCD (commutativity), but it changes how steps are written when you start from the smaller number — the algorithm still reaches the same d.

When GCD = 1 the integers are coprime: they cannot be reduced by a common divisor larger than 1. When |a| = |b| ≠ 0, GCD = |a|.

Numerical notes

The % operator and loop run on floating-point numbers. For |a|, |b| above 2⁵³ precision artifacts can appear — educational tool, not an arbitrary-precision system. Comma and period are equivalent.

The calculator does not solve ax + by = d (Bézout), does not factor primes, and does not compute GCD of many arguments at once — only a pair. Multi-argument LCM needs a separate iterative strategy.

Locale display (en-US) does not change the internal value: GCD(48, 18) is exactly 6.

Related ideas and sources

Related: LCM; ratio of two numbers (reduce by GCD); modulo (remainder in Euclid’s steps); ordinary fractions / reduction; coprime integers. Bézout’s identity and the extended Euclidean algorithm sit one step further — outside this form.

Sources: Euclid, Elements, Book VII (arithmetic, common measure); Hardy & Wright, An Introduction to the Theory of Numbers; Knuth, The Art of Computer Programming (GCD algorithms); Wikipedia — Greatest common divisor; MathWorld — Greatest Common Divisor. Educational tool — not a substitute for a textbook or instructor check.