信息安全数学基础 Chapter 2——同余

Chapter 2 同余

定义2.1 同余、不同余

---

定理2.1 同余是一种等价关系（自反性、对称性、传递性依次证明）

---

定义2.2 模m剩余类，模m完全剩余系

---

定义2.3 模m简化剩余类，完全剩余类中所有与m互素的剩余类。模m简化剩余系。欧拉函数：整数1,2,…,m中所有与m互素的整数个数，即为$\phi (m)$

---

定理2.2$a,b$正整数，$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}mn)\Rightarrow a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m),a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$（逆定理不成立）

---

定理2.3$m,n$正整数，$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m),a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)\Rightarrow a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}[m,n])$

---

定理2.4 同余性质：
(1) $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)\Rightarrow a+c\equiv b+c(\mathrm{m}\mathrm{o}\mathrm{d}m)$
(2) $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m),k\in Z\Rightarrow ak\equiv bk(\mathrm{m}\mathrm{o}\mathrm{d}m)$
(3) $ak\equiv bk(\mathrm{m}\mathrm{o}\mathrm{d}m),k\in Z,(k,m)=1\Rightarrow a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$
(4) $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m),k\in N\iff ak\equiv bk(\mathrm{m}\mathrm{o}\mathrm{d}mk)$
(5) $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m),f(x)$为一整系数多项式，$f(a)\equiv f(b)(\mathrm{m}\mathrm{o}\mathrm{d}m)$

推论 若$a_1\equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}m),b_1\equiv b_2(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则$a_1+b_1\equiv a_2+b_2(\mathrm{m}\mathrm{o}\mathrm{d}m),a_1{b}_1\equiv a_2{b}_2(\mathrm{m}\mathrm{o}\mathrm{d}m)$

---

定理2.5 设m为正整数，若(a,m)=1，则当x遍历m的一个完全剩余系时，对于任意整数b，ax+b遍历模m的一个完全剩余系；当x遍历m的一个简化剩余系时，ax遍历m的一个简化剩余系。

证明：
设$r_1,r_2,...,r_m$是模m的一个完全剩余系，当$i\ne j$时，$r_i\ne r_j(\mathrm{m}\mathrm{o}\mathrm{d}m)$，又$(a,m)=1$，则$a{r}_i+b\ne a{r}_j+b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，故x遍历r₁，r₂，…，r_m时，ax+b是m个关于m两两互不同余的整数，因此构成完全剩余系。
如果$r_1,r_2,...,r_{\phi (m)}$是简化剩余系，对于所有$r_i,(r_i,m)=1$，因为$(a,m)=1$，则有$(a{r}_i,m)=1$，即任意ar_i均在简化剩余系中且两两互不同余。因此构成简化剩余系。

---

定理2.6 设m,n为正整数，(m,n)=1，则当x遍历模n的一个完全剩余系，y遍历模m的一个完全剩余系时，mx+ny遍历模mn的一个完全剩余系；当x遍历模n的一个简化剩余系，y遍历模m的一个简化剩余系时，mx+ny遍历模mn的一个简化剩余系。

证明：
假设$m{x}_1+n{y}_1\equiv m{x}_2+n{y}_2(\mathrm{m}\mathrm{o}\mathrm{d}mn)$，由定理2.2可知，$m{x}_1+n{y}_1\equiv m{x}_2+n{y}_2(\mathrm{m}\mathrm{o}\mathrm{d}m),m{x}_1+n{y}_1\equiv m{x}_2+n{y}_2(\mathrm{m}\mathrm{o}\mathrm{d}n)$，又(m,n)=1，故$y_1\equiv y_2(\mathrm{m}\mathrm{o}\mathrm{d}m),x_1\equiv x_2(\mathrm{m}\mathrm{o}\mathrm{d}n)$。因此mx+ny互不同余，构成模mn的完全剩余系。
若$(x,n)=1,(y,m)=1$，则$(mx+ny,m)=(ny,m)=(y,m)=1,(mx+ny,n)=1$，故$(mx+ny,mn)=1$，即任意一个与mn互素的整数都在遍历所产生的$\phi (m)\phi (n)$个简化剩余类中。

---

定理2.7 （欧拉定理）m为正整数，(a,m)=1，则$a^{\phi (m)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$

证明：
构造模m的简化剩余系$r_1,r_2,...,r_{\phi (m)}$，(a,m)=1，故由定理2.4有$a{r}_1,a{r}_2,...,a{r}_{\phi (m)}$也是模m简化剩余系。故对于任意$1\le i\le \phi (m)$有且仅有唯一$1\le j\le \phi (m)$使得$a{r}_i=r_j$。故
$$r_1{r}_2...r_{\phi (m)}\equiv a^{\phi (m)}{r}_1{r}_2...r_{\phi (m)}(\mathrm{m}\mathrm{o}\mathrm{d}m)$$
证毕

---

定理2.8 （费马小定理）p为素数，则对于任意整数a，$a^p\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$

证明：
由欧拉定理可知若(a,p)=1，则$a^{\phi (p)}=a^{p-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$，原命题成立
否则必有p|a，即$a^{p-1}\equiv a\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$

---

定理2.9 m,n为正整数，若互素，则$\phi (m)\phi (n)=\phi (mn)$

证明：
定理2.6

---

定理2.10 p为素数，e为正整数，则$\phi (p^e)=p^e-p^{e-1}$

证明：
从1到p^e中与p^e不互素的只有p的倍数，共有p^e-1个。

---

定理2.11 设m为正整数，$m={\prod }_{i=1}^S{p}_i^{a_i}$，则$\phi (m)=m{\prod }_{i=1}^S(1-\frac{1}{p_i})$

证明：
定理2.9，2.10

---

定义2.4 模m同余式：$f(x)={\sum }_{i=0}^n{a}_i{x}^i$为一个整系数多项式，m为正整数，称$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}m)$为模m同余式。若$a_n\ne 0(\mathrm{m}\mathrm{o}\mathrm{d}m)$则称该同余式次数为n，如果整数a满足$f(a)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}m)$则称a为同余式的解。解数：同余式解的个数。

