Modular Arithmetic
Modular inverses, huge powers, linear congruences and the Chinese remainder theorem.
7 × 15 ≡ 1 (mod 26)
Bézout: 7(-11) + 26(3) = 1
the true remainder, never negative
Modular arithmetic is arithmetic on remainders — clock arithmetic, where 10 + 5 is 3 rather than 15. Addition and multiplication carry over unchanged; division does not, and a ÷ b becomes a × b⁻¹, which exists only when gcd(b, n) = 1.
What survives, and what does not
Working modulo n, two numbers are treated as the same when they differ by a multiple of n. Addition, subtraction and multiplication all pass through that identification cleanly: you can reduce at any point without changing the answer, which is what makes huge computations tractable.
Division is where the analogy breaks. There is no general “divide by 3” modulo 12, because 3 × 4 and 3 × 8 both give 0, so the operation cannot be undone. What replaces it is the modular inverse: b⁻¹ is the number with b × b⁻¹ ≡ 1, and it exists precisely when b shares no factor with n. Modulo 26 — the alphabet, and so the affine cipher — the invertible multipliers are exactly the twelve numbers coprime to 26, which is why a cipher key cannot be even or 13.
Why the exponent is not just a big number
Computing 7¹⁰⁰ mod 13 by working out 7¹⁰⁰ first is hopeless: it has 85 digits, and in floating point the answer comes back confidently wrong. Repeated squaring instead reduces after every step, so nothing ever exceeds n², and the whole thing takes about as many multiplications as the exponent has bits. This page uses exact integers throughout, so nothing overflows however large the input.
ax ≡ b (mod n) has gcd(a, n) solutions when that gcd divides b, and none otherwise
- 1 Check that an inverse exists. Run the Euclidean algorithm on a and n. If the gcd is anything but 1, there is no inverse.
- 2 Run it again, keeping track. The extended version records how each remainder was built, giving integers x and y with ax + ny = gcd.
- 3 Read the inverse off. Taking that equation modulo n kills the ny term, leaving ax ≡ 1, so x is the inverse.
- 4 Reduce it into range. x may come out negative; add n until it lands between 0 and n − 1.
- 5 Check by multiplying back. For 7 modulo 26: 7 × 15 = 105 = 4 × 26 + 1, so 15 is the inverse.
Which numbers are invertible modulo 26
Only those coprime to 26 — twelve of them, which is φ(26). This is why an affine cipher key must be one of these.
| a | gcd(a, 26) | Inverse mod 26 |
|---|---|---|
| 3 | 1 | 9 |
| 5 | 1 | 21 |
| 7 | 1 | 15 |
| 11 | 1 | 19 |
| 2 | 2 | none — shares a factor with 26 |
| 13 | 13 | none — 13 divides 26 |
The Chinese remainder theorem
Given several congruences with different moduli, the theorem says a common solution exists and is unique modulo the product — provided the moduli are pairwise coprime. The classical example asks for a number leaving remainder 2 on division by 3, 3 by 5 and 2 by 7; the answer is 23, and every other solution differs from it by a multiple of 105.
The coprimality condition is usually stated as a requirement, but it is really only a requirement for the guarantee. When moduli share factors a solution may still exist — it just has to be consistent on the overlap. x ≡ 1 (mod 4) and x ≡ 3 (mod 6) both demand x be odd and are compatible; x ≡ 1 (mod 4) and x ≡ 2 (mod 6) are not, since one wants odd and the other even. This page merges the congruences pairwise, so it handles both cases and says which one you have.
Where this all goes is cryptography. RSA is modular exponentiation with a modulus that is a product of two primes; the decryption exponent is a modular inverse; and implementations use the Chinese remainder theorem to work modulo each prime separately, which is several times faster. The tools on this page are small, but they are the actual operations involved.