密码学数学基础（二）同余

二、同余

2.1 同余的概念和性质

定义2.1：给定正整数\(m\)，若\(m\mid a-b\)，即存在整数\(k\)使得\(a-b=km\)，则称\(a\)与\(b\)对模\(m\)同余，或\(a\)同余于\(b\)模\(m\)，记作 \[ a\equiv b\pmod m \] 该式称为模\(m\)的同余式。当\(0\le b<m\)时，称\(b\)是\(a\)对模\(m\)的最小非负剩余。

符号\(\bmod\)有两种使用方式：

• 表示同余关系，如\(a\equiv b\pmod m\)；
• 表示取最小非负剩余，如\(a\pmod m\)。

定理2.1：\(a\)同余于\(b\)模\(m\)的充要条件是\(a\)和\(b\)除以\(m\)后所得的最小非负余数相等。

定理显然成立，这也是同余的另一种定义方法。相对于定义2.1，余数相等的定义更容易理解，但定义2.1也同样重要，一定要熟练使用。下面给出一些同余的性质，简单的就不推导了。

定理2.2：同余是一种等价关系，即满足

• 自反性：\(a\equiv a\pmod m\)；
• 对称性：\(a\equiv b\pmod m\Leftrightarrow b\equiv a\pmod m\)；
• 传递性：\(a\equiv b\pmod m,b\equiv c\pmod m\Leftrightarrow a\equiv c\pmod m\)。

定理2.3：同余可以相加减，即若 \[ a\equiv b\pmod m,\quad c\equiv d\pmod m \] 则 \[ a+c\equiv b+d\pmod m \]

定理2.4：同余可以相乘，即若有 \[ a\equiv b\pmod m,\quad c\equiv d\pmod m \] 则 \[ ac\equiv bd\pmod m \]

定义2.2：设\(f(x)=a_nx^n+\cdots+a_0\)，\(g(x)=b_nx^n+\cdots+b_0\)是两个整系数多项式，满足 \[ a_j\equiv b_j\pmod m,\quad0\le j\le n \] 则称多项式\(f(x)\)同余于\(g(x)\)模\(m\)，记作\(f(x)\equiv g(x)\pmod m\)。

定理2.5：设\(d\ge 1\)，\(d\mid m\)，若\(a\equiv b\pmod m\)，则 \[ a\equiv b\pmod d \]

定理2.6：同余式 \[ ca\equiv cb\pmod m \] 等价于 \[ a\equiv b\pmod{m/(c,m)} \]

证明：由同余的性质有 \[ ca\equiv cb\pmod m\Leftrightarrow m\mid c(a-b)\Leftrightarrow\frac{m}{(c,m)}\Bigg|\frac{c}{(c,m)}(a-b) \] 因为\(\frac{m}{(c,m)}\)和\(\frac{c}{(c,m)}\)互素，所以 \[ \frac{m}{(c,m)}\Bigg|(a-b) \]

特别地，当\(c\)与\(m\)互素时，两端同时乘上或除以\(c\)同余式仍成立。记不住上面的没关系，这个特殊情况要记住。

定理2.7：若\(m\ge1\)，\((a,m)=1\)，则存在\(c\)使得 \[ ca\equiv1\pmod m \] 称\(c\)为\(a\)对模\(m\)的逆（元），记作\(a^{-1}\pmod m\)。若限定\(0\le c<m\)，则逆元\(c\)是唯一的。

证明：由扩展欧几里得算法知，存在\(x,y\)使得\(ax+my=(a,m)=1\)，取\(c=x\)即可。

若\(0\le c<m\)，存在两个不同的逆元\(c_1,c_2\)，则有\(c_1a\equiv c_2a\equiv1\pmod m\)，因此\(m\mid a(c_1-c_2)\)，由于\((a,m)=1\)，所以\(m\mid(c_1-c_2)\)，这与\(0\le c_1,c_2<m\)矛盾，因此逆元唯一。由此也能得出\(a\)的全体逆元为剩余类\(c\bmod m\)中的所有元素。

由证明知可以通过扩展欧几里得算法来求逆元。另外注意到定理的条件有\((a,m)=1\)，下面说明如果不互素的话必无逆元。

证明：假设\((a,m)>1\)，存在\(c\)使得\(ca\equiv1\pmod m\)，则有\(ac+my=1\)。因为\((a,m)\mid a,m\)，所以有\((a,m)\mid ac+my\)，即\((a,m)\mid1\)，与假设矛盾。

定理2.8：同余式组 \[ a\equiv b\pmod{m_j},\quad j=1,2,\cdots,k \] 同时成立的充要条件是\(a\equiv b\pmod{[m_1,\cdots,m_k]}\)。

