Modular Arithmetic & Congruence Calculator
Calculate modular arithmetic operations, find modular inverses, and solve linear congruences. Covers the mathematics behind computer science and cryptography.
As an Amazon Associate and CJ Affiliate publisher we earn from qualifying purchases. Prices and availability may vary.
Modular Arithmetic Guide
What Is Modular Arithmetic?
a mod n = the remainder when a is divided by n. 17 mod 5 = 2 (17 = 3 × 5 + 2). 23 mod 7 = 2 (23 = 3 × 7 + 2). −1 mod 7 = 6 (not −1 — modular arithmetic uses positive remainders). Congruence notation: a ≡ b (mod n) means n divides (a − b). 17 ≡ 2 (mod 5) because 5 divides (17 − 2) = 15. The clock is the most intuitive modular arithmetic example: clocks operate modulo 12 (or 24). 15:00 ≡ 3:00 (mod 12). Day of the week cycles modulo 7.
What should I know about Modular Exponentiation?
Computing aᵇ mod n directly for large b is infeasible — but fast modular exponentiation solves it efficiently. Method: repeated squaring. To compute 2¹⁰ mod 7: 2¹ = 2. 2² = 4. 2⁴ = 16 ≡ 2 (mod 7). 2⁸ ≡ 4 (mod 7). 2¹⁰ = 2⁸ × 2² ≡ 4 × 4 = 16 ≡ 2 (mod 7). Fermats little theorem: if p is prime and gcd(a,p) = 1, then aᵖ⁻¹ ≡ 1 (mod p). This dramatically simplifies modular exponentiation for prime moduli. Used in: RSA encryption, digital signatures, Diffie-Hellman key exchange.
What should I know about Modular Inverse?
The modular inverse of a mod n is the value x such that ax ≡ 1 (mod n). Exists only if gcd(a, n) = 1 (a and n are coprime). Found using extended Euclidean algorithm. Example: 3⁻¹ mod 7: we need 3x ≡ 1 (mod 7). Test: 3×5 = 15 = 2×7 + 1 ≡ 1 (mod 7). So 3⁻¹ ≡ 5 (mod 7). Application: in RSA encryption, the private key exponent d is computed as d = e⁻¹ mod φ(n) — the modular inverse of the public exponent e modulo Euler's totient function of n.
What should I know about Cryptography Applications?
RSA encryption: select two large primes p and q. Compute n = pq (public key modulus). Choose public exponent e coprime to φ(n) = (p−1)(q−1). Private key d = e⁻¹ mod φ(n). Encrypt: c = mᵉ mod n. Decrypt: m = cᵈ mod n. Security: factoring n into p and q is computationally infeasible for large n (2048+ bits). Diffie-Hellman: two parties agree on a prime p and generator g. Each picks a secret a or b and computes gᵃ mod p or gᵇ mod p publicly. Shared secret: gᵃᵇ mod p — computed independently by both parties without ever transmitting the secret itself, which is the foundational idea behind secure key exchange over an insecure channel.