GCD Calculator, Greatest Common Divisor (Euclidean Algorithm)

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both of them without leaving a remainder. It is one of the most fundamental operations in elementary number theory, and it shows up in places you would not always expect: in the kitchen when you scale a recipe by the largest common unit, in engineering when you align gear teeth or subdivide a measurement, and in cryptography where the difficulty of reversing modular exponentiation is what keeps your bank transactions safe. This free GCD calculator computes the greatest common divisor of any two positive integers up to one billion, walks you through every step of the Euclidean algorithm that produces the answer, and reports the matching least common multiple so you can move straight on to related problems.

The tool uses the iterative Euclidean algorithm, never the recursive form, because the recursive version will eventually overflow the call stack when the inputs are large or when the algorithm takes many iterations. The iterative loop is mathematically identical, just expressed without function self-calls, and it works for every integer the input fields accept. Enter two numbers, click Calculate, and you get the GCD plus the full chain of reductions that led to it: gcd(48, 18) → gcd(18, 48 mod 18 = 12) → gcd(12, 18 mod 12 = 6) → gcd(6, 12 mod 6 = 0) → 6.

The GCD has a long history. Euclid described the algorithm in Book VII of his Elements around 300 BC, and it is still the standard method taught today, partly because it is fast, and partly because it is beautiful. The number of divisions it performs is bounded by about five times the number of digits in the smaller input, which means even 30-digit numbers reduce in well under a hundred steps. There is essentially no number a calculator like this can be given where the Euclidean algorithm feels slow.

The GCD is sometimes called the greatest common factor (GCF), the highest common factor (HCF), or, particularly in older British textbooks, the greatest common measure. All four names refer to the same quantity. If you have seen those terms elsewhere and want to make sure you are computing the same thing, you are in the right place.

How to Use the GCD Calculator

1. Enter the first integer in the box labelled A. The calculator accepts non-negative whole numbers from 0 to 1,000,000,000. Use the smallest number as input A if you want the most compact step-by-step trace, although the algorithm works correctly regardless of which value you put first.
2. Enter the second integer in the box labelled B. The same range and constraints apply: a non-negative whole number up to one billion. Decimal fractions, scientific notation, and negative numbers are rejected with a clear error message rather than silently coerced.
3. Click Calculate. The button runs the iterative Euclidean algorithm and renders the result. You can also press Enter inside either input field to trigger the same calculation without moving the mouse.
4. Read the GCD, the chain of Euclidean steps, and the LCM (least common multiple). The result box shows the original pair, the final answer in large type, a chip that lights up if the two inputs are coprime, the step-by-step chain (open by default, but collapsible), and the LCM computed via the standard identity lcm(a, b) = |a × b| / gcd(a, b).
5. Clear the inputs with the secondary button when you want to start over. Both fields reset to empty, the result panel disappears, and any error message is cleared.

A note on the edge cases: the calculator accepts gcd(0, n) = n for any positive integer n, which is the convention most textbooks use. It does not accept gcd(0, 0) because that case is genuinely undefined, every integer divides zero, so there is no single "greatest" divisor to report. The tool shows an explanatory error message rather than guessing.

The calculator does not accept negative inputs, fractions, or values above one billion. These limits exist for two reasons: keeping the displayed numbers readable (a thousand-digit output would not fit cleanly in a result panel) and staying well within JavaScript's safe integer range for the LCM, which squares to roughly 10^18 when both inputs are at the upper bound.

The Formulas

Euclidean algorithm, recurrence. The mathematical statement is gcd(a, b) = gcd(b, a mod b), with the base case gcd(a, 0) = a. The recurrence is correct because any common divisor of a and b is also a common divisor of b and a mod b (since a mod b = a − b × floor(a/b)), and conversely. Repeatedly swapping the pair until the second element reaches zero is guaranteed to terminate because the second element strictly decreases on every iteration.

Euclidean algorithm, iterative. Translated into code without recursion, the algorithm is:

while b is not 0:
    record the current (a, b) and the remainder r = a mod b
    set (a, b) to (b, r)
return a