证明：\(a\equiv b\pmod{m_j}\Leftrightarrow m_j\mid a-b\Leftrightarrow[m_1,\cdots,m_k]\mid a-b\)。可结合定理2.5理解。

例2.1：整数\(n\)被9整除的充要条件。

解：设\(n=a_k\cdot10^k+\cdots+a_0\)被9整除，因为\(10^k\equiv1\pmod 9\)，由同余可以相加和相乘可得 \[ n\equiv a_k+\cdots+a_0\pmod 9 \] 因此充要条件为各位数之和被9整除。

2.2 剩余类和剩余系

定义2.3：给定正整数\(m\)，所有对\(m\)同余的数组成的集合称为模\(m\)的一个剩余类，用\(r\bmod m\)表示\(r\)所属的剩余类。如果\((r,m)=1\)，则\(r\bmod m\)称为模\(m\)的既约剩余类。模\(m\)的所有既约剩余类的个数记为\(\varphi(m)\)，称为欧拉函数，也即\(\varphi(m)\)等于所有不超过\(m\)的正整数中与\(m\)互素的整数的个数，根据定义有\(\varphi(1)=\varphi(2)=1\)。

同余是一个等价关系，一个等价关系确定一个划分。对于同余关系来说，它将整数划分为\(m\)个剩余类，这些剩余类满足：

• \(\mathbb{Z}=\bigcup\limits_{r=0}^{m-1}(r\bmod m)\)；
• \((i\bmod m)\cap(j\bmod m)=\varnothing,\quad 0\le i,j<m,i\ne j\)。

通常剩余类\(0\bmod m,\cdots,(m-1)\bmod m\)简记为\(\overline 0,\cdots,\overline{m-1}\)。

定义2.4：模\(m\)的所有剩余类的集合记为\(\mathbb Z_m\)。在模\(m\)的每个剩余类\(\overline i\)中，任取\(a_i\in\overline i,0\le i<m\)，称\(a_0,a_1,\cdots,a_{m-1}\)为模\(m\)的一个完全剩余系，当不会混淆时也简记作\(\mathbb Z_m\)。称\(0,1,2,\cdots,m-1\)为模\(m\)的最小非负（完全）剩余系；称\(-[\frac{m}{2}]+1,\cdots,0,\cdots,[\frac{m}{2}]\)为模\(m\)的最小绝对剩余系。

定义2.5：模\(m\)的所有既约剩余类的集合记为\(\mathbb Z_m^*\)。在模\(m\)的每个既约剩余类\(\overline k_i\)中，任取\(a_i\in\overline k_i,0\le i<\varphi(m),0\le k_i<m,(k_i,m)=1\)，称\(a_0,a_1,\cdots,a_{\varphi(m)-1}\)为模\(m\)的一个既约剩余系（简化剩余系），当不会混淆时也简记作\(\mathbb Z_m^*\)。

举个例子加深理解。

例2.2：模\(6\)的一个完全剩余系为\(\{0,1,2,3,4,5\}\)，既约剩余系为\(\{1,5\}\)，\(\varphi(6)=2\)。

下面的定理给出了判断构成完全剩余系和既约剩余系的充要条件，常用于证明。

定理2.9：

• \(m\)个整数组成模\(m\)的一个完全剩余系的充要条件是这\(m\)个数两两对模\(m\)不同余；
• \(\varphi(m)\)个整数组成模\(m\)的一个既约剩余系的充要条件是这\(\varphi(m)\)个数两两对模\(m\)不同余，且都与\(m\)互素。

定理2.10：

• 设\(a,b\)是任意整数，且\((a,m)=1\)，那么，\(x\)遍历模\(m\)的一组完全剩余系的充要条件是\(ax+b\)也遍历模\(m\)的一组完全剩余系；
• 设\(a,b\)是任意整数，且\((a,m)=1\)，那么，\(x\)遍历模\(m\)的一组既约剩余系的充要条件是\(ax+bm\)也遍历模\(m\)的一组既约剩余系。

证明：

• 由定理2.9，\(x_0,x_1,\cdots,x_{m-1}\)两两不同余，同时加一个\(b\)不影响同余，又因为\((a,m)=1\)，由定理2.6的特殊情况知乘以\(a\)也不影响同余；
• 同理乘以\(a\)不影响同余，注意加的是\(bm\)，因为既约剩余系不是“连续”的，所以比上面的条件弱一点。

下面的定理需要重点理解。

定理2.11：设\(m=m_1m_2,(m_1,m_2)=1\)。\(x_i^{(1)}\)遍历模\(m_1\)的完全/既约剩余系，\(x_j^{(2)}\)遍历模\(m_2\)的完全/既约剩余系的充要条件是 \[ x_{ij}=m_2x_i^{(1)}+m_1x_j^{(2)} \] 遍历模\(m\)的完全/既约剩余系。

