定义：

若\((a-b)\ mod\ p=0\)，则\(a\)与\(b\)在模\(p\)的意义下同余，记作\(a\equiv b(mod\ p)\)。(\(a,c\in Z\)(整数)，\(m\in N^*\)(正整数))

性质：

1.\(a\equiv a(mod\ p)\)

2.若\(a\equiv b(mod\ p)\)，则\(b\equiv a(mod\ p)\)

3.若\(a\equiv b(mod\ p)\)，且\(b\equiv c(mod\ p)\)，则\(a\equiv c(mod\ p)\)

令\(a=kp+r\)，\(b=k_1p+r\)，\(c=k_2p+r\)，则有\(a-c=k_3p\)，即 \(a\equiv c(mod\ p)\)

4.若\(a\equiv b(mod\ p)\)，且\(c\equiv d(mod\ p)\)，则\(a\pm c\equiv b\pm d(mod\ p)\)

证法与3相同

5.若\(a\equiv b(mod\ p)\)，且\(c\equiv d(mod\ p)\)，则\(ac\equiv bd(mod\ p)\)

令\(a=kp+r\)，\(b=k_1p+r\)，\(c=k_2p+r_1\)，\(d=k_3+r_1\)，则有\(ac=k_4p+rr_1\)，\(bd=k_5p+rr_1\)，即\((ac-bd)mod\ p=0\)

6.如果ac\equiv bc(mod\ p)，且 c和p互质，则有a\equiv b(mod\ p)

令\(a=kp+r\)，\(b=k_1p+r_1\)，\(c=k_2p+r_2\)，则有\(ac=k_3+rr_2\)，\(bc=k_4p+r_1r_2\)，即\(rr_2=r_1r_2\)，
又\(r_2\neq 0\)，所以\(r=r_1\)

7.若\(a\equiv b(mod\ p)\)，则\(a^c\equiv b^c(mod\ p)\)(\(c\in N\))

由第3条性质可得该性质

8.若\(a-b\equiv c(mod\ p)\)，则\(a\equiv c+b(mod\ p)\)

9.若\(a\equiv b(mod\ p)\)，且\(m|p\)，则\(a\equiv b(mod\ p)\)

令\(a=kp+r\)，\(b=k_1p+r\)
\(\because m|p\)
\(\therefore a=k_2m+r\)，\(b=k_3m+r\)

剩余类，完全剩余系，缩剩余系

• 剩余类：

对于所有模n余r的整数，我们可以将其分为n类，
那么\(\bar{r}_n=\{k\in Z|kn+r\}\)就为n余r剩余类。

比如模5的一个剩余类\(\cdots,-5,0,5,10,\cdots\)

• 完全剩余系：

若从\(\bar{0}_n,\bar{1}_n,\bar{2}_n,\cdots,\bar{(n-1)}_n\)中各挑选出一个数，便组成了模n的完全剩余系。
\(R(n)=\{0,1,2,\cdots,n-1\}\)称为模n的最小非负完全剩余系。

比如模5的一个(最小非负)完全剩余系0,1,2,3,4

• 缩剩余系

对于模n的完全剩余系，去所有与n互质的数，即为模n的缩剩余系\(\Phi_n\)。
\(\Phi_n=\{c_1,c_2,\cdots,c_{\Phi(n)}\}\)
若缩剩余系\(\Phi_n\)满足\(c_i\in [i,n-1]\)，那么就称为模n的最小正缩剩余系。

比如模6的一个(最小正)缩剩余系1,5