The variable a at the end of the loop is the greatest common divisor. This iterative form is what the calculator uses, because it never builds a deep call stack regardless of how many reductions the algorithm performs. Even for two 30-digit numbers where the Euclidean algorithm might take nearly a hundred steps, the iterative version uses only a handful of variables.

Bézout's identity. For any two integers a and b with gcd g, there exist integers x and y such that ax + by = g. The coefficients x and y can be computed by working the Euclidean algorithm in reverse; this is the extended Euclidean algorithm, and it is the heart of the modular-inverse computation used in RSA cryptography and in the Chinese Remainder Theorem. The standard calculator on this page returns just g, but the steps shown are exactly the trace that the extended algorithm walks backwards to find x and y.

Least common multiple. The LCM has a clean identity in terms of the GCD: lcm(a, b) = |a × b| / gcd(a, b). This formula is useful because it reduces the LCM problem, which is hard to compute directly, to a GCD problem, which is fast. The trade-off is that for very large inputs you may need arbitrary-precision arithmetic to avoid overflowing a × b; the calculator's one-billion cap keeps the product within the safe-integer range, so ordinary JavaScript numbers suffice.

Coprimality. Two integers are coprime (or relatively prime, or mutually prime) when their GCD is 1. Coprime pairs are central to number theory: Fermat's little theorem and Euler's theorem both require the modulus and base to be coprime, and the RSA cryptosystem chooses its public exponent e to be coprime with (p − 1)(q − 1) specifically to guarantee that the modular inverse used for decryption exists.

Worked Examples

Example 1, Reducing a fraction. You are baking and need to scale a recipe that calls for 48 grams of one ingredient and 18 grams of another to a smaller batch. What is the largest common unit you can factor out?

1. Enter 48 for A and 18 for B.
2. Click Calculate.
3. The result reads gcd(48, 18) = 6.
4. The chain shows: gcd(48, 18) → gcd(18, 48 mod 18 = 12) → gcd(12, 18 mod 12 = 6) → gcd(6, 12 mod 6 = 0) → 6.
5. The LCM is 144, which is the smallest number divisible by both 48 and 18.
6. Interpretation: every 48 grams of the first ingredient corresponds to every 18 grams of the second, and the ratio simplifies to 8:3. The smallest pair of whole-number gram measurements that preserves the ratio is 8 and 3, scaled by 6.

Example 2, A coprime pair. Are 17 and 5 coprime?

1. Enter 17 for A and 5 for B.
2. Click Calculate.
3. The result reads gcd(17, 5) = 1, with the coprime chip highlighted.
4. The chain shows: gcd(17, 5) → gcd(5, 17 mod 5 = 2) → gcd(2, 5 mod 2 = 1) → gcd(1, 2 mod 1 = 0) → 1.
5. Interpretation: 17 and 5 share no common factor other than 1, which makes them coprime. This matters if you later need to find the modular inverse of 5 modulo 17 (it exists and is 7, since 5 × 7 = 35 = 2 × 17 + 1).

Example 3, A larger pair with several reductions. Find gcd(1071, 462).

1. Enter 1071 for A and 462 for B.
2. Click Calculate.
3. The result reads gcd(1071, 462) = 21.
4. The chain shows: gcd(1071, 462) → gcd(462, 1071 mod 462 = 147) → gcd(147, 462 mod 147 = 21) → gcd(21, 147 mod 21 = 0) → 21.
5. Interpretation: 1071 and 462 share exactly 21 as their largest common factor. The factorisations are 1071 = 3² × 7 × 17 and 462 = 2 × 3 × 7 × 11, and their intersection (the product of common primes with the minimum exponent) is 3 × 7 = 21.

Example 4, Edge case, one input is zero. Find gcd(0, 5).

1. Enter 0 for A and 5 for B.
2. Click Calculate.
3. The result reads gcd(0, 5) = 5.
4. The chain shows a single terminal step: gcd(5, 0) → 5.
5. Interpretation: every integer divides 0, but the largest integer that divides 5 is 5 itself. The convention gcd(a, 0) = |a| is universally adopted.

