What is a modular inverse?

The modular inverse of a modulo m is a number x such that a·x ≡ 1 (mod m). It exists only when gcd(a, m) = 1 (a and m are coprime). The inverse is computed with the extended Euclidean algorithm and is widely used in RSA encryption and solving modular equations.

What is modular exponentiation?

Modular exponentiation computes aᵇ mod m efficiently using the square-and-multiply algorithm. Naive computation would require multiplying enormous numbers, but this algorithm keeps intermediate results small by taking mod at every step, running in O(log b) multiplications.

What is the Chinese Remainder Theorem (CRT)?

CRT states that if m₁ and m₂ are coprime, any system x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂) has a unique solution mod (m₁·m₂). CRT is used in cryptography (RSA optimisation), calendar calculations, and fast polynomial multiplication.

What are Bézout coefficients?

For any integers a and b, the extended Euclidean algorithm finds integers x and y such that a·x + b·y = gcd(a, b). These are called Bézout coefficients. They prove gcd is a linear combination of a and b, and are the basis for computing modular inverses.

Modular Arithmetic Calculator - Mod, Power, Inverse & CRT

What is modular arithmetic?

Modular arithmetic studies the remainders left when integers are divided by a fixed number called the modulus. Writing a ≡ b (mod m) means a and b have the same remainder when divided by m. All integers from 0 to m−1 form a complete residue system mod m.

Supported operations

Basic mod: a mod m: always returns a value in [0, m−1].
Modular exponentiation: aᵇ mod m using fast square-and-multiply, running in O(log b) steps.
Modular inverse: a⁻¹ mod m via extended Euclidean algorithm. Requires gcd(a, m) = 1.
Extended GCD: gcd(a, b) plus Bézout coefficients x, y where a·x + b·y = gcd(a, b).
Chinese Remainder Theorem: Solve simultaneous congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂).

Applications

Cryptography: RSA key generation, Diffie-Hellman, elliptic curve cryptography all rely on modular arithmetic.
Hashing: Hash functions use mod to map large values into fixed-size buckets.
Calendars: Computing the day of the week uses modular arithmetic (mod 7).
Error detection: ISBN, IBAN, credit card checksums all use modular computations.

Clock arithmetic visual

The classic way to visualize modular arithmetic is a clock face. A 12-hour clock is arithmetic mod 12. If it is 9 o'clock and you add 8 hours, you don't get 17 - you get 17 mod 12 = 5. Similarly, 17 mod 12 = 5, meaning 17 and 5 are congruent mod 12.

Worked examples

Modular exponentiation: 3⁵ mod 7. Compute 3¹=3, 3²=9->2, 3⁴=4, 3⁵=3×4=12->5. Answer: 5.
Modular inverse: 3⁻¹ mod 7. Find x such that 3x ≡ 1 (mod 7). Test: 3×5=15=2×7+1 ->1 (mod 7). Answer: x = 5.
CRT: x ≡ 2 (mod 3) and x ≡ 3 (mod 5). Combined modulus = 15. Answer: x = 8 (check: 8 mod 3=2 ✓, 8 mod 5=3 ✓).

Fermat's Little Theorem

If p is prime and a is not divisible by p, then:

a^(p-1) ≡ 1 (mod p)

This is foundational to RSA encryption: it guarantees that the encryption and decryption exponents satisfy ed ≡ 1 (mod λ(n)), ensuring the message can be recovered. It also enables fast modular inverse: a⁻¹ ≡ a^(p−2) (mod p) when p is prime.