1. 剩余类的定义

设\(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\)。

2. 完全剩余系的定义

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

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

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

3. 完全剩余系的性质

性质一：元素个数固定：模\(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\)的一个完全剩余系。

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

简化计算：在计算整数关于模\(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\)。

数论基础 - 主要研究整数性质以及和它有关的规律