5.2 Modular Arithmetic

Modular arithmetic is a system for working with remainders after division. It simplifies calculations involving large numbers by confining everything to a fixed range of integers, and it's the mathematical foundation behind cryptographic systems like RSA, clock arithmetic, and hashing algorithms.

Modular Arithmetic Fundamentals

Understanding Modular Arithmetic and Congruence

Think of a 12-hour clock. After 12 o'clock, you don't go to 13; you wrap back around to 1. That's modular arithmetic in action: you work within a fixed range of integers, and when you hit the modulus, you wrap around.

The formal notation uses the congruence symbol ≡. Two integers $a$ and $b$ are congruent modulo $m$ if $m$ divides their difference. You write this as:

$a \equiv b \pmod{m}$

This means $a$ and $b$ leave the same remainder when divided by $m$. For example, $17 \equiv 5 \pmod{12}$ because $17 - 5 = 12$, which is divisible by 12. Both 17 and 5 leave a remainder of 5 when divided by 12.

Modular addition and modular multiplication work the way you'd expect: perform the operation, then take the remainder when dividing by the modulus.

• Addition: $(7 + 8) \bmod 12 = 15 \bmod 12 = 3$
• Multiplication: $(7 \times 8) \bmod 12 = 56 \bmod 12 = 8$

A useful shortcut: you can reduce each operand mod $m$ before you multiply or add. This keeps numbers small throughout a calculation.

Properties and Applications of Modular Arithmetic

Modular arithmetic preserves the core properties you rely on from regular arithmetic:

• Commutative: $a + b \equiv b + a$ and $a \cdot b \equiv b \cdot a \pmod{m}$
• Associative: $(a + b) + c \equiv a + (b + c) \pmod{m}$
• Distributive: $a \cdot (b + c) \equiv a \cdot b + a \cdot c \pmod{m}$

These properties mean you can rearrange and simplify modular expressions using the same algebraic moves you already know.

Congruence classes group all integers that share the same remainder for a given modulus. For mod 3, the congruence classes are $\{..., -3, 0, 3, 6, ...\}$, $\{..., -2, 1, 4, 7, ...\}$, and $\{..., -1, 2, 5, 8, ...\}$. Every integer belongs to exactly one class.

Practical applications show up everywhere: hashing algorithms map data to fixed-size outputs using mod, digital clocks display time mod 12 (or mod 24), and computer memory addressing uses mod to wrap around available address space.

Multiplicative Inverses in Modular Arithmetic

The multiplicative inverse of $a$ modulo $m$ is a value $a^{-1}$ such that:

$a \cdot a^{-1} \equiv 1 \pmod{m}$

This inverse exists if and only if $a$ and $m$ are coprime (i.e., $\gcd(a, m) = 1$). If they share a common factor greater than 1, no inverse exists.

For example, the inverse of 3 mod 7: you need $3x \equiv 1 \pmod{7}$. Testing values, $3 \times 5 = 15 \equiv 1 \pmod{7}$, so $3^{-1} \equiv 5 \pmod{7}$.

For larger numbers, you compute the inverse using the extended Euclidean algorithm, which finds integers $x$ and $y$ satisfying $ax + my = \gcd(a, m)$. When $\gcd(a, m) = 1$, the coefficient $x$ (reduced mod $m$) is your inverse.

Multiplicative inverses are essential in cryptography for computing private keys and for guaranteeing unique solutions to linear congruences of the form $ax \equiv b \pmod{m}$.

Modular Exponentiation and Theorems

Efficient Modular Exponentiation Techniques

Computing $a^b \bmod m$ directly by multiplying $a$ by itself $b$ times is impractical when $b$ is hundreds of digits long. The square-and-multiply algorithm (also called binary exponentiation or repeated squaring) solves this by using the binary representation of the exponent.

Here's the process for computing $a^b \bmod m$:

1. Write $b$ in binary. For example, $b = 13$ becomes $1101_2$.

2. Start with a result of 1.

3. Scan the binary digits from left to right. For each bit:

   • Square the current result (mod $m$).
   • If the bit is 1, multiply the result by $a$ (mod $m$).

4. After processing all bits, the result is $a^b \bmod m$.

Worked example: Compute $3^{13} \bmod 7$. Binary of 13 is $1101$.

