小结：数论四大定理（威尔逊定理+欧拉定理+中国剩余定理+费马小定理）

模运算消去律：ac ≡ bc (mod p) → a ≡ b (mod p/gcd(c,p) )

当且仅当p为素数时，( p -1 )! ≡ -1 ( mod p )

当且仅当p为素数时，( p -1 )! ≡ p-1 ( mod p )

若p为质数，则p能被(p-1)!+1整除

当且仅当p为素数时，p∣(p−1)!+1

证明：https://brilliant.org/wiki/wilsons-theorem https://www.jianshu.com/p/ad5bb5b8fa7d

若正整数a和n互质，则 aφ(n) ≡ 1 (mod n) 若a,p互素， a φ ( p ) a^{φ( p)} aφ(p)≡1 (mod p) → a* a φ ( p ) − 1 a^{φ( p)-1} aφ(p)−1 ≡ 1 (mod p) 因此 a φ ( p ) − 1 a^{φ( p)-1} aφ(p)−1 为a mod p意义下的逆元’

证明：https://brilliant.org/wiki/eulers-theorem/

设 k 组数 (ai, ni), 其中 ni两两互素，要找到最小的正整数x， 满足方程组 x≡ai(mod ni)(i=1,2…k)

◼ 算法步骤: ◼ 令 n=n1n2…nk, mi=n/ni ◼ 显然 gcd(mi,ni)=1，用扩展欧几里德算法计算出 xi 满足mixi≡1(mod ni) ◼ 方程组的解 x = (a1x1m1+a2x2m2+…+akxkmk) mod n ◼ 方程组的任意两个解 模n同余，因此x就是最小的解。

证：因为 φ( p) = p-1，代入欧拉定理即证

若p为素数，ap-1≡1 (mod p) → a*ap-2 ≡ 1 (mod p) 因此 ap-2 为a mod p意义下的逆元