初等数论：剩余类、完全剩余系、简化剩余系、中国剩余定理

陈一男学习网站[ ChenYinan.com ] - 中国数学学会 - 中国院士 - GeoGebra - 数学基础

一、剩余类

设\(m\)是一个正整数，对于任意整数\(a\)，所有与\(a\)模\(m\)同余的整数构成的集合，称为模\(m\)的一个剩余类。

记为\(\overline{a}\)，其中\(\overline{a}=\{x|x\in Z,x\equiv a(\bmod m)\}\)。

例如，当\(m = 5\)时，模\(5\)的一个剩余类\(\overline{2}=\{\cdots,-8,-3,2,7,12,\cdots\}\)，这些数除以\(5\)的余数都是\(2\)。

二、完全剩余系

从模\(m\)的每一个剩余类中各取一个代表元素，所构成的集合称为模\(m\)的一个完全剩余系。

例如，\(\{0,1,2,3,4\}\)是模\(5\)的一个完全剩余系。

通常情况下，最小非负完全剩余系是\(\{0,1,\cdots,m - 1\}\)，但完全剩余系的选取不唯一，\(\{-2,-1,0,1,2\}\)也是模\(5\)的一个完全剩余系。

完全剩余系的性质

性质一：元素个数固定：模\(m\)的完全剩余系含有\(m\)个元素。这是因为模\(m\)共有\(m\)个不同的剩余类，每个剩余类取一个代表元素组成完全剩余系，所以元素个数为\(m\)。

性质二：同余关系保持：设\(\{a_1,a_2,\cdots,a_m\}\)是模\(m\)的一个完全剩余系，对于任意整数\(b\)，\(\{a_1 + b,a_2 + b,\cdots,a_m + b\}\)也是模\(m\)的一个完全剩余系。证明如下：

假设\(a_i + b\equiv a_j + b(\bmod m)\)（\(i\neq j\)），根据同余的性质，两边同时减去\(b\)，可得\(a_i\equiv a_j(\bmod m)\)，这与\(\{a_1,a_2,\cdots,a_m\}\)是完全剩余系矛盾，所以\(\{a_1 + b,a_2 + b,\cdots,a_m + b\}\)中任意两个元素模\(m\)不同余，即它是模\(m\)的一个完全剩余系。

性质三：乘法保持（在与\(m\)互质的情况下）：设\(\{a_1,a_2,\cdots,a_m\}\)是模\(m\)的一个完全剩余系，若整数\(c\)与\(m\)互质\((c,m)=1\)，则\(\{ca_1,ca_2,\cdots,ca_m\}\)也是模\(m\)的一个完全剩余系。证明如下：

假设\(ca_i\equiv ca_j(\bmod m)\)（\(i\neq j\)），因为\((c,m)=1\)，根据同余除法性质，可得\(a_i\equiv a_j(\bmod m)\)，这与\(\{a_1,a_2,\cdots,a_m\}\)是完全剩余系矛盾，所以\(\{ca_1,ca_2,\cdots,ca_m\}\)中任意两个元素模\(m\)不同余，即它是模\(m\)的一个完全剩余系。

剩余类和完全剩余系的应用

简化计算：在计算整数关于模\(m\)的同余问题时，可以利用完全剩余系来简化计算。

例如，计算\(1001\times1002\times\cdots\times2000\)除以\(1000\)的余数。因为\(\{1001,1002,\cdots,2000\}\)与\(\{1,2,\cdots,1000\}\)是模\(1000\)的完全剩余系，所以\(1001\times1002\times\cdots\times2000\equiv1\times2\times\cdots\times1000(\bmod1000)\)，而\(1\times2\times\cdots\times1000\)能被\(1000\)整除，余数为\(0\)。

同余方程求解：在求解同余方程\(ax\equiv b(\bmod m)\)时，剩余类和完全剩余系的概念也很有用。

例如，通过在模\(m\)的完全剩余系中逐一验证来求解简单的同余方程。对于方程\(3x\equiv1(\bmod5)\)，在模\(5\)的完全剩余系\(\{0,1,2,3,4\}\)中分别代入\(x\)进行验证，找到满足方程的解\(x = 2\)。

三、简化剩余系

设\(m\)是一个正整数，一个模\(m\)的简化剩余系是指从模\(m\)的完全剩余系中与\(m\)互质的数所构成的集合。

例如，对于\(m = 10\)，其完全剩余系是\(\{0,1,2,3,4,5,6,7,8,9\}\)，而与\(10\)互质的数为\(1,3,7,9\)，所以\(\{1,3,7,9\}\)是模\(10\)的一个简化剩余系。

简化剩余系性质

性质一：元素个数与欧拉函数相关

模\(m\)的简化剩余系中元素的个数为\(\varphi(m)\)，其中\(\varphi(m)\)是欧拉函数。

