Modular Arithmetic

Modular Arithmetic

1. Congruences (The Language of Crypto Math)

$a \equiv b \pmod n$ means $n \mid (a-b)$ — same remainder. Residue classes $\{0, 1, \dots, n-1\}$ form $\mathbb{Z}_n$:

Arithmetic respects congruences: if $a \equiv b$, $c \equiv d$, then $a+c \equiv b+d$, $ac \equiv bd \pmod n$ — so we can reduce ANY time mid-computation. Worked: $7^{4} \bmod 11$? $7^2 = 49 \equiv 5$; $7^4 \equiv 5^2 = 25 \equiv 3$. Never compute $2401$ first — reduce early (exam time-saver).

2. Inverses, GCD, and When Division Works

$a$ has inverse mod $n$ ⟺ $\gcd(a, n) = 1$ (proof via Euclid, Module 3 Topic 1). Units form group $\mathbb{Z}_n^*$ of size $\phi(n)$.

Worked inverses: $3^{-1} \bmod 7$: $3 \times 5 = 15 \equiv 1$ → $5$. $2^{-1} \bmod 11$: $2 \times 6 = 12 \equiv 1$ → $6$. No inverse: $4 \bmod 8$ ($\gcd = 4$): $4x \equiv 1 \pmod 8$ has NO solution (LHS always even) — division by 4 illegal mod 8. Solving $ax \equiv b$: unique solution $x \equiv a^{-1}b$ iff $\gcd(a,n) = 1$; else $0$ or $\gcd$ solutions (e.g. $4x \equiv 4 \pmod 8$: $x = 1, 3, 5, 7$ — four solutions).

3. Exponent Rules: Fermat, Euler, Fast Power

• Fermat: $a^{p-1} \equiv 1 \pmod p$ ($p$ prime, $p
  mid a$) → reduce exponents mod$p-1$.
• Euler: $a^{\phi(n)} \equiv 1 \pmod n$ ($\gcd(a,n) = 1$) → reduce exponents mod $\phi(n)$.
• Fast square-and-multiply: $x^{13} = x^{8+4+1}$ ($13 = 1101_2$): square chain $x, x^2, x^4, x^8$ (3 squarings), multiply selected (2 mults) — $O(\log e)$ instead of $O(e)$.

Worked RSA-style: $5^{16} \bmod 17$: Fermat $\to 5^{16} \equiv 1$ directly. $3^{100} \bmod 7$: $3^6 \equiv 1 \to 3^{100} = 3^{96} \cdot 3^4 \equiv 1 \cdot 81 \equiv 81 \equiv 4 \pmod 7$. $2^{36} \bmod 35$: $\phi(35) = 24$, $\gcd = 1$: $2^{36} = 2^{24} \cdot 2^{12} \equiv 2^{12} = 4096 \equiv 4096 - 35 \times 117 = 4096 - 4095 = 1$? Check $35 \times 117 = 4095$ ✓ → $1$. (Pattern: Euler reduction makes big exponents tiny.)

4. Modular Arithmetic Toolkit (Exam Crib)

Tool	Statement	Use
Reduce early	$(a \cdot b) \bmod n = ((a \bmod n)(b \bmod n)) \bmod n$	Keep numbers small
Negative residues	$-3 \equiv 8 \pmod{11}$	Subtraction without borrowing
Inverse via Euclid	$ax + ny = 1 \Rightarrow x = a^{-1}$	DH/RSA/AES key computations
Fermat reduction	$a^e \equiv a^{e \bmod (p-1)} \pmod p$	Fast exponent questions
CRT (Module 5)	Split mod $pq$ into mod $p$ + mod $q$	RSA speedup ×4, exam numericals

Pitfall list: never divide without checking $\gcd$; never reduce exponent mod $n$ (reduce mod $\phi(n)$ or $p-1$, base mod $n$); $a - b \bmod n$ add $n$ first if negative.

Exam Points

• Congruence definition + reduce-early demo ($7^4 \equiv 3 \pmod{11}$) — 2-mark opener.
• Inverse condition $\gcd(a,n) = 1$ with success ($3^{-1} = 5$ mod 7) and failure ($4$ mod $8$) cases.
• Fermat/Euler exponent reduction numericals ($3^{100} \equiv 4 \pmod 7$) — favourite 5-marker.
• Square-and-multiply steps for $x^{13}$; crib-table recall.