同余

同余定义：\(n|a-b\Leftrightarrow a\equiv b\pmod n\).

性质：

若 \(a\equiv b\pmod n\)，则 \(a,b\) 对 \(n\) 作带余除法的余数相同。
自反性：\(a\equiv b\pmod n\Rightarrow b\equiv a\pmod n\).
传递性：\(a\equiv b\pmod n,b\equiv c\pmod n\Rightarrow a\equiv c\pmod n\).
可加性：\(a_1\equiv a_2\pmod n,b_1\equiv b_2\pmod n\Rightarrow a_1\pm b_1\equiv a_2\pm b_2\pmod n\).
可乘性：\(a_1\equiv a_2\pmod n,b_1\equiv b_2\pmod n\Rightarrow a_1\times b_1\equiv a_2\times b_2\pmod n\).
可除性：\(ka\equiv kb\pmod {kn}\Rightarrow a\equiv b\pmod n\).
互质可除性：\(ka\equiv kb\pmod n,\gcd(k,n)=1\Rightarrow a\equiv b\pmod n\).

[定理 1] 特殊数的余数特征：
设 \(m_i\) 为 \(m\) 的第 \(i\) 位数字。

若 \(m|10^k,n=a\cdot 10^k+\overline{m_km_{k-1}...m_1}\)，则 \(n\equiv \overline{m_km_{k-1}...m_1}\pmod m\).
(和系)若 \(m|10^k-1,n=\sum\limits_{i=0}^{e}a_i\cdot 10^{ik}\)，其中 \(a_i\) 均小于 \(10^k\)，则 \(n\equiv\sum\limits_{i=0}^ea_i\pmod m\).
(差系)若 \(m|10^k+1,n=\sum\limits_{i=0}^{e}a_i\cdot 10^{ik}\)，其中 \(a_i\) 均小于 \(10^k\)，则 \(n\equiv\sum\limits_{i=0}^e(-1)^ia_i\pmod m\).
比如对于 \(11\)，它可以是 \(1\) 位差系(\(11|10+1\))，2 位和系(\(11|10^2-1\))，3 位差系(\(11|10^3+1\))，4 位和系(\(11|10^4-1\))……

[定理 2]：若 \(n\) 为奇质数，则 \(1^2,2^2,...,n^2\) 被 \(n\) 除所得的余数恰好有 \(\frac{n+1}{2}\) 个。

发现 \(k^2\equiv (n-k)^2\)，所以我们可以在 \(\frac{n+1}{2}\) 处划分，左边的一定与右边对应的数同余，所以命题转化为在 \(1\sim \frac{n+1}{2}\) 中模 \(n\) 的余数互不相同。

考虑反证。若 \(\exists 1\le j< i< \frac{n+1}{2},i^2\equiv j^2(\text{mod }n)\)，则 \(n|i^2-j^2\to n|i+j\) 或 \(n|i-j\)。而 \(i\pm j<n\)，所以不成立。

原命题得证。

余数定理
剩余类：\(\mathbb{Z}\) 按 \(\bmod n\) 分为 \(0\pmod n,1\pmod n,...,n-1\pmod n\). 记为 \(\mathbb{Z}_n=\{\overline{0},\overline{1},...,\overline{n-1}\}\)，对加减乘法封闭。

完全剩余系（完系）：\(X=\{a_i\in\overline{i}|0\le i\le n-1\}\).
性质：\(X+k\) 仍为完系，\(X\times k,gcd(k,n)=1\) 仍为完系。

既约剩余系（缩系）：\(X^{\times}=\{a_i\in\overline{i}|0\le i\le n-1\}\).
性质：\((X+k)^{\times}\) 仍为缩系，\((X\times k)^{\times},gcd(k,n)=1\) 仍为缩系。

欧拉函数：\(\varphi(n)\) 表示 \(0\sim n-1\) 与 \(n\) 互质的个数。
性质：是积性函数(\(m,n\) 互质 \(\Rightarrow \varphi(mn)=\varphi(m)\varphi(n)\))。

\(\varphi(p^k)=p^k(1-\frac 1p)\)
\(\varphi(\prod\limits_{i=1}^sp_i^{e_i})=\prod\limits_{i=1}^s\varphi(p_i^{e_i}))=n\prod\limits_{i=1}^s(1-\frac 1p))\)

