同余

等价关系

设集合$S$，定义在$S$上的二元关系$R:S\times S$，如果$R$满足以下性质，则称它为等价关系：

• 自反性：$\forall a\in S,(a,a)\in R$
• 对称性：$(a,b)\in R\to (b,a)\in R$
• 传递性：$(a,b)\in R\wedge (b,c)\in R⟹(a,c)\in R$
  例：
• 实数R上的相等关系$=$
• 所有三角形构成的集合的全等关系$\cong$

同余

$a\equiv b(\mathrm{mod}n)$ ：设$n$为正整数，整数$a$和$b$分别模$n$，如果得到相同的余数，就称$a$和$b$在模$n$下满足同余关系(congruence relation)，简称同余。

定义：设$a,b,n\in \mathbb{Z},n>0$，如果$n|(a-b)$，就称$a$和$b$在模$n$下同余，记作$a\equiv b(\mathrm{mod}n)$

乘法逆元

定义： 设$a\in \mathbb{Z},n\in \mathbb{N}$，如果$az\equiv 1(\mathrm{mod}n)$,称$z$是模$n$下$a$的乘法逆元，记作$a^{-1}=z$