Inputs

a\,x + b\,y = \gcd(a,b)

Integer a

Integer b

Integers of up to 40 digits, with optional sign.

Examples

GCD(a, b)

LCM(a, b)

5520

Coefficient x

−9

Coefficient y

Bézout identity

240·(−9) + 46·47 = 2

Derivation & verification

Successive divisions

240 = 5·46 + 10

46 = 4·10 + 6

10 = 1·6 + 4

6 = 1·4 + 2

4 = 2·2 + 0

Back-substitution

2 = 1·6 − 1·4

2 = (−1)·10 + 2·6

2 = 2·46 − 9·10

2 = (−9)·240 + 47·46

Verification

Identity a·x + b·y = gcd

−2160 + (2162) = 2

The GCD divides both integers

2 | 240 ∧ 2 | 46

gcd · lcm = |a·b|

2 · 5520 = 11040

Fundamentals & Explanation

The Euclidean Algorithm

The Euclidean algorithm computes the greatest common divisor (GCD) of two integers through successive divisions. It rests on a single observation: every common divisor of a and b also divides the remainder of dividing a by b. Since remainders strictly decrease, the process always terminates, and the last nonzero remainder is the GCD.

Algorithm invariant

\gcd(a,b) = \gcd(b,\; a \bmod b)

The extended version and the Bézout identity

The extended version of the algorithm does more than find the GCD: it walks through the same divisions while keeping track of how each remainder combines the original integers. The result is a pair of integer coefficients x and y that certify the GCD as a linear combination of a and b:

Bézout identity

a\,x + b\,y = \gcd(a,b)

The classic classroom presentation reconstructs this identity by back-substitution: the GCD is isolated from the last useful division and earlier remainders are replaced one by one. The tool shows that full derivation, together with the extended table (r, q, x, y) that performs the same computation forwards.

Linear Diophantine equations

A linear Diophantine equation asks for integer solutions of ax + by = c. The solvability criterion is direct: a solution exists if and only if gcd(a, b) divides c. In that case, scaling the Bézout identity by c/g yields a particular solution, and every other solution is reached by sliding along the line:

Complete family of solutions

x = x_0 + \tfrac{b}{g}\,t, \qquad y = y_0 - \tfrac{a}{g}\,t, \qquad t \in \mathbb{Z}

Linear congruences and the modular inverse

The congruence ax ≡ b (mod n) is the same Diophantine equation in disguise: ax − ny = b. With g = gcd(a, n), a solution exists if and only if g divides b; and when it does, there are exactly g solution classes modulo n, spaced n/g apart. The case g = 1 is the most important one: the solution is unique and is obtained by multiplying by the modular inverse a⁻¹, which is precisely the solution of ax ≡ 1 (mod n) and falls out of the extended algorithm for free.

How to use the tool

GCD & Bézout: enter two integers (negatives and zero allowed) to get the GCD, LCM, coefficients x and y, the successive divisions, the back-substitution and the full numeric verification.
Linear Diophantine: solve ax + by = c with an explicit solvability criterion, a canonical particular solution and the complete family parameterized by t.
Linear congruence: solve ax ≡ b (mod n) with a visible canonical reduction, every solution class (or its parametric form) and the modular inverse when it exists.
Exact arithmetic: all computations use arbitrary-precision integers (up to 40 digits per input); no step involves rounding.

Module conventions

Zero cases

gcd(a, 0) = |a| and gcd(0, 0) = 0 (standard convention); lcm(a, 0) = 0. The GCD is always reported as non-negative.

Canonical solutions

In the Diophantine mode, the particular solution is normalized to 0 ≤ x₀ < |b/g|; in the congruence mode, a and b are first reduced to the range [0, n). This makes results unique and reproducible.

Class enumeration

A congruence with g classes is fully enumerated up to g = 12; beyond that, the parametric form x ≡ x₀ (mod n/g), which describes all of them, is shown instead.

The worst case: Fibonacci

Lamé's theorem (1844) — regarded as the first complexity analysis of an algorithm — shows that the worst case of the Euclidean algorithm occurs with consecutive Fibonacci numbers: the number of divisions never exceeds five times the number of decimal digits of the smaller operand.

With the 40-digit limit of this tool, the longest possible derivation is around 190 divisions (for instance, two consecutive 40-digit Fibonacci numbers), all of which the table displays.

References

Euclid, Elements, Book VII, Propositions 1–2 (c. 300 BC) — the original formulation by repeated subtraction.
Bachet, C.-G. (1624). Problèmes plaisants et délectables — first complete solution of the linear equation in integers; the identity is named after Bézout for his later generalization to polynomials.
Lamé, G. (1844). "Note sur la limite du nombre des divisions…". C. R. Acad. Sci. Paris, 19, 867–870.
Niven, I., Zuckerman, H. S. & Montgomery, H. L. (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley — ch. 1–2.
Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2, §4.5.2 — analysis of the Euclidean algorithm and its extended version.

Extended Euclidean Algorithm: GCD, Bézout & Congruences

Inputs

Examples

Bézout identity

Derivation & verification

Successive divisions

Back-substitution

Verification

Fundamentals & Explanation

The Euclidean Algorithm

The extended version and the Bézout identity

Linear Diophantine equations

Linear congruences and the modular inverse

How to use the tool

Module conventions

The worst case: Fibonacci

References

The Euclidean Algorithm

The extended version and the Bézout identity

Linear Diophantine equations

Linear congruences and the modular inverse

How to use the tool

Module conventions

The worst case: Fibonacci

References