Modular Arithmetic

The basics

Modular arithmetic is integer arithmetic where you only care about remainders modulo n. Numbers that have the same remainder mod n are equivalent (≡):

17 ≡ 7  (mod 5)        because both have remainder 2
17 ≡ -3 (mod 5)        same remainder modulo 5
17 ≡ 2  (mod 5)        canonical representative

The set of equivalence classes is denoted ℤ/nℤ or ℤₙ. For mod 5, there are 5 classes — {..., -10, -5, 0, 5, 10, ...}, {..., -9, -4, 1, 6, 11, ...}, etc. Each class is denoted by its smallest non-negative representative — 0, 1, 2, 3, 4.

Arithmetic operations

Addition, subtraction, and multiplication of equivalence classes are well-defined:

(a mod n) + (b mod n) = (a + b) mod n
(a mod n) · (b mod n) = (a · b) mod n
(a mod n) - (b mod n) = (a - b) mod n

So you can do arithmetic and reduce mod n at any point — answer is the same. This is what makes modular arithmetic computationally tractable for huge numbers — keep reducing along the way.

Division is trickier. a/b mod n requires the modular inverse of b — denoted b⁻¹ — which exists iff gcd(b, n) = 1. Then a/b ≡ a · b⁻¹ (mod n).

Modular inverses

The modular inverse of a mod n is x such that:

a · x ≡ 1 (mod n)

Exists iff gcd(a, n) = 1. Computed via the Extended Euclidean Algorithm:

find x, y such that a·x + n·y = gcd(a, n) = 1
then a·x ≡ 1 (mod n), so x is the inverse

Example — find 7⁻¹ mod 26. Extended Euclidean gives 7·15 + 26·(-4) = 1. So 7⁻¹ ≡ 15 (mod 26). Verify — 7·15 = 105 = 4·26 + 1 ≡ 1 (mod 26). ✓

Modular inverses are used in RSA decryption (compute private key from public key + φ(n)), affine ciphers (decrypt by multiplying by inverse), and many number-theoretic algorithms.

Fermat's Little Theorem

For a prime p and an integer a with gcd(a, p) = 1:

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

Equivalently, a^p ≡ a (mod p) for any integer a (no coprimality needed).

Examples — 2^4 = 16 ≡ 1 (mod 5). 3^4 = 81 = 16·5 + 1 ≡ 1 (mod 5). 7^6 ≡ 1 (mod 7) trivially since 7 ≡ 0 (mod 7); but the form a^p ≡ a still holds — 7^7 = 823543 ≡ 7 (mod 7), which is 0.

Used in:

• Fast modular exponentiation — to compute a^k mod p, you only need k mod (p-1).
• Primality testing — pick random a; compute a^(p-1) mod p; if not 1, p is composite (Fermat primality test).
• Generating random elements with known properties in finite groups.

Euler's theorem

Generalization of Fermat. For coprime a and n:

a^(φ(n)) ≡ 1 (mod n)

where φ(n) is Euler's totient — the number of integers from 1 to n coprime to n. For prime p, φ(p) = p − 1, recovering Fermat's Little Theorem.

For a product of two distinct primes (n = pq), φ(n) = (p−1)(q−1). This is the foundation of RSA — the decryption key d satisfies ed ≡ 1 (mod φ(n)), so d is the modular inverse of e mod φ(n).

Modular exponentiation

Computing a^b mod n efficiently — without computing a^b directly, which would overflow.

function modPow(base, exp, mod) {
  let result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 === 1) result = (result * base) % mod;
    exp = Math.floor(exp / 2);
    base = (base * base) % mod;
  }
  return result;
}

modPow(7, 100, 13);  // 9 — computes 7^100 mod 13 quickly

Square-and-multiply takes O(log exp) multiplications instead of exp multiplications. Foundation of all modern public-key crypto — encrypt/decrypt millions-bit numbers in milliseconds.

JavaScript — modular arithmetic functions

// Always-positive modulo (handles negative numbers correctly)
function mod(a, n) {
  return ((a % n) + n) % n;
}

// Modular inverse via Extended Euclidean
function modInverse(a, n) {
  let [old_r, r] = [a, n];
  let [old_s, s] = [1, 0];
  while (r !== 0) {
    const q = Math.floor(old_r / r);
    [old_r, r] = [r, old_r - q * r];
    [old_s, s] = [s, old_s - q * s];
  }
  if (old_r !== 1) return null;  // inverse doesn't exist
  return mod(old_s, n);
}

// Modular exponentiation (above)

// Test Fermat's Little Theorem on a few primes
const p = 13;
for (let a = 2; a < p; a++) {
  console.log(`${a}^${p-1} mod ${p} =`, modPow(a, p - 1, p));  // all 1
}

// Modular division
function modDiv(a, b, n) {
  const inv = modInverse(b, n);
  if (inv === null) return null;
  return mod(a * inv, n);
}

modDiv(7, 3, 11);  // 7/3 mod 11 — 3⁻¹ mod 11 = 4, so answer is 7·4 = 28 ≡ 6 (mod 11)

Where modular arithmetic appears

• Cryptography. RSA, Diffie-Hellman, ElGamal, ECC — all built on modular arithmetic with large primes. Modular exponentiation is the inner loop.
• Hash functions. Hash table indices computed via mod(hash, table_size). Cyclic redundancy checks (CRC) are polynomial divisions in finite fields.
• Random number generation. Linear congruential generators — x_{n+1} = (a · x_n + c) mod m. Mersenne Twister mixes bits with mod operations.
• Calendar / date arithmetic. Days of the week — mod 7. Months — mod 12. Leap years — mod 4 (with exceptions for centuries). Zeller's congruence is a famous mod-based date formula.
• Parity and bit manipulation. Even/odd is mod 2. Many bit-tricks (counting set bits, reversing bytes) work mod powers of 2 in disguise.
• Number theory. Prime testing (Fermat, Miller-Rabin), discrete logarithm, factorization, finite fields, p-adic numbers — all involve modular arithmetic.
• Coding theory. Error-correcting codes (Reed-Solomon, BCH) work over finite fields of prime characteristic — modular arithmetic at the bit level.

Common mistakes

• Negative modulo confusion. JavaScript's -3 % 5 is −3, not 2. C, Java, JavaScript all return signed mod; Python returns positive (-3 % 5 = 2). Use ((a % n) + n) % n to always get non-negative.
• Trying to invert without checking gcd. a⁻¹ mod n only exists if gcd(a, n) = 1. Forgetting this gives wrong results when the inverse doesn't exist.
• Computing a^b directly before mod. For huge b, a^b overflows. Use modular exponentiation (square-and-multiply) instead.
• Confusing congruence with equality. a ≡ b (mod n) doesn't mean a = b. It means n divides (a − b). Don't substitute one for the other in non-modular contexts.
• Forgetting that division requires inversibility. a/b mod n needs b to have an inverse mod n. If gcd(b, n) ≠ 1, you can't divide. Some operations (Chinese Remainder, partial inverses) need this checked carefully.
• Off-by-one in Fermat's Little Theorem exponent. a^(p−1) ≡ 1 (mod p), not a^p. Easy to swap.