Modular Arithmetic
Congruence
| Property | Statement |
|---|---|
| Addition | (a+b) mod m |
| Multiplication | (ab) mod m |
| Inverse | ax≡1 (mod m) if gcd(a,m)=1 |
Examples
Example 1. 17 mod 5.
Solution. 17=3·5+2, so 17≡2 (mod 5).
In Depth
Modular arithmetic is arithmetic on a 'clock' — numbers wrap around after reaching the modulus \(m\). It is the foundation of number theory and modern cryptography. The integers mod \(m\), written \(\mathbb{Z}/m\mathbb{Z}\), form a ring; when \(m\) is prime, they form a field.
The multiplicative group \((\mathbb{Z}/m\mathbb{Z})^*\) consists of residues coprime to \(m\) and has order \(\varphi(m)\). Fermat's little theorem and Euler's theorem describe the structure of this group. Discrete logarithms in this group — finding \(x\) such that \(g^x\equiv a\pmod{m}\) — are computationally hard, forming the basis of Diffie–Hellman key exchange.
The Chinese Remainder Theorem shows that \(\mathbb{Z}/mn\mathbb{Z}\cong\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\) when \(\gcd(m,n)=1\). This isomorphism is used in fast arithmetic (splitting large computations into smaller ones) and in the RSA algorithm.
Further Reading & Context
Modular arithmetic is the arithmetic of remainders. The integers modulo \(n\) form a ring \(\mathbb{Z}/n\mathbb{Z}\) with \(n\) elements. When \(n=p\) is prime, this ring is a field — every nonzero element has a multiplicative inverse. Finite fields \(\mathbb{F}_p\) are the simplest examples of fields with finitely many elements.
Fast modular exponentiation (square-and-multiply) computes \(a^k\bmod n\) in \(O(\log k)\) multiplications. Write \(k\) in binary; square for each bit, multiply by \(a\) for each 1-bit. This is essential for RSA, Diffie–Hellman, and primality testing.
Montgomery multiplication avoids expensive division in modular arithmetic by working in a transformed representation. It is used in hardware implementations of RSA and ECC, where modular reductions must be performed billions of times per second.
The discrete logarithm problem (DLP): given \(g^x\equiv h\pmod{p}\), find \(x\). The best classical algorithms (index calculus, NFS) run in subexponential time. The DLP is the basis of Diffie–Hellman key exchange and ElGamal encryption.
Modular arithmetic appears throughout mathematics: in the theory of elliptic curves (points are computed modulo a prime), in coding theory (Reed–Solomon codes use arithmetic over finite fields), in combinatorics (counting problems modulo a prime), and in the analysis of hash functions and pseudorandom generators.