剩余

概念解释

符号/概念	定义
$Z/mZ=\left\{C_0,C_1,\cdots,C_{m-1}\right\}$	模$m$的完全剩余系
$F_p=Z/pZ$	$m=p$为素数
$C_a$	模$m$的$a$的剩余类
剩余	一个剩余类中的任一数
${\left(Z/mZ\right)}^{*}=\left\{C_a\mid 0\leq a\leq m-1\right\},(a,m)=1$	简化剩余类
$F_{p}^{*}={\left(Z/pZ\right)}^{*}$	$m=p$为素数

定理

• 设$m$ 是一个正整数， $a$ 是满足$(a,m )=1$ 的整数。如果$k$ 遍历模 $m$ 的一个简化剩余系，则 $a\cdot k$ 也遍历模 $m$ 的一个简化剩余系

• 设 $m_1,m_2$ 是互素的两个正整数。如果$k_1,k_2$ 分别遍历模 $m_1$和模$m_2$ 的简化剩余系，则$k_3=m_2\cdot k_1+m_1\cdot k_2$遍历模$m_1\cdot m_2=12$的简化剩余系