---

定理2.12 m为正整数，同余式$ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$有解的充要条件是(a,m)|b。有解时结束为(a,m)，且若x=x₀是同余式的一个特解，则同余式的所有解可以表示为
$$x\equiv x_0+\frac{m}{(a,m)}t(\mathrm{m}\mathrm{o}\mathrm{d}m),t=0,1,2,...,(a,m)-1$$

证明：
若$ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$有解，则存在整数y使得ax-b=my，且若x=x₀，y=y₀是ax-b=my的一个解，则$x\equiv x_0(\mathrm{m}\mathrm{o}\mathrm{d}m)$就是$ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$的一个解。根据定理1.8可知，ax-b=my有解的充要条件是(a,m)|b。
若x=x₀，y=y₀是ax-b=my的一个解，则ax-b=my的所有解可以表示为：
$$\{\begin{array}{r}x=x_0+\frac{m}{(a,m)}t\\ y=y_0+\frac{a}{(a,m)}t\end{array},t\in \mathbb{Z}$$
可将$x=x_0+\frac{m}{(a,m)}t,t\in \mathbb{Z}$写为(a,m)个模m的同余类，即t取0,1,…,(a,m)-1

---

定理2.13 m为正整数，(a,m)=1，则$a^{\phi (m)-1}$是a模m的逆元。

证明：略

---

定理2.14 （Wilson定理）设p为素数，则$(p-1)!\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)$

证明：
p=2时结论显然成立
p>2，对于$1\le a\le p-1$，因为(a,p)=1，因此a存在逆元a’，由$ax\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$的解数为1，故满足$1\le a^{\prime }\le p-1$的逆元也是唯一的。在1,2,…,p-1中将这些数一一配对，每一对的两数均互为逆元，则结论显然成立。

---

定理2.15 （中国剩余定理）设$m_1,m_2,...,m_S$为两两互素的正整数，$b_1,b_2,...,b_S$为任意整数，则同余式组
$$\{\begin{array}{r}x\equiv b_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ x\equiv b_2(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)\\ ...\\ x\equiv b_S(\mathrm{m}\mathrm{o}\mathrm{d}{m}_S)\end{array}$$
模$M=m_1...m_S$有唯一解$x\equiv {\sum }_{i=1}^S{b}_i\frac{M}{m_i}(\frac{M}{m_i}{)}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)(\mathrm{m}\mathrm{o}\mathrm{d}M)$