逆：\(X\text{ op1 } X'\text{ op2 } X\)，\(\text{op1},\text{op2}\) 互为逆。
同余逆（逆元）：\((a,n)=1\Rightarrow \exists b\)，使得 \(ab\equiv 1(\text{mod }n)\)，且 \(b\) 在 \(\bmod n\) 意义下唯一。

\(\mathbb{Z}_p=\{0,1,...,p-1\}\)，对四则运算封闭（域）。

求 \(a^{-1}\pmod n\).
法一：裴蜀定理
法二：带余除法+线性递推

扩展欧几里得算法(exgcd)： 求 \(ax+by=\gcd(a,b)\) 的一组解。

Lucas 定理：\(\exists a,b,c,d\in \mathbb{N}\)，使得 \(n=ap+b,m=cp+d\) ，则 \(C_n^m=C_a^c\times C_b^d\).
特别地：
\(C_{p-1}^m\equiv(-1)^m\pmod p\).
\(C_m^p\equiv\left\lfloor\frac{m}{p}\right\rfloor\pmod p\).

代码：[[P3807 【模板】Lucas 定理]]

中国剩余定理(CRT)：
解方程组：

\[\begin{cases}x\equiv a_1\pmod{n_1}\\x\equiv a_2\pmod {n_2}\\...\\x\equiv a_k\pmod {n_k}\end{cases} \]

\(n_1,n_2,...,x_k\) 两两互质，在 \(\bmod n_1n_2...n_k\) 意义下有唯一解。
令 \(M_i=\frac{\prod\limits_{j=1}^k n_j}{n_i}\)，即为原方程组的一组基 \(\begin{cases}x\equiv 1\pmod {n_i}\\x\equiv 0\pmod {n_j}(j\not=i)\end{cases}\) ，所以 \(\exists y,M_iy\equiv 1\pmod {n_i}\)，设此时的 \(y\) 为 \(M_i^{-1}\)，则有 \(M_iM_i^{-1}\) 为第 \(i\) 个方程的解，所以原方程组的解为 \(\sum\limits_{i=1}^ka_iM_iM_i^{-1}\).

例题：证明 \(\forall n\in\mathbb{Z}^+,\exists\) 连续 \(n\) 个自然数 \(a_n\in\mathbb{Q}\) 不是质数的乘方。(IMO 1989)
构造

\[\begin{cases}a&\equiv 0\pmod{p_1p_2}\\a+1&\equiv 0\pmod {p_3p_4}\\...\\a+n-1&\equiv 0\pmod{p_{2n-1}p_{2n}}\end{cases} \]

这样可以满足存在从 \(a\) 到 \(a+n-1\) 都有两个质因子，就能保证其不是质数的平方。

代码：[[P1495 【模板】中国剩余定理（CRT）]]

扩展中国剩余定理(exCRT)：
解同上的方程组，但是 \(n_i\) 不两两互质。
我们可以考虑将方程两两合并：

\[\begin{cases}x\equiv a_1\pmod{n_1}\\x\equiv a_2\pmod{n_2}\end{cases} \]

这个方程组等价于：

\[x=k_1n_1+a_1=k_2n_2+a_2 \]

移项：

\[k_1n_1-k_2n_2=a_2-a_1 \]

是标准的不定方程形式。
即有解需满足，\(\gcd(n_1,n_2)|(a_2-a_1)\)。
若有解，就可以用 exgcd 求出一组 \(k_1,k_2\)，然后将方程组替换成方程

\[x\equiv a_1+k_1n_1\pmod{\text{lcm}(n_1,n_2)} \]

即可。当然，\(k_1\) 可以替换成 \(k_2\)。

代码：[[P4777 【模板】扩展中国剩余定理（exCRT）]]

Wilson 定理：若 \(p\in\mathbb{P}\)，则 \((p-1)!\equiv p-1\pmod p\).
推论：令 \((n!)_p\) 表示所有小于等于 \(n\) 但不能被 \(p\) 整除的正整数的乘积，即 \((n!)_p=\frac{n!}{\lfloor n/p\rfloor!p^{\lfloor n/p\rfloor}}\)，对于 \(p\in \mathbb{P}\)，\((p^q!)_p\equiv - 1\pmod{p^q}\)，特别地，\(p=2\) 且 \(q\ge 3\) 时答案为 \(1\)。

exlucas：不会。

缩系的乘积：

\[\prod\limits_{a\in\mathbb{Z}_n^{\times}}a\equiv\prod\limits_{i^2\equiv i}i\equiv\begin{cases}1&n=p^{e},2,4,2p^e\\-1&\text{otherwise}\end{cases}\pmod n \]

欧拉定理：\(a,n\in\mathbb{Z}^+,(a,n)=1\)，则 \(a^{\varphi(n)}\equiv\pmod n\).
证明：因为 \((a,n)=1\)，所以 \(\{ax_1,ax_2,...,ax_{\varphi(n)}\}\) 为缩系。
所以 \(\prod\limits_{i=1}^{\varphi(n)}(ax_i)\equiv\prod\limits_{i=1}^{\varphi(n)}x_i\pmod n\).
所以 \(a^{\varphi(n)}\equiv 1\pmod n\).（互质可消）
由此可以得出 \(a^b\equiv a^{b\bmod \varphi(n)}\pmod n(a\perp n)\).
发现两边 \(×a^{-1}\)，有 \(a^{\varphi(n)-1}\equiv a^{-1}\pmod p\)，即求逆元的另一种方法。