剩余类、剩余系、完全剩余系和简化剩余系学习笔记

大家好，欢迎来到IT知识分享网。

经常在一些数论题题解中看到剩余类、剩余系、完全剩余系、简化剩余系这几个名词，但总感觉自己对它们的概念理解得不是很深，而且还经常混淆，故写篇博客记录下自己所理解的剩余系相关知识，如有错误，欢迎路过的大佬指正。

剩余类（同余类）

定义

给定一个正整数 \(n\)，把所有整数根据模 \(n\) 的余数 \(r\in[0,n-1]\) 分为 \(n\) 类，每一类数都是诸如 \(C_r=n*x+r,\ x\in Z\) 的形式，这样的一类数所构成的一个集合称为模 \(n\) 的剩余类。

例如我们取 \(n=1145,\ r=14\)，则 \(C_{14}=1145x+14\)，为一个模 \(1145\) 的剩余类，\(-1131,14,1159\) 都是其中的元素。

性质

剩余类的性质都很显然，没什么好说的，直接过了。

剩余系

定义

给定一个正整数 \(n\)，有 \(n\) 个不同的模 \(n\) 的剩余类，从中任选 \(x\) 个不同的剩余类，从这 \(x\) 个剩余类中各取出一个元素，总共 \(x\) 个数，将这些数构成一个新的集合，则称这个集合为模 \(n\) 的剩余系。

例如我们取 \(n=1145\)，则 \(r=\{11,4,5,14\}\)​​ 是一个模 \(114514\) 的剩余系。

性质

没啥性质，略。

完全剩余系（完系）

定义

给定一个正整数 \(n\)，有 \(n\) 个不同的模 \(n\) 的剩余类，从这 \(n\) 个不同的剩余类中各取出一个元素，总共 \(n\) 个数，将这些数构成一个新的集合，则称这个集合为模 \(n\) 的完全剩余系。

例如我们取 \(n=5\)，则 \(\{0,1,2,3,4\}\) 是一个模 \(5\) 的完全剩余系，\(\{5,1,8,-3,14\}\) 也是一个模 \(5\) 的完全剩余系。

性质

对于一个模 \(n\) 的完全剩余系 \(r\)，若有 \(a\in Z,\ b\in Z\)，且 \(\gcd(n,a)=1\)，则 \(a*r_i+b\ (i\in[0,n-1])\) 也构成一个模 \(n\) 的完全剩余系。

证明：

命题 \(1\) ：如果 \(r\) 是一个模 \(n\) 的剩余系，那 \(r_i+b\) 一定也构成一个模 \(n\) 的完全剩余系。

反证法，若 \(r_i+b\) 不构成一个模 \(n\) 的完全剩余系，则存在两个元素同余 \(n\)，即有 \(r_x+b\equiv r_y+b\pmod n\)，同余式两边同时减去 \(b\)，有 \(r_x\equiv r_y\pmod n\)，与 \(r\) 是一个模 \(n\) 的剩余系这一前提矛盾，命题 \(1\) 得证。

命题 \(2\)：若 \(r\) 是一个模 \(n\) 的完全剩余系，对于任意的整数 \(a\)，若有 \(\gcd(a,n)=1\)，则 \(a*r_i\) 也构成一个模 \(n\) 的完全剩余系。

同样是反证法，若结论不成立，则有 \(a*r_x\equiv a*r_y\pmod n\)，因为 \(\gcd(a,n)=1\)，所以一定存在 \(a\mod p\) 的逆元 \(inv(a)\)，同余式两边同时乘以 \(inv(a)\)，则有 \(r_x\equiv r_y\pmod n\)，与前提矛盾，命题 \(2\) 得证。

这俩个命题都得证，所以 \(a*r_i\) 构成一个模 \(n\) 的完全剩余系，\(a*r_i+b\) 也构成一个模 \(n\) 的完全剩余系，故性质得证。

简化剩余系（既约剩余系、缩系）

定义

给定一个正整数 \(n\)，有 \(\varphi(n)\) 个不同的、模 \(n\) 的余数 \(r\) 与 \(n\) 互质的剩余类，从这 \(\varphi(n)\) 个剩余类中各取出一个元素，总共 \(\varphi(n)\) 个数，将这些数构成一个新的集合，则称这个集合为模 \(n\) 的简化剩余系。

例如我们取 \(n=10\)，则 \(\{1,3,7,9\}\) 是一个模 \(10\) 的简化剩余系；取 \(n=5\)，则 \(\{1,8,7,14\}\) 是一个模 \(5\) 的简化剩余系，显然模 \(n\) 的简化剩余系中所有的数都与 \(n\) 互质。

性质

对于一个模 \(n\) 的简化剩余系 \(r\)，若有 \(a\in Z\) 且 \(\gcd(n,a)=1\)，则 \(a*r_i\) 也构成一个模 \(n\) 的简化剩余系。证明跟上面的差不多，反证就完了嗷。

参考资料

• 剩余系_百度百科 (baidu.com)
• 剩余类_百度百科 (baidu.com)
• 完全剩余系_百度百科 (baidu.com)
• 简化剩余系_百度百科 (baidu.com)
• 【初等数论】 03 – 同余和剩余系 – 卞爱华 – 博客园 (cnblogs.com)