初等数论：剩余类、完全剩余系、简化剩余系

陈一男学习网站[ 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\)的简化剩余系。具体构造过程较为复杂，需要根据同余方程求解。