Java教程

同余

本文主要是介绍同余,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

定义:

若\((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

这篇关于同余的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!