class="markdown_views prism-github-gist"> 原文：同余模定理 定义
所谓的同余，顾名思义，就是许多的数被一个数 d 去除，有相同的余数。d 数学上的称谓为模。如 a = 6, b = 1, d = 5, 则我们说 a 和 b 是模 d 同余的。因为他们都有相同的余数 1 。 数学上的记法为：
a≡ b(mod d) 可以看出当 n < d 的时候,所有的 n 都对 d 同商，比如时钟上的小时数，都小于 12，所以小时数都是模 12 的同余.对于同余有三种说法都是等价的,分别为:
(1) a 和 b 是模 d 同余的.
(2) 存在某个整数 n ,使得 a = b + nd .
(3) d 整除 a - b .
可以通过换算得出上面三个说话都是正确而且是等价的. 定律
同余公式也有许多我们常见的定律，比如相等律，结合律，交换律，传递律….如下面的表示:

1. a≡a(mod d)
2. a≡b(mod d)→b≡a(mod d)
3. (a≡b(mod d),b≡c(mod d))→a≡c(mod d)

如果a≡x(mod d),b≡m(mod d),则
4) a+b≡x+m （mod d）
5) a-b≡x-m(mod d)
6) ab≡xm(mod d ) 应用
$(a+b) \% c=(a\%c+b\%c)\%c$
$(a*b)\%c=(a\%c*b\%c)\%c$; 对于大数的求余，联想到进制转换时的方法，得到 举例如下，设大数 m=1234, 模 n 就等于
$((((1 * 10) \% n + 2 \% n) \% n * 10 \% n + 3 \% n) \% n * 10 \% n + 4 \% n) \% n$ 大数求余的简单模板： #include //大数求余，其中 n(除数）不是大数 char a[1000]; int main() { int i, j, k, m, n; while(~scanf("%s%d", a, &n)) { m = 0; for(i = 0; a[i] != '