模的定义

对于整数 $a,b$，满足 $b>0$，则存在唯一的整数 $q,r$ 使得 $a=bq+r$，其中 $0\le r<b$。$q$ 称为 $a$ 除以 $b$ 的商，$r$ 称为 $a$ 除以 $b$ 的余数。余数可使用 $amodb$ 或 $a\mathrm{\%}b$ 表示。

模运算：

1. $(a+b)modM=(amodM+bmodM)modM$。
2. $(a-b)modM=(amodM-bmodM)modM$。
3. $(a\ast b)modM=(amodM\ast bmodM)modM$。

由模的定义可知，所有数模 $b$ 的结果只有 $0,1,2,\cdots ,b-1$ 这 $b$ 个数。若两个数模 $b$ 的结果相同，就有了下面的同余。

同余

若整数 $a$ 和 $b$ 除以正整数 $m$ 的余数相等，则称 $a,b$ 模 $m$ 同余。记作 $a\equiv b(\mathrm{mod}m)$。

同余类与剩余系

对于 $\mathrm{\forall }a\in [0,m-1]$，集合 $\{a+km\}(k\in \mathbb{Z})$ 的所有数模 $m$ 同余，余数都是 $a$。该集合称为一个模 $m$ 的同余类。简记为 $\bar{a}$。

模 $m$ 的同余类一共有 $m$ 个，分别为 $\bar{0},\bar{1},\bar{2},\cdots ,\overline{m-1}$。它们构成 $m$ 的完全剩余系。

$1\sim m$ 中与 $m$ 互质的数代表的同余类共有 $\phi (m)$ 个。它们构成 $m$ 的简化剩余系。

同余定理

1. $a\equiv b(\mathrm{mod}m)$ 当前仅当 $m\mid (a-b)$。
2. $a\equiv b(\mathrm{mod}m)$ 当且仅当存在整数 $k$ 使得 $a=b+km$。

同余性质

1. 自反性：$a\equiv a(\mathrm{mod}m)$。
2. 对称性：$a\equiv b(\mathrm{mod}m)\Rightarrow b\equiv a(\mathrm{mod}m)$。
3. 传递性：$a\equiv b(\mathrm{mod}m)\wedge b\equiv c(\mathrm{mod}m)\Rightarrow a\equiv c(\mathrm{mod}m)$。
4. 同加性：$a\equiv b(\mathrm{mod}m)\Rightarrow (a+c)\equiv (b+c)(\mathrm{mod}m)$。
5. 同乘性：$a\equiv b(\mathrm{mod}m)\Rightarrow (a\ast c)\equiv (b\ast c)(\mathrm{mod}m)$。
6. 同幂性：$a\equiv b(\mathrm{mod}m)\Rightarrow a^n\equiv b^n(\mathrm{mod}m)$。
7. 若 $a\mathrm{mod}p=x,a\mathrm{mod}q=x$，其中 $p,q$ 互质，则 $a\mathrm{mod}pq=x$。
8. $a\equiv b(\mathrm{mod}m)\rightleftharpoons m\mid (a-b)$。

注意的是同余不满足同除性。

欧拉定理

若正整数 $a,n$ 互质，则 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$。

证明：

记 $X=\{x_1,x_2,\cdots ,x_{\phi (n)}\}$，其中 $gcd(x_i,n)=1$，$\phi (n)$ 表示 $n$ 的欧拉函数，即是模 $n$ 的简化剩余系。

记 $Y=X\ast a=\{x_{1}a,x_{2}a,\cdots ,x_{\phi (n)}a\}$。

引理 1：$Y$ 中任意两个元素模 $n$ 不同余。

反证：假设存在 $y_{i}modn=y_{j}modn$，不妨设 $x_i>x_j$，则有 $(y_i-y_j)modn=0$，即 $(a(x_i-x_j))modn=0$，又因为 $gcd(a,n)=1$ 那么 $n\mid (x_i-x_j)$，又因为 $x_j<x_i<n$，所以不存在 $n\mid (x_i-x_j)$，矛盾。

或者由逆元证明：假设存在 $y_i\equiv y_j(\mathrm{mod}n)\Rightarrow a{x}_i\equiv a{x}_j(\mathrm{mod}n)$。因为 $gcd(a,n)=1$，两边同时乘上 $a$ 的逆元 $a^{-1}$，则有 $a{x}_i\equiv a{x}_j(\mathrm{mod}n)$，但 $X$ 中任意两个元素模 $n$ 不同余，矛盾。

引理 2：$Y$ 中每个元素模 $n$ 的结果都与 $n$ 互质。

反证：假设 $y_{i}modn=r$ 则 $a{x}_i=kn+r\Rightarrow r=a{x}_i-kn$，由假设可知 $gcd(r,n)>1$，令 $d=gcd(r,n)$，可知 $d\mid r,d\mid n\Rightarrow d\mid a{x}_i$ 则 $gcd(a{x}_i,n)\ge d$。又因为 $gcd(a,n)=1,gcd(x_i,n)=1$ 则 $gcd(a{x}_i,n)=1$，矛盾。

或者由同余性质证明：对任意 $y_i=a{x}_i$，模 $n$ 后得到 $r\equiv a{x}_i(\mathrm{mod}n)$。又因为 $gcd(a,n)=1,gcd(x_i,n)=1$ 则 $gcd(a{x}_i,n)=1$，从而 $gcd(r,n)=1$。

由以上两个引理可得：$Y$ 中任意两个元素模 $n$ 不同余，且 $Y$ 中每个元素模 $n$ 的结果都与 $n$ 互质，则 $X$ 中的元素与 $Ymodn$ 之后的元素一一对应，则它们的连乘积模 $n$ 相等，即：

$$\prod _{i=1}^{\phi (n)}{y}_i(\mathrm{mod}n)\equiv \prod _{i=1}^{\phi (n)}{x}_i(\mathrm{mod}n)$$

提取 $a^{\phi (n)}$ 项：

$$a^{\phi (n)}\prod _{i=1}^{\phi (n)}{x}_i(\mathrm{mod}n)\equiv \prod _{i=1}^{\phi (n)}{x}_i(\mathrm{mod}n)$$

又因为 $gcd(\prod _{i=1}^{\phi (n)}{x}_i,n)=1$，两边约去 $\prod _{i=1}^{\phi (n)x_i}$

$$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

证毕。

欧拉定理的推论

若正整数 $a,n$ 互质，则对于任意的正整数 $b$，有 $a^b\equiv a^{b\mathrm{mod}\phi (n)}(\mathrm{mod}n)$。

费马小定理

若 $p$ 是质数，则对于任意整数 $a$，有 $a^p\equiv a(\mathrm{mod}p)\Rightarrow a^{p-1}\equiv 1(\mathrm{mod}p)$。