剩余类和完全剩余系

剩余类和完全剩余系的定义（定理1，定义1）

定理1

设$m\in {\mathbb{Z}}_{+},$则全部整数可以分成$m$个集合，记作$K_0,K_1,\dots ,K_{m-1},$其中$K_r(r=0,1,\dots ,m-1)$是由一切形如$qm+r(q\in \mathbb{Z})$的整数组成的。这些集合具有下列性质。

1. 每一个整数必包含而且仅在上诉的一个集合里面；
2. 两个整数再同一个集合的充要条件是这两个整数对模$m$同余。

说白了就把整数集分成了$m$个集合，每个集合模$m$的余数相同的放在一个集合。比如我可以把正整数分为三个集合，模为$0$的在一个集合，$1$的在一个集合，$2$的在一个集合。

下面看个例子就懂了

例1

计算$m=2,3,5$时，对应的$K_r$

1. $m=2$时，可以把整数划分为两个集合，一个余数是0，一个余数是一，也就是奇数一个集合，偶数一个集合

   k 0 = { 0 , ± 2 , ± 4 , ± 6 , ± 8 , … } , k 1 = { ± 1 , ± 3 , ± 5 , … } k_0=\{0,\pm2,\pm4,\pm6,\pm8,\dots\},k_1=\{\pm1,\pm3,\pm5,\dots\} k0​={0,±2,±4,±6,±8,…},k1​={±1,±3,±5,…}

2. $m=3$时会被划分为三个集合 k 0 = { 0 , ± 3 , ± 6 , ± 9 , … } , k 1 = { ± 1 , ± 4 , ± 7 , ± 10 , … } , k 2 = { ± 2 , ± 5 , ± 8 , ± 11 , … } k_0=\{0,\pm3,\pm6,\pm9,\dots\},k_1=\{\pm1,\pm4,\pm7,\pm10,\dots\},k_2=\{\pm2,\pm5,\pm8,\pm11,\dots\} k0​={0,±3,±6,±9,…},k1​={±1,±4,±7,±10,…},k2​={±2,±5,±8,±11,…}

3. $m=5$被划分成五个集合，这里留给读者写了。

定义1

定理1中的$K_0,K_1,\dots ,K_{m-1}$叫做模$m$的剩余类，一个剩余类中的任一数叫做它同类的数的剩余。

若$a_0,a_1,\dots ,a_{m-1}$是$m$个整数，并且其中任何两个数都不在同一个剩余类中，则$a_0,a_1,\dots ,a_{m-1}$叫做模$m$的一个完全剩余系。

说白了就是从$K_0,K_1,\dots ,K_{m-1}$每个集合中取一个出来就组成了完全剩余系。

比如模5的一个完全剩余系为 { 0 , 1 , 2 , 3 , 4 } \{0,1,2,3,4\} {0,1,2,3,4}

完全剩余系的判定方法和例子（推论1，例2，定义2）

推论1

$m$个整数 { a 0 , a 1 , a 2 , … , a m − 1 } \{a_0,a_1,a_2,\dots,a_{m-1}\} {a0​,a1​,a2​,…,am−1​}作成模$m$一个完全剩余类的充要条件是它们两两对模$m$不同余。

这个结论很显然的，不证了。

例2

有推论我们知道下列序列

$$0,1,\dots ,m-1$$

$$0,m+1,\dots ,am+a,\dots ,(m-1)m+m-1$$

$$0,-m+1,\dots ,(-1{)}^{a}m+a,\dots ,(-1{)}^{m-1}m+m-1$$

都是模$m$的完全剩余系。

定义2

$0,1,\dots ,m-1$这$m$个整数叫做模$m$的最小非负完全剩余系；当$m$是偶数时

$$-\frac{m}{2},\dots ,-1,0,1,\dots ,\frac{m}{2}-1$$

或

$$-\frac{m}{2}+1,\dots ,-1,0,1,\dots ,\frac{m}{2}$$

叫做模$m$的绝对最小完全剩余系，当$m$是奇数时，

$$-\frac{m-1}{2},\dots ,-1,0,1,\dots ,\frac{m-1}{2}$$

叫做模$m$绝对最小完全剩余系。

练习1

写出当$m=5$和$7$以及$m=6$和$8$时的模$m$的绝对最小完全剩余系，并验证你的结果

1. m = 5 ⇒ { − 2 , − 1 , 0 , 1 , 2 } m=5 \Rightarrow \{-2,-1,0,1,2\} m=5⇒{−2,−1,0,1,2}
2. m = 7 , ⇒ { − 3 , − 2 , − 1 , 0 , 1 , 2 , 3 } m=7, \Rightarrow \{-3,-2,-1,0,1,2,3\} m=7,⇒{−3,−2,−1,0,1,2,3}
3. m = 6 , ⇒ { − 3 , − 2 , − 1 , 0 , 1 , 2 } o r { − 2 , − 1 , 0 , 1 , 2 , 3 } m=6, \Rightarrow \{-3,-2,-1,0,1,2\} \ or \ \{-2,-1,0,1,2,3\} m=6,⇒{−3,−2,−1,0,1,2} or {−2,−1,0,1,2,3}
4. m = 8 , ⇒ { − 4 , − 3 , − 2 , − 1 , 0 , 1 , 2 , 3 } o r { − 3 , − 2 , − 1 , 0 , 1 , 2 , 3 , 4 } m=8,\Rightarrow \{-4,-3,-2,-1,0,1,2,3\} \ or \{-3,-2,-1,0,1,2,3,4\} m=8,⇒{−4,−3,−2,−1,0,1,2,3} or{−3,−2,−1,0,1,2,3,4}

完全剩余系的性质（定理2，定理3）

定理2

设$m\in \mathbb{Z},(a,m)=1,b\in \mathbb{Z},$若$x$通过模$m$的一个完全剩余系，则$ax+b$也通过模$m$的完全剩余系，也就是说，若

$x_0,x_1,\dots ,x_{m-1}$是模$m$的完全剩余系，则$a{x}_0+b,\dots ,a{x}_{m-1}+b$也是模$m$的完全剩余系。

例3

设$m=5,a=4,b=3$

1. 证明$x:1,3,5,7,9$是模$m$的一个完全剩余系。
2. 计算由$x$确定的模$m$的完全剩余系$ax+b$

第一问只需要证明两两模$m$不同余即可，余数分别为$1,3,0,2,4$显然是一个模5完全剩余系

对于第二问，$(a,m)=1,ax+b=4x+3,$带入得$7,15,23,31,39$易验证这也是一个模5完全剩余系

定理3

若$m,n$是互素的两个正整数，而$x,y$分别通过模$m,n$的完全剩余系，则$nx+my$通过模$mn$的完全剩余系。

例4

设$m=2,n=3,x:0,1$是通过$m=2$的一个完全剩余系，$y:0,1,2$是通过模$n=3$的一个完全剩余系，计算由$nx+my$确定的模$mn=6$的完全剩余系。

$3\times 0+2\times 0,3\times 0+2\times 1,3\times 0+2\times 2$

$3\times 1+2\times 0,3\times 1+2\times 1,3\times 1+2\times 2$

所以为 { 0 , 2 , 4 , 3 , 5 , 7 } \{0,2,4,3,5,7\} {0,2,4,3,5,7}