Example 5, The forbidden edge case, both inputs zero. Try gcd(0, 0).

1. Enter 0 for A and 0 for B.
2. Click Calculate.
3. The result panel is not shown; instead an error appears: "gcd(0, 0) is undefined, every integer divides zero, so there is no single greatest common divisor."
4. Interpretation: the calculation has no meaningful answer in this case. By convention, some software libraries return 0, others return NaN, and some throw an exception. The calculator refuses to give a single answer because it is mathematically undefined rather than merely difficult.

Where It Shows Up

• Simplifying fractions. Dividing numerator and denominator by their GCD produces the lowest terms. The fraction 48/18 reduces to 8/3 because gcd(48, 18) = 6 divides both. This is the single most common use of GCD in school mathematics.
• Computing the LCM. The formula lcm(a, b) = |a × b| / gcd(a, b) lets you compute the least common multiple by way of the GCD. LCM is used whenever you want to align repeating cycles, schedules with multiple periods, gear ratios, the resync point in audio loops.
• RSA and public-key cryptography. RSA keys are built from two large primes p and q. The public exponent e must be coprime with (p − 1)(q − 1), and the private exponent d is the modular inverse of e modulo (p − 1)(q − 1). Both of these checks rely on GCD computations, and the extended Euclidean algorithm is what finds d in the first place.
• Mesh-grid alignment and tiling. When you tile a rectangle with smaller rectangles, the dimensions of the master grid are constrained by the GCDs of the tile dimensions. If your tiles are 18 × 24 and 12 × 30, the GCDs (6 and 6) tell you that a 6-unit grid is the finest resolution at which the tiling pattern repeats.
• Gear, scale, and engineering problems. Two meshing gears with a and b teeth return to the same alignment after lcm(a, b) rotations. The number of distinct alignments before the system repeats equals lcm(a, b) / max(a, b), which is computed directly from the GCD.
• Polynomial and matrix arithmetic. Over a ring, the content of a polynomial (the GCD of its coefficients) is divided out to put it in primitive form. The Smith normal form of an integer matrix is built by repeated GCD operations on its entries.

Common Mistakes

• Trying to compute gcd(0, 0). Every integer divides zero, so there is no single greatest divisor. Some software libraries return 0 by convention, but mathematically the case is undefined. The calculator reports an error rather than picking an arbitrary answer.
• Confusing GCD with LCM. The GCD is the largest number that divides both inputs. The LCM is the smallest number that both inputs divide. They are related by gcd × lcm = a × b, but they are not the same value and they answer different questions.
• Using the recursive Euclidean algorithm with very large inputs. A naive recursive implementation will eventually overflow the call stack when the inputs are big enough that the algorithm runs for many iterations. The calculator uses the iterative form, which has no such limit.
• Forgetting to handle the b = 0 termination. If you write the Euclidean algorithm by hand and forget the while (b !== 0) guard, you will get an infinite loop or a divide-by-zero error. The base case gcd(a, 0) = a is what closes the algorithm.
• Computing the GCD of negative integers without taking absolute values. The Euclidean algorithm works on the absolute values of the inputs. If you pass −48 and 18, you should be computing gcd(48, 18) = 6, not −6. The calculator rejects negative inputs to avoid this confusion entirely.
• Assuming gcd(a, b) × lcm(a, b) = a × b always holds without absolute values. For positive inputs the identity holds exactly. For mixed-sign inputs, the LCM is conventionally taken as positive, and the identity becomes gcd(a, b) × lcm(a, b) = |a × b|.

Frequently Asked Questions

Q: What does GCD stand for, and what is it?

GCD stands for Greatest Common Divisor. It is the largest positive integer that divides two given integers without leaving a remainder. For example, gcd(12, 18) = 6 because 6 divides both 12 and 18 and no larger integer does. It is sometimes also called the greatest common factor (GCF) or the highest common factor (HCF).

Q: How does the Euclidean algorithm work?

The Euclidean algorithm repeatedly replaces the larger number with the remainder when the larger is divided by the smaller: gcd(a, b) = gcd(b, a mod b). Each step strictly decreases the second number, so the algorithm terminates with gcd(a, 0) = a. The number of steps is bounded by about five times the number of digits in the smaller input, which makes the algorithm extremely fast even for very large integers.

