原文转载链接：
https://blog.csdn.net/baodream/article/details/80529917

威尔逊定理

当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
或者这么写( p -1 )! ≡ p-1 ( mod p )
或者说若p为质数，则p能被(p-1)!+1整除

欧拉定理

欧拉定理，也称费马-欧拉定理
若n,a为正整数，且n,a互质，即gcd(a,n) = 1，则
数论四大定理 - 图1

  1. /*欧拉函数解法：
  2. Euler函数表达通式(即解法)：E(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…(1-1/pn),
  3. 其中p1,p2……pn为x的所有素因数，x是不为0的整数。E(1)=1（唯一和1互质的数就是1本身）。*/
  4. //复杂度:O（√n）
  5. int phi(int x){
  6.     int ans=x;
  7.     for(int i=2;i*i<=x;i++){
  8.         if(x%i == 0){
  9.             ans = ans/i * (i-1);
  10.             while(x % i==0) x/=i;
  11.         }
  12.     }
  13.     if(x>1) ans = ans/x*(x-1);
  14.     return ans;
  15. }
  17. //欧拉筛
  18. //1.跟埃筛素数差不多
  19. const int N = 1e6+5;
  20. int phi[N];
  22. void Euler(int n){  //筛出所有小于等于n的欧拉函数值
  23.     memset(phi,0,sizeof(phi));
  24.     phi[1]=1;
  25.     for(int i=2;i<=n;i++){
  26.         if(!phi[i]){
  27.             for(int j=i;j<=n;j+=i){
  28.                 if(!phi[j]) phi[j] = j;
  29.                 phi[j] = phi[j]/i*(i-1);
  30.             }
  31.         }
  32.     }
  33. }
  34. //2.比上面更快的方法，需要用到如下性质。当p为质数：
  35. //(1). phi(p)=p-1   因为质数p除了1以外的因数只有p，故1至p的整数只有p与p不互质
  36. //(2). 如果i mod p = 0, 那么 phi(i * p)=phi(i) * p
  37. //(3).若i mod p ≠0,  那么 phi( i * p )=phi(i) * ( p-1 )
  38. const int N = 1e6+5;
  39. int phi[N],prime[N];
  40. int tot;  //计数,表示prime[N]中有多少质数
  41. void Euler(int n){  筛出所有小于等于n的欧拉函数值和素数
  42.     memset(phi,0,sizeof(phi));
  43.     tot=0,phi[1]=1;
  44.     for(int i=2;i<=n;i++){
  45.         if(!phi[i]){
  46.             phi[i] = i-1;
  47.             prime[tot++]=i;
  48.         }
  49.         for(int j=0;j<tot&&1ll*i*prime[j]<=n;j++){
  50.             if(i%prime[j]!=0) phi[i*prime[j]] = phi[i] * (prime[j]-1);
  51.             else{
  52.                 phi[i*prime[j]] = phi[i]*prime[j];
  53.                 break;
  54.             }
  55.         }
  56.     }
  57. }

孙子定理（中国剩余定理）

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：
数论四大定理 - 图2
中国剩余定理说明：假设整数 数论四大定理 - 图3 两两互质，则对任意的整数：数论四大定理 - 图4，方程组 (S)有解。
并且通解可以用如下方式构造得到：
设数论四大定理 - 图5 是整数 数论四大定理 - 图6 的乘积，并设数论四大定理 - 图7 是除了 数论四大定理 - 图8 以外的n- 1个整数的乘积。
设数论四大定理 - 图9 ，这个就是逆元了。则 数论四大定理 - 图10
通解形式为：
数论四大定理 - 图11 ,k是整数。
在模M的意义下，方程组(S)只有一个解：
数论四大定理 - 图12
代码模板：

  1. void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d){
  2.     if (!b) {d = a, x = 1, y = 0;}
  3.     else{
  4.         ex_gcd(b, a % b, y, x, d);
  5.         y -= x * (a / b);
  6.     }
  7. }
  8. ll inv(ll t, ll p){//如果不存在，返回-1
  9.     ll d, x, y;
  10.     ex_gcd(t, p, x, y, d);
  11.     return d == 1 ? (x % p + p) % p : -1;
  12. }
  14. //n个方程：x=a[i](mod m[i]) (0<=i<n)
  15. ll china(int n, ll *a, ll *m){
  16.     ll M = 1, ret = 0;
  17.     for(int i = 0; i < n; i ++) M *= m[i];
  18.     for(int i = 0; i < n; i ++){
  19.         ll w = M / m[i];
  20.         ret = (ret + w * inv(w, m[i]) * a[i]) % M;  //这里用ex_gcd求逆元,因为他们是两两互质,而m[i]不一定是质数
  21.     }
  22.     return (ret + M) % M;
  23. }

费马小定理

假如p是质数，若p不能整除a，即a不是p的倍数，则 数论四大定理 - 图13 ，若p能整除a，则a^(p-1) ≡0（mod p）。

费马大定理

当整数n >2时，关于x, y, z的方程 数论四大定理 - 图14 没有正整数解。