同余
2019-04-14 16:40发布
生成海报
【定义】
给定一个正整数m,如果二整数α、b满足m│α-b((α-b)被m整除),就称整数α、b对模m同余,记作α≡b)(mod m)。对模m同余是整数的一个等价关系。
【基本性质】
1、a≡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)⇒ an≡bn⇒ an≡bn(mod k) 推论 1、a·b%k=(a%k)·(b%k)%k //快速幂2、a%p=x,a%q=x,且gcd(p,q)=1,则a%(p·q)=x 注意:
[快速幂]
点这里
打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