Q: Can the calculator handle very large inputs?

Yes, up to one billion (10^9). Both inputs are bounded to that range so that the LCM calculation |a × b| / gcd stays well within JavaScript's safe integer range. Numbers above that can be computed with arbitrary-precision libraries (Python's math.gcd, SymPy, GMP) but would not fit cleanly in a web-based result panel.

Q: What does it mean when the GCD is 1?

When gcd(a, b) = 1, the two numbers are coprime, they share no common divisor other than 1. Coprime pairs are important in modular arithmetic: any integer has a multiplicative inverse modulo n if and only if it is coprime with n. The calculator lights up a chip on the result panel whenever the input pair is coprime, so you can spot this property at a glance.

Q: What is the difference between GCD and LCM?

GCD is the largest integer that divides both inputs. LCM is the smallest integer that both inputs divide. They are duals of one another, related by the identity gcd(a, b) × lcm(a, b) = a × b. Use the GCD when you want to reduce something to its smallest representation (such as simplifying a fraction), and use the LCM when you want to find a common unit that both inputs fit into (such as aligning two periodic schedules).

Q: Why use the iterative algorithm instead of the recursive one?

The recursive Euclidean algorithm and the iterative one compute the same result. The iterative form, however, never grows the call stack regardless of how many reductions the algorithm performs. For very large inputs, particularly inputs chosen to be hard cases for the algorithm, the recursive form can exceed the call-stack limit and crash. The calculator's iterative implementation cannot run into that problem.

Q: Is there a connection between GCD and prime numbers?

Yes, a deep one. The Fundamental Theorem of Arithmetic says every integer greater than 1 is the product of primes in exactly one way (up to order). The GCD of two numbers is the product of every prime that appears in both factorisations, raised to the smaller exponent from each side. This is why coprime pairs have no prime factors in common, and why the GCD is in some sense "the intersection" of two numbers' prime decompositions.

Q: Can the calculator find more than two numbers' GCD?

Not directly, this page accepts exactly two inputs. To compute the GCD of a longer list, take the inputs pairwise: gcd(a, b, c) = gcd(gcd(a, b), c). The pairwise GCD is associative, so the order does not matter, and you can chain as many pairs as you like. The companion LCM calculator on this site accepts a list directly, which can be a faster way to handle three or more numbers at once.

References

• Euclid, Elements, Book VII, Propositions 1 to 2 (~300 BC). The original statement of the Euclidean algorithm for finding the greatest common divisor of two numbers. Still the canonical reference for the algorithm's classical form.
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (6th ed., Oxford University Press, 2008). The standard graduate-level introduction to number theory; Chapter 2 covers divisibility and the Euclidean algorithm in depth.
• Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed., Addison-Wesley, 1997). Section 4.5.2 covers the Euclidean algorithm, its analysis, the extended version, and binary GCD variants. The bound on the number of steps is proved here.
• Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography (CRC Press, 1996). Chapter 2 covers modular arithmetic, the extended Euclidean algorithm, and the computation of modular inverses, all of which rely on GCD computations.
• Christof Paar and Jan Pelzl, Understanding Cryptography (Springer, 2010). Chapter 6 walks through RSA step by step and shows where the GCD appears in key generation and primality testing.

Related Tools

• LCM Calculator, Compute the least common multiple of two or more integers and read the matching GCD at the same time. Useful for scheduling and gear-alignment problems.
• Prime Factorisation Calculator, Break any integer up to roughly 10^12 into its prime factors, and read the exponents for each prime. The GCD of two numbers is just the product of every prime that appears in both factorisations with the smaller exponent.
• Prime Checker, Test whether a single integer is prime. Useful when you need to confirm that one of your inputs to a GCD calculation is itself prime, which often makes the resulting GCD trivial.
• Fraction to Decimal Converter, Convert a fraction to its decimal representation and identify whether it terminates or repeats. Use the GCD first to simplify the fraction, then send it to this converter for the decimal form.