同余

2019-04-14 16:40发布

 

【定义】

给定一个正整数m,如果二整数αb满足m│α-b((α-b)m整除),就称整数αb对模m同余,记作α≡b)(mod m)。对模m同余是整数的一个等价关系。

【基本性质】

1a≡a(mod k) 
2
a≡b(mod k)b≡a(mod k) 
3
a≡b(mod k),b≡c(mod k)a≡c(mod k) 
4
a≡b(mod k)a+c≡b+c(mod k) 
5
a≡b(mod k),c≡d(mod k)ac≡bd(mod k) 
6
a≡b(mod k)anbnan≡bn(mod k) 
推论 
1a·b%k=(a%k)·(b%k)%k         //快速幂
2a%p=xa%q=x,且gcd(p,q)=1,则a%(p·q)=x 
注意: 
 

[快速幂]

点这里