剩余类

定义

设m∈N*，将全体整数对m取模。将所有余数为r(0<=r<=m-1)的整数都整合到同一个集合中，记为kr。所有kr称为m的剩余类。

推论

根据定义，可得：
1.k0∪k1∪k2∪…∪km−1=Z
2.ki∩kj=∅(i!=j)
3.a,b∈kr⇔a≡b(mod m)

完系

定义

从每个kr中任取一个数，取出的m个数就是m的完全剩余系（简称完系），显然m的完系有无穷多个。

推论

1.辨定完系：对于任意i和j，都有ai≢aj(mod m)。
2.设(b,m)=1，c是任意整数，如果a1,a2,a3,…,am是模m的一个完系，那么ba1+c,ba2+c,ba3+c,…,bam+c也是模m的一个完系。这个yy一下其实很好得出，所以就不证明了:P。

简系

定义

如果kr中任意一个数与m互质，那么kr就是与m互质的剩余类。欧拉函数φ(n)表示与n互质数的个数。从所有与m互质的剩余类中任意取一个数，这些数（共φ(n)个）称为模m的一个简化剩余系（简称简系）。

推论

1.判定简系：(ai,m)=1，且对于任意i和j，都有ai≢aj(mod m)。
2.设(b,m)=1，如果a1,a2,a3,…,am是模m的一个简系，那么ba1,ba2,ba3,…,bam也是模m的一个简系。也不证明了:P。