Modular Arithmetic

Congruence

Two integers $a$ and $b$ are congruent modulo $n$ if $n$ divides their difference: $a \equiv b \pmod{n} \iff n \mid (a - b)$

Equivalently: $a$ and $b$ have the same remainder when divided by $n$.

Examples

• $17 \equiv 5 \pmod{12}$ (both leave remainder 5)
• $-3 \equiv 9 \pmod{12}$ (difference is 12)
• $100 \equiv 0 \pmod{10}$

Properties of Congruence

Equivalence Relation

• Reflexive: $a \equiv a \pmod{n}$
• Symmetric: If $a \equiv b$, then $b \equiv a$
• Transitive: If $a \equiv b$ and $b \equiv c$, then $a \equiv c$

Arithmetic Properties

If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then:

$a + c \equiv b + d \pmod{n}$ $a - c \equiv b - d \pmod{n}$ $ac \equiv bd \pmod{n}$ $a^k \equiv b^k \pmod{n} \text{ for any } k \geq 0$

Division (Be Careful!)

$ac \equiv bc \pmod{n}$ does NOT imply $a \equiv b \pmod{n}$!

Correct rule: $ac \equiv bc \pmod{n}$ implies $a \equiv b \pmod{n/d}$ where $d = \gcd(c, n)$.

If $\gcd(c, n) = 1$, then we can divide: $a \equiv b \pmod{n}$.

Residue Classes

The residue class of $a$ modulo $n$: $[a]_n = \{b \in \mathbb{Z} : b \equiv a \pmod{n}\}$

The set of residue classes: $\mathbb{Z}_n = \{[0], [1], \ldots, [n-1]\}$

We often write just $0, 1, \ldots, n-1$ for convenience.

Modular Arithmetic Operations

Addition Table (mod 4)

+	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

Multiplication Table (mod 5)

×	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

Modular Inverse

The modular inverse of $a$ modulo $n$ is an integer $a^{-1}$ such that: $a \cdot a^{-1} \equiv 1 \pmod{n}$

Existence

$a^{-1}$ exists if and only if $\gcd(a, n) = 1$.

Finding the Inverse

Use the extended Euclidean algorithm to find $x$ such that: $ax + ny = 1$ Then $x$ is the inverse of $a$ modulo $n$.

Example

Find $7^{-1} \pmod{11}$: $7 \cdot 8 = 56 = 5 \cdot 11 + 1 \equiv 1 \pmod{11}$ So $7^{-1} \equiv 8 \pmod{11}$.

Linear Congruences

Solve: $ax \equiv b \pmod{n}$

Solution

Let $d = \gcd(a, n)$.

No solution if $d \nmid b$.

If $d \mid b$: There are exactly $d$ solutions modulo $n$.

Reduce to: $\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{n}{d}}$

Use modular inverse to solve.

Example

Solve $6x \equiv 4 \pmod{10}$

$\gcd(6, 10) = 2$ and $2 \mid 4$, so solutions exist.

Reduce: $3x \equiv 2 \pmod{5}$

$3^{-1} \equiv 2 \pmod{5}$ (since $3 \cdot 2 = 6 \equiv 1$)

$x \equiv 2 \cdot 2 \equiv 4 \pmod{5}$

Solutions mod 10: $x \equiv 4$ or $x \equiv 9$.

Chinese Remainder Theorem

If $n_1, n_2, \ldots, n_k$ are pairwise coprime, then the system: $x \equiv a_1 \pmod{n_1}$ $x \equiv a_2 \pmod{n_2}$ $\vdots$ $x \equiv a_k \pmod{n_k}$

has a unique solution modulo $N = n_1 n_2 \cdots n_k$.

Construction

$x = \sum_{i=1}^{k} a_i N_i y_i \pmod{N}$

where $N_i = N/n_i$ and $y_i = N_i^{-1} \pmod{n_i}$.

Example

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

$N = 3 \cdot 5 \cdot 7 = 105$

$N_1 = 35$, $y_1 = 35^{-1} \equiv 2^{-1} \equiv 2 \pmod{3}$ $N_2 = 21$, $y_2 = 21^{-1} \equiv 1^{-1} \equiv 1 \pmod{5}$ $N_3 = 15$, $y_3 = 15^{-1} \equiv 1^{-1} \equiv 1 \pmod{7}$

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

Fast Modular Exponentiation

Compute $a^k \pmod{n}$ efficiently using binary representation of $k$.

Algorithm (Square and Multiply)

power(a, k, n):
    result = 1
    a = a mod n
    while k > 0:
        if k is odd:
            result = (result * a) mod n
        k = k / 2  (integer division)
        a = (a * a) mod n
    return result

Time: $O(\log k)$ multiplications.

Example

$3^{13} \pmod{7}$

$13 = 1101_2$

$3^1 = 3$ $3^2 = 9 \equiv 2$ $3^4 \equiv 2^2 = 4$ $3^8 \equiv 4^2 = 16 \equiv 2$

$3^{13} = 3^8 \cdot 3^4 \cdot 3^1 \equiv 2 \cdot 4 \cdot 3 = 24 \equiv 3 \pmod{7}$