Extended Euclidean Algorithm Calculator

2026-10-07

Enter two integers to get their greatest common divisor and the Bézout coefficients x and y with a·x + b·y = gcd(a, b), together with every division step. The same page finds modular inverses and computes modular powers by square-and-multiply. All arithmetic uses exact big integers, so numbers with hundreds of digits work.

Extended Euclidean algorithm

Integers only: digits with an optional leading minus sign, no spaces or separators.

gcd(a, b)

x
y

Division steps

Row i holds the remainder r, and the coefficients s and t with r = |a|·s + |b|·t. From row 2 on, q is the quotient of the two remainders above it. The highlighted row, just before the remainder reaches 0, gives the gcd and the coefficients.

i	q	r	s	t	Result

Modular inverse

Finds the number inv in 0 … m − 1 with a × inv ≡ 1 (mod m).

Modulus m (2 or more)

Inverse of a modulo m

Modular exponentiation

Computes base^exponent mod m by square-and-multiply. A negative exponent works when the base has an inverse.

Base

Exponent

Modulus (1 or more)

base^exponent mod m

Step	Bit	Exponent so far	After squaring	After multiplying

Everything is calculated in your browser. Nothing you enter is sent to a server.

How to use the extended Euclidean algorithm calculator

In the first card, type two integers a and b. The gcd, the coefficients x and y, the identity with your numbers substituted and the division table update as you type.
Read the highlighted row of the table: its r, s and t are the gcd and the coefficients. The line below the result gives every solution (x, y) of the same equation.
In the second card, enter a and a modulus m of 2 or more. You get the inverse between 0 and m − 1, or a message explaining why none exists.
In the third card, enter a base, an exponent and a modulus. For exponents of up to 64 bits the table shows each squaring and multiplication; longer exponents show only the result.
Press Copy result to copy a card’s result as plain text, or Reset to example to restore the starting values. Your inputs are remembered in this browser.

How it works

For any two integers a and b that are not both zero, Bézout’s identity says there are integers x and y with:

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

The extended Euclidean algorithm finds such a pair while it computes the gcd. It starts with r0 = |a|, r1 = |b|, s0 = 1, s1 = 0, t0 = 0, t1 = 1 and repeats:

q = floor(r(i−1) / r(i))
r(i+1) = r(i−1) − q·r(i)
s(i+1) = s(i−1) − q·s(i)
t(i+1) = t(i−1) − q·t(i)

Here q is the integer quotient of the division, r the remainder, and s, t are the running coefficients. In every row r = |a|·s + |b|·t holds, so when the remainder reaches 0 the previous row contains the gcd and a valid pair. The number of divisions is at most five times the number of digits of the smaller input (Lamé’s theorem).

Signs and zero. The table works on the absolute values. If a is negative, x changes sign; if b is negative, y changes sign. The identity then holds for the numbers as typed. With b = 0 the result is gcd = |a|, x = ±1, y = 0. If both inputs are 0, the gcd is undefined and the tool says so. If a < b, the first division has quotient 0 and simply swaps the two numbers, so the coefficients come out swapped too.

All solutions. If (x, y) is one solution, every other one is x + k·b/g, y − k·a/g with g = gcd(a, b) and any integer k. To solve a·x + b·y = c for a multiple c of g, multiply both coefficients by c/g; if c is not a multiple of g, there is no integer solution.

Modular inverse. An inverse of a modulo m exists exactly when gcd(a, m) = 1. Then a·x + m·y = 1, so a·x ≡ 1 (mod m), and x reduced into 0 … m − 1 is the inverse. A negative a, or one that is at least m, is reduced modulo m first.

Modular exponentiation. The exponent is read in binary from the top bit. For each bit the running result is squared and reduced modulo m; if the bit is 1 it is also multiplied by the base and reduced again. The numbers never grow beyond m², and an exponent of n bits needs at most 2n multiplications instead of an astronomically large power. A negative exponent is handled as base⁻ⁿ = (base⁻¹)ⁿ, which needs the inverse from the second card.

Examples

Example 1: gcd and coefficients. For a = 240, b = 46 the tool returns gcd 2 with x = −9 and y = 47. Check: 240 × (−9) + 46 × 47 = −2160 + 2162 = 2. The general solution is x = −9 + 23k, y = 47 − 120k.

Example 2: a modular inverse. For a = 17 and m = 3120 the inverse is 2753, because 17 × 2753 = 46801 = 15 × 3120 + 1.

Example 3: no inverse. For a = 6 and m = 9 the gcd is 3, not 1, so the tool reports that no inverse exists. Indeed the multiples of 6 modulo 9 are only 0, 3 and 6, never 1.

Example 4: a modular power. 4¹³ mod 497: the exponent 13 is 1101 in binary, and the table gives the squared and multiplied values step by step, ending in 445. Computing 4¹³ = 67,108,864 first gives the same remainder, but that shortcut fails once the power has thousands of digits.

Where modular inverses are used

Modular inverses are the division of modular arithmetic. They appear when you solve a congruence such as 7x ≡ 3 (mod 26) (multiply by the inverse of 7, which is 15), when you decode an affine cipher, and in the key setup of RSA. Take the textbook toy values p = 61, q = 53, n = 3233, φ(n) = 3120 and public exponent e = 17. The private exponent is the inverse of 17 modulo 3120, which is 2753 (Example 2). Encrypting the message 65 gives 65¹⁷ mod 3233 = 2790, and 2790²⁷⁵³ mod 3233 returns 65. Real keys use primes of hundreds of digits; this page is for learning and checking, not for protecting data.

Common mistakes

Expecting a unique answer. The pair (x, y) is not unique. This tool shows the one the standard algorithm produces and the formula for all others.
Asking for an inverse when gcd is not 1. If a and m share a factor, no inverse exists, whatever method you use.
Forgetting to reduce. A negative a is first replaced by its remainder modulo m; the inverse of −3 modulo 11 is 7, because −3 ≡ 8 and 8 × 7 = 56 = 5 × 11 + 1.
Computing the power first. 2¹⁰⁰⁰ has 302 digits; reducing after every step keeps all numbers small.

Frequently asked questions

What is the extended Euclidean algorithm?

It is Euclid’s algorithm for the greatest common divisor with extra bookkeeping. Besides the gcd it returns integers x and y with a·x + b·y = gcd(a, b).

Why does my result differ from another source?

There are infinitely many valid pairs. Another source may list a different one, for example x + b/g and y − a/g. If your numbers satisfy the identity, they are correct.

When does a modular inverse exist?

Exactly when the number and the modulus are coprime, that is, when their gcd is 1. Modulo a prime, every number that is not a multiple of the prime has an inverse.

What does a negative exponent mean here?

base⁻ⁿ mod m is computed as the n-th power of the modular inverse of the base. If the base has no inverse modulo m, the tool tells you so.

How large can the numbers be?

Each input may have up to 1,000 digits. Very long division tables show only their first and last rows.

Is my data sent anywhere?

No. All calculations run in your browser. The values you type are kept only in this browser’s local storage so they are still there on your next visit; nothing is uploaded.

Related tools

GCF & LCM Calculator — greatest common factor, least common multiple and prime factorization.
Permutation & Combination Calculator — count arrangements and selections with exact big numbers.
Quadratic Equation Solver — roots, discriminant and vertex of a quadratic.
Two’s Complement Calculator — convert and add signed binary numbers.
Truth Table Generator — build truth tables for logical expressions.