Modular Arithmetic & Congruence Calculator

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.

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.

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.

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