Computing GCD...
Ready to find the GCD
Enter two integers to compute the greatest common divisor, Bezout coefficients, LCM, and modular inverse.
What Is the Greatest Common Divisor (GCD)?
The greatest common divisor (GCD) of two integers is the largest positive integer that divides both of them without a remainder. It is also called the greatest common factor (GCF) or highest common factor (HCF). For example, the positive divisors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24, and 48. The positive divisors of 18 are 1, 2, 3, 6, 9, and 18. The divisors common to both lists are 1, 2, 3, and 6, so GCD(48, 18) = 6.
Listing all divisors works for small numbers, but it becomes impractical for large integers. The Euclidean algorithm computes the GCD efficiently using only division and remainders, and it works on numbers of any size. This calculator runs the full algorithm and shows every step so you can follow the working.
How the Euclidean Algorithm Works
The algorithm repeatedly replaces the larger number with the remainder of dividing it by the smaller, until the remainder is zero. The last non-zero remainder is the GCD.
Algorithm in plain English
- Start with two positive integers A and B.
- Divide A by B. Record the quotient and remainder R.
- Replace A with B, and replace B with R.
- Repeat from step 2 until B becomes zero.
- The last non-zero value of A is GCD(original A, original B).
The algorithm terminates because each remainder is strictly smaller than the previous one. In the worst case — consecutive Fibonacci numbers — it takes roughly log(min(A,B)) steps, making it extremely fast even for numbers with millions of digits.
What Is the Extended Euclidean Algorithm?
The Extended Euclidean Algorithm does everything the basic Euclidean algorithm does, but additionally computes two integers x and y called Bezout coefficients, such that:
A · x + B · y = GCD(A, B)
This equation is called Bezout's identity. For example, GCD(48, 18) = 6, and the Bezout coefficients are x = −1, y = 3 because 48 × (−1) + 18 × 3 = −48 + 54 = 6. These coefficients are not unique — there are infinitely many pairs — but the algorithm always returns the pair with the smallest absolute values.
The algorithm tracks two extra sequences alongside the standard division: the s-sequence and the t-sequence. These encode how each remainder can be expressed as a linear combination of the original two inputs. When the remainder reaches zero, the final s and t values are the Bezout coefficients x and y.
Back-Substitution — How Bezout Coefficients Are Derived
An alternative way to see Bezout's identity is back-substitution. Start from the GCD row and work upward, expressing the GCD in terms of earlier remainders.
Worked example: GCD(48, 18) = 6
From step 2: 6 = 18 − 1 × 12 Substitute 12 = 48 − 2 × 18 (from step 1): 6 = 18 − 1 × (48 − 2 × 18) 6 = 18 − 48 + 2 × 18 6 = 3 × 18 − 1 × 48 Therefore: (−1) × 48 + 3 × 18 = 6 → x = −1, y = 3
How to Find a Modular Inverse Using the Extended Euclidean Algorithm
If GCD(A, B) = 1, the numbers are coprime and a modular inverse of A mod B exists. The modular inverse is an integer i such that:
A · i ≡ 1 (mod B)
Because the Bezout coefficient x satisfies A·x + B·y = 1, taking both sides mod B gives A·x ≡ 1 (mod B). So x is the modular inverse of A mod B — just normalise it to the range [0, B−1] by computing ((x mod B) + B) mod B.
Modular inverses are fundamental in RSA encryption: the decryption exponent is the modular inverse of the encryption exponent modulo Euler's totient φ(n). They also appear in solving linear congruences, computing modular fractions, and number-theoretic transforms used in fast polynomial multiplication.
GCD and LCM: How They Are Related
The least common multiple (LCM) of two integers A and B is the smallest positive integer that is divisible by both. GCD and LCM are linked by a simple identity:
GCD(A, B) × LCM(A, B) = |A × B|
This means once you have the GCD, the LCM is free: LCM = |A × B| / GCD. For GCD(48, 18) = 6, the LCM is (48 × 18) / 6 = 864 / 6 = 144. LCM is used in adding fractions with different denominators, scheduling periodic events, and signal processing.
Applications in Cryptography and Number Theory
The Extended Euclidean Algorithm is a workhorse of modern cryptography and number theory. Here are its most important applications:
RSA Key Generation
The RSA private key d is the modular inverse of the public exponent e modulo φ(n). This inverse is computed using the Extended Euclidean Algorithm.
Simplifying Fractions
To simplify a/b, compute GCD(a, b) and divide both numerator and denominator by it. The result is the fraction in its lowest terms.
Linear Diophantine Equations
The equation Ax + By = C has integer solutions exactly when GCD(A, B) divides C. The Bezout coefficients give a particular solution, from which all solutions follow.
Number-Theoretic Transforms
Fast polynomial multiplication and signal processing use modular arithmetic in prime fields, where every non-zero element has a modular inverse found via the Extended Euclidean Algorithm.
GCD Calculator FAQ
What is the greatest common divisor of two numbers?
The greatest common divisor (GCD) of two integers is the largest positive integer that divides both of them exactly, leaving no remainder. It is also called the greatest common factor or highest common factor. GCD(12, 8) = 4 because 4 divides both 12 and 8, and no larger integer does.
How does the Euclidean algorithm find the GCD step by step?
Divide the larger number by the smaller and note the remainder. Replace the larger with the smaller and the smaller with the remainder. Repeat until the remainder is zero. The last non-zero remainder is the GCD. For GCD(48, 18): 48 ÷ 18 = 2 rem 12; 18 ÷ 12 = 1 rem 6; 12 ÷ 6 = 2 rem 0 → GCD = 6.
What does the Extended Euclidean Algorithm add over the basic version?
The basic Euclidean algorithm returns only the GCD. The extended version also returns Bezout coefficients x and y such that A·x + B·y = GCD. These coefficients are needed to compute modular inverses and to solve linear Diophantine equations.
What are Bezout's coefficients and how do I use them?
Bezout's coefficients x and y satisfy A·x + B·y = GCD(A, B). They are used to find modular inverses, to express the GCD as a linear combination of A and B, and to derive particular solutions to linear Diophantine equations. For GCD(48, 18) = 6, the coefficients are x = −1 and y = 3: 48 × (−1) + 18 × 3 = 6.
How do I find a modular inverse using the Extended Euclidean Algorithm?
A modular inverse of A mod B exists only when GCD(A, B) = 1. Run the Extended Euclidean Algorithm to get the Bezout coefficient x. Then normalise: inverse = ((x mod B) + B) mod B. For GCD(17, 13) = 1, x = −3, so the inverse of 17 mod 13 = ((−3 mod 13) + 13) mod 13 = 10. Verify: 17 × 10 = 170 = 13 × 13 + 1 ≡ 1 (mod 13).
What is the relationship between GCD and LCM?
GCD(A, B) × LCM(A, B) = |A × B|. Once the GCD is known, the LCM is computed as LCM = |A × B| / GCD. For example, LCM(48, 18) = (48 × 18) / 6 = 144. This avoids the need to find all multiples of both numbers.
When are two numbers coprime?
Two integers are coprime (or relatively prime) when their GCD equals 1. They do not need to be prime individually: 8 and 15 are both composite, but GCD(8, 15) = 1 because they share no prime factors. Coprimality is required for modular inverses to exist and is central to the Chinese Remainder Theorem.
Why is GCD(0, 0) undefined?
GCD(0, 0) would need to be the largest integer dividing both zero and zero. Every positive integer divides zero, so there is no largest such integer — the value would be unbounded. By convention, GCD(n, 0) = GCD(0, n) = n for any n ≥ 1, because n is the largest integer that divides both n and 0 (everything divides 0).
Related Calculators
Euler's Totient Calculator φ(n)
Count integers coprime to n with prime-factor formula and visual grid
Prime Factorisation Calculator
Decompose any integer into its prime factors with a factor tree
Modular Arithmetic Calculator
Compute modular addition, subtraction, multiplication, and exponentiation
Matrix Multiplier
Multiply matrices of any compatible dimensions with step-by-step working
Fibonacci Sequence Generator
Generate Fibonacci numbers — consecutive Fibonacci pairs give the worst-case GCD inputs
Significant Figures Calculator
Round numbers to a given number of significant figures with rules explained