一、同余概述
1、基本定理
定义：给定正整数 m,a,bm,a,bm,a,b，若 m mod a=m mod bm\ mod\ a=m\ mod\ bm mod a=m mod b ，则称 aaa 和 bbb 对模 mmm 同余，记作 a≡b (mod m)a≡b\ (mod\ m)a≡b (mod m)，并称该式子为同余式；否则称 aaa 和 bbb 对模 mmm 不同余。
费马小定理：若 ppp 是质数，则 ∀a∈N+,ap≡a (mod p)\forall a\in N^+,a^p≡a\ (mod\ p)∀a∈N+,ap≡a (mod p) 。
欧拉定理：若正整数 a,ba,ba,b 互质，则 aϕ(b)≡1 (mod b)a^{\phi(b)}≡1\ (mod\ b)aϕ(b)≡1 (mod b)，其中 ϕ(b)\phi(b)ϕ(b) 为欧拉函数，其定义为：若正整数 xxx 有 mmm 个不同质因数，分别记为 p1,p2,...pm−1,pmp_1,p_2,...p_{m-1},p_mp1 ,p2 ,...pm−1 ,pm ，则 ϕ(x)=x∏i=1m(1−1pi)\phi(x)=x\prod_{i=1}^{m}(1-\frac{1}{p_i})ϕ(x)=x∏i=1m (1−pi 1 ) 。
2、同余性质
对于正整数 a,b,c,ma,b,c,ma,b,c,m，对模 mmm 同余满足：
1. a≡a (mod m)a≡a\ (mod\ m)a≡a (mod m)
2. a≡b (mod m)⇒b≡a (mod m)a≡b\ (mod\ m)\Rightarrow b≡a\ (mod\ m)a≡b (mod m)⇒b≡a (mod m)
3. a≡b (mod m),b≡c (mod m)⇒a≡c (mod m)a≡b\ (mod\ m),b≡c\ (mod\ m)\Rightarrow a≡c\ (mod\ m)a≡b (mod m),b≡c (mod m)⇒a≡c (mod m)
4. a≡b (mod m)⇒a+c≡b+c (mod m)a≡b\ (mod\ m)\Rightarrow a+c≡b+c\ (mod\ m)a≡b (mod m)⇒a+c≡b+c (mod m)
5. a≡b (mod m),c≡d (mod m)⇒ac≡bd (mod m)a≡b\ (mod\ m),c≡d\ (mod\ m)\Rightarrow ac≡bd\ (mod\ m)a≡b (mod m),c≡d (mod m)⇒ac≡bd (mod m)
6. a≡b (mod m)⇒ac≡bc (mod m)a≡b\ (mod\ m)\Rightarrow a^c≡b^c\ (mod\ m)a≡b (mod m)⇒ac≡bc (mod m)
7. a≡b (mod m),gcd(a,b)=1⇒a≡ab (mod m)a≡b\ (mod\ m),gcd(a,b)=1\Rightarrow a≡ab\ (mod\ m)a≡b (mod m),gcd(a,b)=1⇒a≡ab (mod m)
二、算法扩展
欧几里得算法：∀a,b∈N,gcd(a,b)=gcd(b,a mod b)\forall a,b\in N,gcd(a,b)=gcd(b,a\ mod\ b)∀a,b∈N,gcd(a,b)=gcd(b,a mod b) 。
定理：设 a,ba,ba,b 不全为 000，则 ∃x,y∈N,ax+by=gcd(a,b)\exists x,y\in N,ax+by=gcd(a,b)∃x,y∈N,ax+by=gcd(a,b) 。
代码实现（求解 ax+by=gcd(a,b)=dax+by=gcd(a,b)=dax+by=gcd(a,b)=d 的一组解 x,yx,yx,y）：
参考资料《信息学奥赛一本通 · 提高篇》，本人水平有限，如有疑问，欢迎指正！