证明：先证明完全剩余系的情况。\(x_{ij}\)遍历模\(m\)的完全剩余系即两两不同余，采用反证法，如果有\(x_{i_1j_1}\equiv x_{i_2j_2}\pmod m\)，则它们对于\(m\)的因子\(m_1,m_2\)也同余，以\(m_1\)为例有 \[ \begin{align} x_{i_1j_1}&\equiv x_{i_2j_2}\pmod{m_1}\Leftrightarrow\\ m_2x_{i_1}^{(1)}+m_1x_{j_1}^{(2)}&\equiv m_2x_{i_2}^{(1)}+m_1x_{j_2}^{(2)}\pmod{m_1}\Leftrightarrow\\ x_{i_1}^{(1)}&\equiv x_{i_2}^{(1)}\pmod{m_1} \end{align} \] 而由\(x_i^{(1)}\)遍历模\(m_1\)的完全剩余系，\(x_i^{(1)}\)应当两两对\(m_1\)不同余，因此矛盾。

对于既约剩余系的情况，只需额外证明\((x_{ij},m)=1\)，等价于证明\((x_{ij},m_1)=1\)且\((x_{ij},m_2)=1\)，以\(m_1\)为例，显然\(x_{ij}=m_2x_i^{(1)}+m_1x_j^{(2)}\)与\(m_1\)是互素的，得证。

证明的核心是利用定理2.8，将\(m\)上的同余等价到\(m_1,m_2\)上的同余，而将\(x_{ij}\)构造为\(m_2x_i^{(1)}+m_1x_j^{(2)}\)是满足要求的。

上述定理推广如下。

定理2.12：设\(m=m_1\cdots m_k\)，且\(m_1,\cdots,m_k\)两两互素。再设\(M_j=\frac{m}{m_j},1\le j\le k\)及 \[ x=M_1x^{(1)}+\cdots+M_kx^{(k)} \] 那么\(x\)遍历模\(m\)的完全/既约剩余系的充要条件是\(x^{(1)},\cdots,x^{(k)}\)分别遍历模\(m_1,\cdots,m_k\)的完全/既约剩余系。

定理2.11和2.12说明了较大模数的完全/既约剩余系可以表示成多个较小的模的完全/既约剩余系的组合。

最后来讨论模的剩余系和因子的剩余系之间的关系。

定理2.13：设\(m_1\mid m,d=m/m_1\)，那么对任意的\(r\)有 \[ r\bmod m\subseteq r\bmod m_1 \] 等号当且仅当\(m=m_1\)时成立。并且有 \[ r\bmod m_1=\bigcup\limits_{0\le j\le d-1}(r+jm_1)\bmod m \]

看个例子就理解了。

例2.3：设\(m=6,m_1=2,d=3,r=1\)，\(r\bmod m=\{1+6k\}\)，\(r\bmod m_1=\{1+2k\}\)，显然\(\{1+6k\}\)是\(\{1+2k\}\)的子集，并且 \[ \{1+2k\}=\{1+6k\}\cup\{3+6k\}\cup\{5+6k\} \]

注：该表示方法不准确，明白意思即可。

2.3 欧拉（Euler）定理

欧拉函数在已知因式分解的情况下可通过以下定理求值。

定理2.14：

• 设\(p\)是素数，\(k\ge1\)，那么 \[ \varphi(p^k)=p^{k-1}(p-1) \] 特别地，\(\varphi(p)=p-1\)。

• 设\(m=m_1m_2\)，且\((m_1,m_2)=1\)，则\(\varphi(m)=\varphi(m_1)\varphi(m_2)\)。

• 设\(m=p_1^{\alpha_1}\cdots p_r^{\alpha_r}\)，其中\(p_1,\cdots,p_r\)为不同的素因子，则 \[ \varphi(m)=p_1^{\alpha_1-1}(p_1-1)\cdots p_r^{\alpha_r-1}(p_r-1) \]

证明：

• 1到\(p^k\)中与\(p^k\)不互素的只有\(p,2p,\cdots,p^{k-1}p\)，因此\(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\)。
• 由定理2.11可得。
• 由前两条可得。

下面介绍著名的欧拉定理。

定理2.15（欧拉定理）：设\((a,m)=1\)，则有 \[ a^{\varphi(m)}\equiv1\pmod m \] 特别地，当\(m\)为素数\(p\)时， \[ a^{p-1}\equiv1\pmod p \] 称为费马小定理。

证明：