证明：
存在性：代入上式即可
唯一性：设有一个解为x₀，则其满足上面任意一个式子，根据定理1.14有$M=[m_1,m_2,...,m_S]|x-x_0$，即$x\equiv x_0(\mathrm{m}\mathrm{o}\mathrm{d}M)$，解唯一。

---

定理2.16 设$m_1,m_2,...,m_S$为两两互素的正整数，对于$1\le i\le s$，同余式$f_i(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$有C_i个解，则同余式组
$$\{\begin{array}{r}f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)\\ ...\\ f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{m}_S)\end{array}$$
关于模$M=m_1...m_S$有$C_1{C}_2...C_s$个解。

证明：组合。
证明这些解互不同余：
若有$x\equiv x^{\prime }(\mathrm{m}\mathrm{o}\mathrm{d}M)$，则由定理2.2可知对于任意i均有$x\equiv x^{\prime }(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$，故x=x’。
任何b_i变化都会导致解不同。

---

定理2.17 p为素数，$i_1\ge i_2\ge ...i_S,b_1,b_2,...,b_S$为任意整数，同余式组
$$\{\begin{array}{r}x\equiv b_1(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{i_1})\\ x\equiv b_2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{i_2})\\ ...\\ x\equiv b_S(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{i_S})\end{array}$$
有解的充要条件为
$$\{\begin{array}{r}{b}_1\equiv b_2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{i_2})\\ b_1\equiv b_3(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{i_3})\\ ...\\ b_1\equiv b_S(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{i_S})\end{array}$$

证明：
充分性易证
必要性：若有解x₀，则由定理2.2可知$x_0\equiv b_1(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{i_2})$，故$b_1$是第二个式子的解，同理b₁也是后面所有式子的解。

---

定义2.6 导式

---

定理2.18 设p为素数，$k\ge 1$，若$x\equiv x_k(\mathrm{m}\mathrm{o}\mathrm{d}{p}^k)$为同余式$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^k)$的一个解，则在这个剩余类中：
(1) 若$(p,f^{\prime }(x^k))=1$，则同余式$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{k+1})$有唯一解。
(2) 若$p|f^{\prime }(x^k)$，当$f(x_k)\ne 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{k+1})$时，同余式$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{k+1})$无解，否则有p个解。

证明：
由定理2.2可知，同余式$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{k+1})$的解一定是$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^k)$的解，因此我们只需对$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^k)$的解进行筛选即可。

从$x=x_k+p^{k}t,t\in \mathbb{Z}$中进行筛选：
将其代入到$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{k+1})$中使用泰勒公式可得：
$$f(x_k)+f^{\prime }(x_k)p^{k}t+\sum _{i=2}^n\frac{f^{(i)}(x_k)p^{ik}}{i!}{t}^i\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{k+1})$$
因为$\frac{f^{(i)}(x_k)}{i!}=\frac{a_n\cdot n!}{i!(n-i)!}$为整数，因此有$i!|f^{(i)}(x_k)$。即泰勒展开除前面两项之外后面所有项均整除$p^{k+1}$，可以全部消去，化简为：
$$f(x_k)+f^{\prime }(x_k)p^{k}t\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{k+1})$$
又$p^k|f(x_k)$，上式可以化为：
$$\frac{f(x_k)}{p^k}+f^{\prime }(x_k)t\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^{k+1})$$
若$(f^{\prime }(x_k),p)=1$则t仅有1个取值。若为0则与定理结论相符。

推论 p为素数，若$x\equiv x_1(\mathrm{m}\mathrm{o}\mathrm{d}p)$是同余式$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$的一个解，且满足$(f^{\prime }(x_1),p)=1$，则对于任意正整数k>1，$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^k)$的满足$x\equiv x_1(\mathrm{m}\mathrm{o}\mathrm{d}p)$的解x_k可以通过以下递推式得到：
$$x_i=x_{i-1}-f(x_{i-1})((f^{\prime }(x_1){)}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p))(\mathrm{m}\mathrm{o}\mathrm{d}{p}^i),i=1,2,3,...,k$$

证明：数学归纳法

---