例如，当\(m = 6\)时，\(\varphi(6)=2\)（因为与\(6\)互质的数有\(1\)和\(5\)），其简化剩余系可以是\(\{1,5\}\)。

性质二：乘法封闭性（在一定条件下）

设\(r_1,r_2\)是模\(m\)的简化剩余系中的任意两个元素，则\(r_1r_2\)（模\(m\)运算后）的结果仍然属于模\(m\)的简化剩余系（前提是\((r_1r_2,m)=1\)）。例如，对于模\(8\)的简化剩余系\(\{1,3,5,7\}\)，\(3\times5 = 15\equiv7(\bmod8)\)，\(7\)仍然属于模\(8\)的简化剩余系。

构造简化剩余系的方法

方法一：筛选法（基于完全剩余系）

先写出模\(m\)的完全剩余系，然后逐一判断每个元素与\(m\)是否互质，将互质的元素挑选出来组成简化剩余系。

例如，对于\(m = 12\)，完全剩余系是\(\{0,1,2,3,4,5,6,7,8,9,10,11\}\)，通过判断互质关系，得到简化剩余系为\(\{1,5,7,11\}\)。

方法二：利用已知简化剩余系和同余关系构造（对于互质的整数）

设\(m_1\)和\(m_2\)是互质的正整数，已知模\(m_1\)的简化剩余系\(r_{11},r_{12},\cdots,r_{1\varphi(m_1)}\)和模\(m_2\)的简化剩余系\(r_{21},r_{22},\cdots,r_{2\varphi(m_2)}\)，可以通过中国剩余定理构造模\(m = m_1m_2\)的简化剩余系。具体构造过程较为复杂，需要根据同余方程求解。

1. 中国剩余定理内容

设\(m_1,m_2,\cdots,m_n\)是两两互质的正整数，\(a_1,a_2,\cdots,a_n\)是任意整数，则同余方程组

\(\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\cdots\\x\equiv a_n\pmod{m_n}\end{cases}\)在模\(M = m_1m_2\cdots m_n\)下有唯一解。

2. 中国剩余定理解法示例

以一个简单的例子来说明，对于同余方程组\(\begin{cases}x\equiv2\pmod{3}\\x\equiv3\pmod{5}\\x\equiv2\pmod{7}\end{cases}\)。

首先，计算\(M = 3\times5\times7 = 105\)。

然后，分别计算\(M_1=\frac{M}{m_1}=\frac{105}{3}=35\)，\(M_2=\frac{M}{m_2}=\frac{105}{5}=21\)，\(M_3=\frac{M}{m_3}=\frac{105}{7}=15\)。

接着，求\(M_1\)关于\(m_1\)的逆元\(y_1\)，即找到满足\(35y_1\equiv1\pmod{3}\)的\(y_1\)，通过计算可知\(y_1 = 2\)；求\(M_2\)关于\(m_2\)的逆元\(y_2\)，满足\(21y_2\equiv1\pmod{5}\)，可得\(y_2 = 1\)；求\(M_3\)关于\(m_3\)的逆元\(y_3\)，满足\(15y_3\equiv1\pmod{7}\)，可得\(y_3 = 1\)。

最后，根据公式\(x=(a_1M_1y_1 + a_2M_2y_2+\cdots+a_nM_ny_n)\bmod M\)，可得\(x=(2\times35\times2 + 3\times21\times1+2\times15\times1)\bmod105 = 23\)，所以该同余方程组的解为\(x\equiv23\pmod{105}\)。

3. 中国剩余定理证明思路

令\(M = m_1m_2\cdots m_n\)，对于每个\(i = 1,2,\cdots,n\)，定义\(M_i=\frac{M}{m_i}\)。由于\(m_i\)两两互质，所以\(M_i\)与\(m_i\)互质，根据裴蜀定理，存在整数\(y_i\)使得\(M_iy_i\equiv1\pmod{m_i}\)。

构造一个解\(x=a_1M_1y_1 + a_2M_2y_2+\cdots+a_nM_ny_n\)。对于任意的\(j = 1,2,\cdots,n\)，当\(i\neq j\)时，\(m_j\mid M_i\)，所以\(a_iM_iy_i\equiv0\pmod{m_j}\)。而对于\(i = j\)，\(a_iM_iy_i\equiv a_i\pmod{m_i}\)。

所以\(x\)满足同余方程组中的每一个方程，即\(x\)是同余方程组的一个解。再证明解的唯一性，假设\(x_1\)和\(x_2\)是同余方程组的两个解，那么对于每个\(i\)，\(x_1 - x_2\equiv0\pmod{m_i}\)，因为\(m_i\)两两互质，所以\(x_1 - x_2\equiv0\pmod{M}\)，即\(x_1\equiv x_2\pmod{M}\)，所以在模\(M\)下解是唯一的。