# 数论四大定理## 中国剩余定理### 求解二元一次方程组的解#### 模数互质的情况#### a $\equiv$  b (mod c) --> a*n $\equiv$  b*n(mod cn)#### xa $\equiv$ m1(mod ab), xb $\equiv$ m2(mod ab) $\Rightarrow$ x(a+b) $\equiv$ (m1+m2)(mod ab) $\Rightarrow$ x $\equiv$ (m1+m2)inv(a+b)(mod ab)#### n  % abc % a= n % a#### (a + b) % c = a % c + b % c#### a / b % n = a * c % n $\Rightarrow$  inv(b) = c     inv(b + n) = c#### a % b = ((a * n) % (b * n) ) / na, b, c互质x $\equiv$  m1 (mod a)x $\equiv$  m2 (mod b)x $\equiv$  m3 (mod c)abx $\equiv$ abm3 (mod abc)acx $\equiv$ acm2 (mod abc)bcx $\equiv$ bcm3 (mod abc)x(ab + ac + ab) $\equiv$ (abm3 + acm2 + bcm1)(mod abc)x $\equiv$ (abm3 + acm2 + bcm1)inv(ab + ac + bc)(mod abc)x mod a = (abm3 + acm2 + bcm1)inv(ab + ac + ab)(mod abc) mod a $\Rightarrow$ x mod a  = bcm1 * inv(bc) (mod a) $\Rightarrow$ m1 =  bcm1 * inv(bc) bcm1 * inv(bc) % b = 0 bcm1 * inv(bc) % c = 0$\therefore$ x = ( abm3 * inv(ab) + acm2 * inv(ac) + bcm1 * inv(bc) ) (mod abc)#### 模数不互质a1 * x1  + y1 = ca2 * x2 + y2 = ca1 * x1 - a2 * x2 =  y2 - y1设x1 = x0是方程的一个解则设n = a1 * x0 + y1, 设m = lcm(a1, a2)  //lcm是最小公倍数则c = m * k + n    //(a + b) % c = a % c + b % c## 欧拉定理若n,a为正整数，且n,a互素，即gcd(a,n) = 1，则a^φ(n) ≡ 1 (mod n)     //φ(n)为欧拉函数## 费马小定理假如p是质数，且gcd(a,p)=1，那么a^p ≡a（mod p）## 威尔逊定理若p为质数， 则p可整除(p-1)! + 1;