脚本宝典收集整理的这篇文章主要介绍了剩余类、完全剩余系和简化剩余系，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
给定一个正整数 (n)，把所有整数根据模 (n) 的余数 (rin[0,n-1]) 分为 (n) 类，每一类数都是诸如 (C_r=n*x+r, xin Z) 的形式，这样的一类数所构成的一个集合称为模 (n) 的剩余类。
例如我们取 (n=1145, r=14)，则 (C_{14}=1145x+14)，为模 (1145) 的剩余系，(-1131,14,1159) 都是其中的元素。
剩余类的性质都很显然，没什么好说的，直接过了。
给定一个正整数 (n)，有 (n) 个不同的模 (n) 的剩余类，从这 (n) 个不同的剩余类中各取出一个元素，总共 (n) 个数，将这些数构成一个新的集合，则称这个集合为模 (n) 的完全剩余系。
例如我们取 (n=5)，则 ({0,1,2,3,4}) 是一个模 (5) 的完全剩余系，({5,1,8,-3,14}) 也是一个模 (5) 的完全剩余系。
对于一个模 (n) 的完全剩余系 (r)，若有 (ain Z, bin Z)，且 (gcd(n,a)=1)，则 (a*r_i+b (iin[0,n-1])) 也构成一个模 (n) 的完全剩余系。
证明：
命题 (1) ：如果 (r) 是一个模 (n) 的剩余系，那 (r_i+b) 一定也构成一个模 (n) 的完全剩余系。
反证法，若 (r_i+b) 不构成一个模 (n) 的完全剩余系，则存在两个元素同余 (n)，即有 (r_x+bequiv r_y+bpmod n)，同余式两边同时减去 (b)，有 (r_xequiv r_ypmod n)，与 (r) 是一个模 (n) 的剩余系这一前提矛盾，命题 (1) 得证。
命题 (2)：若 (r) 是一个模 (n) 的完全剩余系，对于任意的整数 (a)，若有 (gcd(a,n)=1)，则 (a*r_i) 也构成一个模 (n) 的完全剩余系。
同样是反证法，若结论不成立，则有 (a*r_xequiv a*r_ypmod n)，因为 (gcd(a,n)=1)，所以一定存在 (amod p) 的逆元 (inv(a))，同余式两边同时乘以 (inv(a))，则有 (r_xequiv r_ypmod 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)，若有 (ain Z) 且 (gcd(n,a)=1)，则 (a*r_i) 也构成一个模 (n) 的完全剩余系。证明跟上面的差不多，反证就完了嗷。
以上是脚本宝典为你收集整理的剩余类、完全剩余系和简化剩余系全部内容，希望文章能够帮你解决剩余类、完全剩余系和简化剩余系所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。