整除与同余

整数的整除、最大公约数与同余 $a\equiv b\pmod m$。欧几里得算法用辗转相除高效求 $\gcd$，并给出 $ax+by=\gcd(a,b)$ 的整数解（裴蜀定理）。

素数与重要定理

素数是乘法的“原子”，算术基本定理保证唯一分解。费马小定理 $a^{p-1}\equiv1\pmod p$、欧拉定理 $a^{\varphi(n)}\equiv1\pmod n$ 与中国剩余定理是模运算的支柱。

进阶专题

二次互反律刻画“谁是模 $p$ 的平方”；丢番图方程求整数解；椭圆曲线 $y^2=x^3+ax+b$ 上的有理点构成群，连接数论与几何，并支撑费马大定理的证明。

例题

例 1　$\gcd(48,36)$：$48=36+12,\ 36=3\times12$，故为 $12$。

例 2　求 $7^{100}\bmod 11$：由费马小定理 $7^{10}\equiv1$，故 $7^{100}\equiv1\pmod{11}$。

应用

RSA 的安全性基于大数分解之难，椭圆曲线密码 (ECC) 用更短密钥达同等强度，广泛用于 HTTPS、比特币与手机加密。模运算还用于哈希、校验码（身份证/ISBN）与伪随机数。