1. 定义

   同余定理是数论中的一个重要概念。它的定义是这样的：给定一个整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m 得到一个整数，那么就成整数a和b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。

   简言之：两个整数同时除以一个整数得到的余数相同，则二整数同余。

2. 定理

 两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。
 记作：a≡b (mod m)，
 读作：a同余于b模m，或读作a与b对模m同余，例如         26≡2(mod 12)。

    设m是大于1的正整数，a、b是整数，如果m|(a-b)，则称a与b关于模m同余，记作a≡b(mod m)，读作a与b对模m同余。
   显然,有如下事实
（1）若a≡0(mod m)，则m|a；
（2）a≡b(mod m)等价于a与b分别用m去除，余数相同。

    3.同余方程

        同余方程就是同余式里加了一个需要我们求解的未知数。

        比如，一种同余方程（就是我们首先要讲的一次同余方程）长成这个样子：

                ax≡b(mod p)

    4.定理扩展

• 反身性：a≡a (mod m)；

• 对称性：若a≡b(mod m)，则b≡a (mod m)；

• 传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)；

• 同余式相加：若a≡b(mod m)，c≡d(mod m)，则a c≡b d(mod m)；

• 同余式相乘：若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)。

• 线性运算：如果a ≡ b (mod m)，c ≡ d (mod m)，那么

• a ± c ≡ b ± d (mod m)；

• a * c ≡ b * d (mod m)。

• 7.除法：若ac ≡ bc (mod m) c≠0 则 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数。特殊地 ,gcd(c,m)=1 则a ≡ b (mod m)

• 8.幂运算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)

• 9.若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)

• 10.若a ≡ b (mod mi) (i=1,2…n) 则 a ≡ b (mod [m1,m2,…mn]) 其中[m1,m2,…mn]表示m1,m2,…mn的最小公倍数

    还有我们以前经常见到的下面的操作（同余加减法）：

（a+b）%p=(a%p+b%p)%p;
（a*b）%p=a%p*b%p;
 a/b%m = (a%(b*m))/b%m；

•     高精度取模：

12345 = ( ( (1 * 10 +2 ) * 10 +3 ) * 10 + 4 ) * 10 + 5)

 5.相关定理

• 欧拉函数

• 费马小定理

6.例题以及应用

•      快速幂

•      爆int问题

•      大数取模