易知模\(m\)的两个不同的既约剩余系\(\{r_1,\cdots,r_{\varphi(m)}\}\)和\(\{r_1',\cdots,r_{\varphi(m)}'\}\)，其各元素之积模\(m\)的结果相等，即 \[ \prod_{i=1}^{\varphi(m)}r_i\equiv\prod_{i=1}^{\varphi(m)}r_i'\pmod m \] 现取模\(m\)的一个既约剩余系\(\{r_1,\cdots,r_{\varphi(m)}\}\)，因为\((a,m)=1\)，由定理2.10可得\(\{ar_1,\cdots,ar_{\varphi(m)}\}\)也是模\(m\)的既约剩余系，再由上述结论有 \[ \prod_{i=1}^{\varphi(m)}r_i\equiv\prod_{i=1}^{\varphi(m)}ar_i\equiv a^{\varphi(m)}\prod_{i=1}^{\varphi(m)}r_i\pmod m \] 因为\((r_i,m)=1\)，所以两边可以约掉\(r_i\)，得 \[ a^{\varphi(m)}\equiv1\pmod m \]

欧拉定理也可以用于求逆元，即当\((a,m)=1\)时，有\(a^{-1}\equiv a^{\varphi(m)-1}\pmod m\)。

例2.4：求\(7^{101}\pmod{10}\)。

解：\(\varphi(10)=\varphi(2)\varphi(5)=4\)，由欧拉定理有\(7^4\equiv1\pmod{10}\)，所以\(7^{101}\equiv7^{25\times4+1}\equiv7\pmod{10}\)。

2.4 威尔逊（Wilson）定理

定理2.16（威尔逊定理）：设\(p\)是素数，\(r_1,\cdots,r_{p-1}\)是模\(p\)的既约剩余系，则 \[ \prod_{r\bmod p}r\equiv r_1\cdots r_{p-1}\equiv-1\pmod p \] 特别地有 \[ (p-1)!\equiv-1\pmod p \]

证明：

当\(p=2\)时显然成立。设\(p\ge3\)，对每个\(r_i,0<i<p\)，由定理2.7必有\(r_j\)使得 \[ r_ir_j\equiv1\pmod p \] 现在有两种情况：

• 一种是\(r_i=r_j\)，那\(r_i\)取哪些值会有这种情况呢？当\(r_i=r_j\)时，有\(r_i^2\equiv1\pmod p\)，即\((r_i-1)(r_i+1)\equiv0\pmod p\)，因此当\(r_i\equiv1,-1\pmod p\)时是这种情况；
• 否则\(r_i\ne r_j\)，这样的\(r_i,r_j\)两两配对就可以消去。

因此只需将第一种情况的取值乘起来：\(1\times-1\equiv-1\mod p\)。

定理2.17：设素数\(p\ge3\)，\(c=\varphi(p^l),l\ge1\)，\(r_1,\cdots,r_c\)是模\(p^l\)的既约剩余系，则 \[ r_1\cdots r_c\equiv-1\pmod{p^l} \]

证明：和上面的证明类似，\(r_i\ne r_j\)时可以两两配对消去，\(r_i=r_j\)时\(r_i\equiv1,-1\pmod{p^l}\)。

定理2.18：设素数\(p\ge3\)，\(c=\varphi(2p^l),l\ge1\)，\(r_1,\cdots,r_c\)是模\(2p^l\)的既约剩余系，则 \[ r_1\cdots r_c\equiv-1\pmod{2p^l} \]

证明：

乘以2实际上不影响既约剩余类的个数，因为\(\varphi(2p^l)=\varphi(2)\varphi(p^l)=\varphi(p^l)\)，这里取 \[ r_j'= \begin{cases} r_j&r_j为奇数\\ r_j+p^l&r_j为偶数 \end{cases} \] 可以发现\(r_j'\)仍是模\(p^l\)的既约剩余系，且都为奇数。因此有\(r_1'\cdots r_c'\equiv-1\pmod{p^l}\)和\(r_1'\cdots r_c'\equiv-1\pmod2\)，由定理2.8可得\(r_1\cdots r_c\equiv-1\pmod{2p^l}\)。

总结：以上定理说明当\(m=2,4,p^l,2p^l\)（\(p\)为奇素数）时，模\(m\)的既约剩余系的乘积\(r_1\cdots r_c\equiv-1\pmod m\)，可以证明\(m\)取其他值的情况下\(r_1\cdots r_c\equiv1\pmod m\)。

2.5 SageMath

sage: mod(5, 3)         # 求模
2
sage: inverse_mod(2, 7) # 求逆元
4
sage: pow(3, 4, 40)     # 平方取模
1

# 定义模12下的同余运算
sage: R = Zmod(12)
sage: list(R)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
sage: a = R(5)
sage: b = R(7)
sage: a + b
0
sage: a ^ (-1)
5

# 欧拉函数
sage: euler_phi(15)
8