数论四大定理

中国剩余定理

求解二元一次方程组的解

模数互质的情况

a \(\equiv\) b (mod c) --> an \(\equiv\) bn(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) ) / n

a, 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 = c

a2 * x2 + y2 = c

a1 * 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;