Modular Arithmetic¶

Job: Work in $\mathbb{Z}/n\mathbb{Z}$ and $(\mathbb{Z}/n\mathbb{Z})^\times$; apply CRT, Euler–Fermat, and structure theorems for units.

Core¶

Congruence: $a\equiv b\pmod n$ iff $n\mid(a-b)$. Ring $\mathbb{Z}/n\mathbb{Z}$ with $+$ and $\cdot$ mod $n$.

Units: $(\mathbb{Z}/n\mathbb{Z})^\times=\{a\bmod n:\gcd(a,n)=1\}$, group order $\varphi(n)$.

Euler: $a^{\varphi(n)}\equiv1\pmod n$ if $\gcd(a,n)=1$. Fermat: $a^{p-1}\equiv1\pmod p$ for prime $p\nmid a$; equivalently $a^p\equiv a\pmod p$ all $a$.

Wilson: $(p-1)!\equiv-1\pmod p$ iff $p$ prime.

Chinese Remainder Theorem. If $n=\prod n_i$ with pairwise coprime $n_i$, then $$ \mathbb{Z}/n\mathbb{Z}\ \cong\ \prod_i\mathbb{Z}/n_i\mathbb{Z} $$ as rings (componentwise reduction). Hence $(\mathbb{Z}/n\mathbb{Z})^\times\cong\prod(\mathbb{Z}/n_i\mathbb{Z})^\times$. Constructive: $x=\sum a_i N_i y_i$ with $N_i=n/n_i$, $N_i y_i\equiv1\pmod{n_i}$.

Structure of units: - $(\mathbb{Z}/p^k\mathbb{Z})^\times$ cyclic for odd prime $p$;
- $(\mathbb{Z}/2^k\mathbb{Z})^\times\cong C_2\times C_{2^{k-2}}$ for $k\ge3$;
- general $n$: product via CRT.

Primitive root mod $n$: generator of $(\mathbb{Z}/n\mathbb{Z})^\times$ when cyclic (exists iff $n=1,2,4,p^k,2p^k$ odd prime $p$).

Linear congruences: $ax\equiv b\pmod n$ solvable iff $\gcd(a,n)\mid b$; then $\gcd(a,n)$ solutions mod $n$.

Quadratic residues: Legendre $(a/p)=a^{(p-1)/2}\bmod p\in\{0,\pm1\}$; quadratic reciprocity links $(p/q)(q/p)$.

See it¶

Solve $x\equiv2\pmod3$, $x\equiv3\pmod5$, $x\equiv2\pmod7$. Here $n=105$, $N_1=35$, $N_2=21$, $N_3=15$. Inverses: $35\equiv2\Rightarrow y_1\equiv2\pmod3$; $21\equiv1\Rightarrow y_2\equiv1\pmod5$; $15\equiv1\Rightarrow y_3\equiv1\pmod7$. Then $x=2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1=140+63+30=233\equiv23\pmod{105}$.

Check¶

Prove Euler's theorem from Lagrange in group theory.

$a\bmod n\in G=(\mathbb{Z}/n\mathbb{Z})^\times$, $|G|=\varphi(n)$. Order of $a$ divides $|G|$, so $a^{\varphi(n)}=1$ in $G$.

Is $a^{n-1}\equiv1\pmod n$ for all $a$ coprime to $n$ a characterization of primes?

No. Carmichael numbers are composite $n$ with $a^{n-1}\equiv1\pmod n$ for all $\gcd(a,n)=1$. Fermat test is necessary but not sufficient for primality.

Pitfalls¶

Reducing exponents mod $\varphi(n)$ requires $\gcd(a,n)=1$; for $\gcd(a,n)>1$ use CRT split or Carmichael $\lambda(n)$.
"Division" mod $n$ only by units; $2x\equiv2\pmod4$ has solutions but canceling $2$ is invalid.
Discrete log and factoring hardness are computational, not mere nonexistence of formulas.

Refs¶

Ireland–Rosen; Niven–Zuckerman–Montgomery; Crandall–Pomerance (computational).

Next¶

Foundations · Index · Cryptography