最后更新于3年前
设mmm 是一个正整数， aaa 是满足(a,m)=1(a,m )=1(a,m)=1 的整数。如果kkk 遍历模 mmm 的一个简化剩余系，则 a⋅ka\cdot ka⋅k 也遍历模 mmm 的一个简化剩余系
设 m1,m2m_1,m_2m1,m2 是互素的两个正整数。如果k1,k2k_1,k_2k1,k2 分别遍历模 m1m_1m1和模m2m_2m2 的简化剩余系，则k3=m2⋅k1+m1⋅k2k_3=m_2\cdot k_1+m_1\cdot k_2k3=m2⋅k1+m1⋅k2遍历模m1⋅m2=12m_1\cdot m_2=12m1⋅m2=12的简化剩余系
符号/概念
定义
Z/mZ={C0,C1,⋯ ,Cm−1}Z/mZ=\left\{C_0,C_1,\cdots,C_{m-1}\right\}Z/mZ={C0,C1,⋯,Cm−1}
模mmm的完全剩余系
Fp=Z/pZF_p=Z/pZFp=Z/pZ
m=pm=pm=p为素数
CaC_aCa
模mmm的aaa的剩余类
剩余
一个剩余类中的任一数
(Z/mZ)∗={Ca∣0≤a≤m−1},(a,m)=1{\left(Z/mZ\right)}^{*}=\left\{C_a\mid 0\leq a\leq m-1\right\},(a,m)=1(Z/mZ)∗={Ca∣0≤a≤m−1},(a,m)=1
简化剩余类
Fp∗=(Z/pZ)∗F_{p}^{*}={\left(Z/pZ\right)}^{*}Fp∗=(Z/pZ)∗