剩余类

设$a\in \mathbb{Z}$,定义剩余类为:$\{x|x\equiv a(\mathrm{mod}n)\}$

剩余类是一种等价类。

记模n下含整数a的剩余类为$[a{]}_n$，在不引起歧义时，简记为 $[a]$。

代表元

剩余类里的每个整数都是剩余类里的代表元。

剩余类集合

用${\mathbb{Z}}_n$表示模n下所有剩余类的集合。 如：${\mathbb{Z}}_5=\{[0],[1],[2],[3],[4]\}$

剩余类的运算

• 加法：$[a]+[b]:=[a+b]$
• 乘法：$[a]\cdot [b]:=[a\cdot b]$
• 乘法逆元：设$u,v\in {\mathbb{Z}}_n,u\cdot v=[1]$，则u,v互为乘法逆元。
  • 设$u=[a]$，$u$有乘法逆元$⟺gcd(a,n)=1$

有乘法逆元的剩余类

将${\mathbb{Z}}_n$中所有有乘法逆元的剩余类的集合记为${\mathbb{Z}}_n^{\ast }$。也即：${\mathbb{Z}}_n^{\ast }:=\{[a]|a\in \mathrm{0..}n\wedge gcd(a,n)=1\}$

${\mathbb{Z}}_n$和${\mathbb{Z}}_n^{\ast }$的关系

• 若n是素数，${\mathbb{Z}}_n^{\ast }={\mathbb{Z}}_n\backslash \{[0]\}$
• 若n是合数，${\mathbb{Z}}_n^{\ast }\subset {\mathbb{Z}}_n\backslash \{[0]\}$