【数论】同余定理与同余方程
定义
同余定理是数论中的一个重要概念。它的定义是这样的：给定一个整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m 得到一个整数，那么就成整数a和b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。
简言之：两个整数同时除以一个整数得到的余数相同，则二整数同余。
定理
两个整数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.例题以及应用
(adsbygoogle = window.adsbygoogle || []).push({});