So $3^{13} \bmod 7 = 3$. (You can verify: by Fermat's Little Theorem, $3^6 \equiv 1 \pmod{7}$, so $3^{13} = 3^{12} \cdot 3 = (3^6)^2 \cdot 3 \equiv 1 \cdot 3 = 3$.)

The time complexity is $O(\log b)$ multiplications, which makes this feasible even for the enormous exponents used in RSA encryption.

Fermat's Little Theorem and Its Applications

Fermat's Little Theorem states: if $p$ is prime and $\gcd(a, p) = 1$, then

$a^{p-1} \equiv 1 \pmod{p}$

An equivalent form that works for any integer $a$ (including multiples of $p$) is $a^p \equiv a \pmod{p}$.

This theorem is useful in several ways:

• Simplifying large exponents: To compute $2^{100} \bmod 13$, note that $2^{12} \equiv 1 \pmod{13}$ by Fermat's Little Theorem. Since $100 = 12 \times 8 + 4$, you get $2^{100} \equiv 2^4 = 16 \equiv 3 \pmod{13}$.
• Finding modular inverses: When $p$ is prime, $a^{-1} \equiv a^{p-2} \pmod{p}$. This follows directly from the theorem since $a \cdot a^{p-2} = a^{p-1} \equiv 1$.
• Probabilistic primality testing: If $a^{n-1} \not\equiv 1 \pmod{n}$ for some $a$, then $n$ is definitely not prime. If the congruence holds for many random values of $a$, then $n$ is probably prime. (This is the basis of the Fermat primality test, though Carmichael numbers can fool it.)

Euler's Totient Function and Related Concepts

Euler's totient function $\phi(n)$ counts how many integers from 1 to $n-1$ are coprime to $n$.

Key formulas for computing $\phi(n)$:

• For a prime $p$: $\phi(p) = p - 1$ (every number from 1 to $p-1$ is coprime to a prime)
• For a prime power: $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$
• For coprime integers $a$ and $b$: $\phi(ab) = \phi(a) \cdot \phi(b)$ (this is the multiplicative property)

For example, $\phi(12) = \phi(4) \cdot \phi(3) = 2 \cdot 2 = 4$. The four integers coprime to 12 in the range 1–11 are: 1, 5, 7, 11.

Euler's theorem generalizes Fermat's Little Theorem to any modulus: if $\gcd(a, n) = 1$, then

$a^{\phi(n)} \equiv 1 \pmod{n}$

When $n$ is prime, $\phi(n) = n - 1$, so this reduces to Fermat's Little Theorem exactly.

In the RSA cryptosystem, Euler's theorem is what makes decryption work. The public and private key exponents $e$ and $d$ are chosen so that $ed \equiv 1 \pmod{\phi(n)}$, which guarantees that encrypting and then decrypting a message returns the original.

Chinese Remainder Theorem

Fundamentals of the Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) says that if you have a system of congruences with pairwise coprime moduli, there's a unique solution modulo the product of all the moduli.

More precisely: given $x \equiv a_1 \pmod{m_1}$, $x \equiv a_2 \pmod{m_2}$, ..., $x \equiv a_k \pmod{m_k}$, where every pair of moduli satisfies $\gcd(m_i, m_j) = 1$, there exists exactly one solution for $x$ in the range $0$ to $M - 1$, where $M = m_1 \cdot m_2 \cdots m_k$.

The power of CRT is that it lets you break a problem with one large modulus into several smaller, independent problems.

Solving Simultaneous Congruences with CRT

Here's the step-by-step method:

1. Compute $M = m_1 \cdot m_2 \cdots m_k$.
2. For each $i$, compute $M_i = M / m_i$.
3. Find the modular inverse $y_i$ of $M_i$ modulo $m_i$, so that $M_i \cdot y_i \equiv 1 \pmod{m_i}$.
4. Combine: $x \equiv a_1 M_1 y_1 + a_2 M_2 y_2 + \cdots + a_k M_k y_k \pmod{M}$.
5. Verify by plugging $x$ back into each original congruence.

Worked example: Solve $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$.

1. $M = 3 \times 5 \times 7 = 105$

2. $M_1 = 105/3 = 35$, $M_2 = 105/5 = 21$, $M_3 = 105/7 = 15$

3. Find inverses:

   • $35 \cdot y_1 \equiv 1 \pmod{3}$: $35 \equiv 2 \pmod{3}$, and $2 \cdot 2 = 4 \equiv 1 \pmod{3}$, so $y_1 = 2$
   • $21 \cdot y_2 \equiv 1 \pmod{5}$: $21 \equiv 1 \pmod{5}$, so $y_2 = 1$
   • $15 \cdot y_3 \equiv 1 \pmod{7}$: $15 \equiv 1 \pmod{7}$, so $y_3 = 1$

4. $x \equiv 2(35)(2) + 3(21)(1) + 2(15)(1) = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}$

5. Check: $23 \bmod 3 = 2$ ✓, $23 \bmod 5 = 3$ ✓, $23 \bmod 7 = 2$ ✓

Applications and Extensions of Modular Equations

CRT and modular equations appear across several areas of discrete math and computer science:

• RSA optimization: CRT speeds up RSA decryption by splitting computation mod $n$ into two smaller computations mod $p$ and mod $q$ (the prime factors of $n$), then combining results.
• Discrete logarithm problem: Given $g^x \equiv h \pmod{p}$, finding $x$ is computationally hard. This difficulty underpins the security of Diffie-Hellman key exchange and ElGamal encryption.
• Quadratic residues: An integer $a$ is a quadratic residue mod $n$ if there exists some $x$ with $x^2 \equiv a \pmod{n}$. Quadratic reciprocity describes when quadratic residues exist across different prime moduli.
• Error-correcting codes: Modular arithmetic over finite fields is used to construct codes that detect and correct transmission errors in digital communication.

These topics connect modular arithmetic to the broader landscape of cryptography and coding theory, where the computational difficulty of certain modular problems is exactly what makes secure systems possible.