数论

记 $a\equiv b\pmod m$ 表示 $m\mid a-b$。同余在加、减、乘下封闭，可整体「换成余数再算」。

最有用的是平方数（及高次幂）在小模下的取值受限：

证「某种形式的数不具某性质」时，先算目标式在某个模下的可能取值集合，若目标落在集合外即得证。例如两平方之和模 $4$ 只能是 $0,1,2$，故 $4k+3$ 不是两平方和。

每个正整数唯一地写成素数幂之积（算术基本定理）。由此：

• 互素两数之积为完全平方 $\Rightarrow$ 两数各自为完全平方（如证 $n(n+1)(n+2)=m^3-m$ 非平方，用 $\gcd(m,m^2-1)=1$）。
• 欧几里得法证素数无穷：构造一个「逃出名单」的数，取其新素因子。改造构造数所在的同余类，可证 $4k+3$ 型素数无穷（配合「$\equiv3\pmod4$ 必有 $\equiv3\pmod4$ 的素因子」引理）。
• 费马数 $F_k=2^{2^k}+1$ 两两互素（由 $F_0\cdots F_{k-1}=F_k-2$），也给出素数无穷。

对素数 $p$ 与 $p\nmid a$：费马小定理 $a^{p-1}\equiv1\pmod p$。记 $d=\operatorname{ord}_p(a)$ 为最小的正整数使 $a^d\equiv1$，则 $d\mid p-1$，且 $a^n\equiv1\iff d\mid n$。

招牌杀招（处理 $n\mid a^n\pm1$）：取 $n$ 的最小素因子 $p$，看 $\operatorname{ord}_p(a)$——它同时整除 $n$ 与 $p-1$，而最小素因子迫使 $\gcd(n,p-1)=1$，把阶逼成 $1$ 得矛盾。由此 $n\mid2^n-1$ 只有 $n=1$。

威尔逊定理：$p$ 素数 $\iff(p-1)!\equiv-1\pmod p$（用「元素与逆元配对，只有 $\pm1$ 自逆」证明）。

证某方程「无正整数解」时：假设存在解，取使某变量最小的一组，再造出一组严格更小的同型解，矛盾（正整数不能无限下降）。引擎往往是同余。

典型：$x^2+y^2=3z^2$。平方模 $3\in\{0,1\}$，$x^2+y^2\equiv0$ 迫使 $3\mid x,\ 3\mid y$，代入后又得 $3\mid z$，于是 $(x/3,y/3,z/3)$ 是更小的解——矛盾，故仅有平凡解。同法证 $\sqrt3$ 无理（$p^2=3q^2$ 的递降）。

若模 $m_1,\dots,m_k$ 两两互素，则同余方程组 $x\equiv r_i\pmod{m_i}$ 有解，且模 $\prod m_i$ 唯一。

CRT 是「构造存在性」的利器：想要一串数各满足不同的整除要求，就为每个位置分配一个互素的模。例如证「存在任意长的连续整数，每个都被某平方数 $>1$ 整除」：取不同素数 $p_1,\dots,p_n$，解 $x\equiv-i\pmod{p_i^2}$，则 $x+i$ 被 $p_i^2$ 整除。