Modular arithmetic calculator

What each operation computes§

• a mod n: the remainder after dividing a by n, always between 0 and n − 1. For negative a this is the mathematical remainder: −7 mod 5 = 3, because −7 = −2 × 5 + 3^[1].
• a + b, a − b, a × b (mod n): the ordinary result, reduced mod n. Reducing first gives the same answer, which is why clock arithmetic works^[1].
• a^b mod n: by square-and-multiply. The exponent is written in binary; each binary digit squares the running value and each 1 multiplies it by a, reducing mod n every time^[1]. An exponent with 1000 binary digits needs at most about 2000 multiplications. The table shows every step for exponents up to 40 binary digits.
• a⁻¹ mod n: the number x with a·x ≡ 1 (mod n), found by the extended Euclidean algorithm. It exists exactly when gcd(a, n) = 1; otherwise the calculator says there is no inverse and shows the gcd^[1].
• gcd(a, b): the greatest common divisor, by Euclid's algorithm, with the table of remainders.

All numbers may have up to 400 digits, may be typed with spaces or commas, and may be negative (except the modulus and the exponent). Results are exact: the arithmetic uses whole numbers of unlimited size, never floating point.

Worked examples§

7¹⁰⁰⁰ mod 13 = 9. 1000 in binary is 1111101000: nine squarings and five multiplications. As a check, Fermat's little theorem says 7¹² ≡ 1 (mod 13), and 1000 = 83 × 12 + 4, so 7¹⁰⁰⁰ ≡ 7⁴ = 2401 = 184 × 13 + 9.

17⁻¹ mod 3120 = 2753. 17 × 2753 = 46,801 = 15 × 3120 + 1. This is the private exponent of the RSA example on the RSA calculator page.

4⁻¹ mod 10 does not exist. gcd(4, 10) = 2, and every multiple of 4 is even, so none leaves remainder 1 on division by 10.

Sources

1. Victor Shoup (2008). A Computational Introduction to Number Theory and Algebra, 2nd edition (Version 2, free PDF). Cambridge University Press. ISBN 9780521516440. textbook