JavaAlgorithm

同余定理

定义：给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。（a整除b == b能被a整除 == a|b == b / a 余数为0）

显然,有如下事实：

• 若a≡0(mod m)，则m|a；
• a≡b(mod m)等价于a与b分别用m去除，余数相同。

引申推论：

• (a+b)%m = (a%m+b%m)%m
• (ab)%m = ((a%m)(b%m))%m