欧拉函数与欧拉定理

$\varphi(n)$ 表示 $1\sim n$ 中与 $n$ 互素的个数；若 $n=pq$（不同素数）则 $\varphi(n)=(p-1)(q-1)$。欧拉定理：当 $\gcd(a,n)=1$，
$a^{\varphi(n)}\equiv1\pmod n$

费马小定理

欧拉定理在素数 $p$ 下的特例（$\varphi(p)=p-1$）：
$a^{p-1}\equiv1\pmod p\quad(p\nmid a)$
它让大指数模幂可「约简指数」，也是费马素性测试的依据。

中国剩余定理 (CRT)

两两互素的模 $n_1,\dots,n_k$ 下，同余方程组
$x\equiv a_i\pmod{n_i}$
在模 $\prod n_i$ 下有唯一解。CRT 把大模运算拆成几个小模并行。

例题

例　解 $x\equiv2\pmod3,\ x\equiv3\pmod5$：枚举 $x=8$ 满足两式，故 $x\equiv8\pmod{15}$。

应用

欧拉定理是 RSA 正确性的核心（$m^{ed}\equiv m$）；CRT 把 RSA 解密提速约 4 倍（分别模 $p,q$ 再合并）；费马小定理支撑素性测试与许多协议的指数约简。