Find the greatest common divisor of two integers, the Bézout coefficients with a·x + b·y = gcd(a, b), and the modular inverse of a number, with every division step in a table.
The Euclidean algorithm finds the greatest common divisor of two integers by repeated division. It relies on the fact that gcd(a, b) = gcd(b, a mod b). Starting with a and b, replace the pair by (b, remainder) until the remainder is 0; the last non-zero remainder is the gcd. For example, gcd(240, 46): 240 = 5·46 + 10, 46 = 4·10 + 6, 10 = 1·6 + 4, 6 = 1·4 + 2, 4 = 2·2 + 0, so the gcd is 2.
The extended algorithm keeps track of two more sequences while it divides, so that every remainder is written as a combination of the original numbers. At the end it produces integers x and y with a·x + b·y = gcd(a, b). This statement is Bézout's identity. The coefficients are not unique, and the calculator verifies the identity for the pair it reports.
A modular inverse of a modulo m is a number x with a·x ≡ 1 (mod m). It exists exactly when gcd(a, m) = 1. In that case the Bézout identity reads a·x + m·y = 1, and reducing modulo m shows that x is the inverse. This is the step that computes the private exponent in RSA and the key inverses in the Affine and Hill ciphers.
If gcd(a, m) is greater than 1, the calculator explains that no inverse exists. For example, 6 has no inverse modulo 9 because gcd(6, 9) = 3.
Each row shows the quotient q, the remainder r and the coefficients s and t satisfying r = s·a + t·b. The last non-zero row gives the gcd together with x = s and y = t. Negative inputs are accepted: the gcd is always non-negative, and the signs of x and y adjust to match.
The algorithm is fast: the number of division steps is at most about five times the number of decimal digits of the smaller input (Lamé's theorem), and the worst case occurs for consecutive Fibonacci numbers. That is why it works comfortably on the 300-digit numbers used in RSA.
These examples are computed by the same engine as the calculator above, so you can compare each step with your own working.
| i | q | r | s | t |
|---|---|---|---|---|
| 0 | — | 240 | 1 | 0 |
| 1 | — | 46 | 0 | 1 |
| 2 | 5 | 10 | 1 | -5 |
| 3 | 4 | 6 | -4 | 21 |
| 4 | 1 | 4 | 5 | -26 |
| 5 | 1 | 2 | -9 | 47 |
| 6 | 2 | 0 | 23 | -120 |
Mainly to compute modular inverses and Bézout coefficients. It is a key step in RSA key generation, in solving linear congruences and in the Chinese Remainder Theorem.
Run the extended Euclidean algorithm on (a, m). If the gcd is 1, the coefficient of a in a·x + m·y = 1, reduced modulo m, is the inverse. If the gcd is not 1, no inverse exists.
No. If (x, y) works, so does (x + k·b/g, y − k·a/g) for any integer k. The algorithm returns one particular pair.
It equals the absolute value of a. The gcd of 0 and 0 is undefined.
Greatest common divisor and least common multiple of up to eight integers, with Euclid's algorithm and prime factorization.
Add, subtract, multiply, divide and exponentiate modulo m, find modular inverses and solve ax ≡ b (mod m).
Solve a system of congruences x ≡ a (mod m), including moduli that are not coprime, with every merge step shown.
Generate an RSA key pair from two primes and encrypt or decrypt an integer, with every calculation shown.