同余定理

2019-04-13 21:28发布

参考链接
原理:
  • 如果两个数a和b之差能被m整除,那么我们就说a和b对模数m同余(关于m同余)。
  • 比如,100-60除以8正好除尽,我们就说100和60对于模数8同余。
  • 另一层含义就是说,100和60除以8的余数相同。a和b对m同余,我们记作a≡b(mod m)。
  • 再比如,刚才的例子可以写成100≡60(mod 8)。
性质:
  1. 如果a≡b(mod m),x≡y(mod m),则a+x≡b+y(mod m)。
  2. 如果a≡b(mod m),x≡y(mod m),则ax≡by(mod m)。
  3. 如果ac≡bc(mod m),且c和m互质,则a≡b(mod m) 。