Skip to content

Modular Arithmetic

Work modulo \(m\): wrap values to \([0, m-1]\). Essential to avoid overflow and for cryptography-style problems.

Basics

[ (a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m ] [ (a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m ]

Subtraction: \((a - b) \bmod m = (a \bmod m - b \bmod m + m) \bmod m\).

Modular inverse

\(x\) such that \(a x \equiv 1 \pmod{m}\) exists iff \(\gcd(a,m)=1\).

  • Fermat: if \(m\) is prime, \(a^{-1} \equiv a^{m-2} \pmod{m}\) (binary exponentiation).
  • Extended Euclidean algorithm for general coprime \(a, m\).
long long modPow(long long a, long long e, long long mod) {
    long long r = 1 % mod;
    a %= mod;
    while (e) {
        if (e & 1) r = r * a % mod;
        a = a * a % mod;
        e >>= 1;
    }
    return r;
}

long long modInvFermat(long long a, long long p) { return modPow(a, p - 2, p); } // p prime

Chinese Remainder Theorem (sketch)

If moduli are pairwise coprime, a system of congruences has a unique solution modulo the product—combine with Garner’s algorithm or constructive CRT.