同余理论相关

一.取模与同余的定义.

取模：定义 $a$对 $b$取模后的值 $a\,\,mod\,\,b=a-\left[\frac{a}{b}\right] b$，其中 $[]$表示向 $0$取整， $b$必须为正整数.

同余：定义 $a$和 $b$在模 $n$意义下同余，意为 $a\,\,mod\,\,n=b\,\,mod\,\,n$，记为 $a\equiv b\,\,(mod\,\,n)$.

接下来若无特殊说明，则所有同余式中的未知数都是在模意义下的，即值域是小于模数的自然数.

定理1： $b<a\Rightarrow 2(a\,\,mod\,\,b)\leq b$.

分类讨论即可证明.


二.同余的基本性质.

自反性： $a\equiv a\,\,(mod\,\,n)$.

对称性： $a\equiv b\,\,(mod\,\,n)\Rightarrow b\equiv a\,\,(mod\,\,n)$.

传递性： $a\equiv b\,\,(mod\,\,n),b\equiv c\,\,(mod\,\,n)\Rightarrow a\equiv c\,\,(mod\,\,n)$.

模意义下的加法性质：
$a\pm b\equiv (a\,\,mod\,\,n)\pm(b\,\,mod\,\,n)\,\,(mod\,\,n)\\ a\equiv b\Leftrightarrow a\pm c\equiv b\pm c\,\,(mod\,\,n)$

模意义下的乘法性质：
$ab\equiv (a\,\,mod\,\,n)(b\,\,mod\,\,n)\,\,(mod\,\,n)\\ a\equiv b\Rightarrow ac\equiv bc\,\,(mod\,\,n)$

但不幸的是， $a\equiv b\,\,(mod\,\,n)$并不是 $ac\equiv bc\,\,(mod\,\,n)$的必要条件.

完全剩余系：定义 $n$的完全剩余系 $S_n=\{x\in N|x\in [0,n)\}$.

定理2： $ac\equiv bc\,\,(mod\,\,n)\Rightarrow a\equiv b\,\,\left(mod\,\,\frac{n}{\gcd(n,c)}\right)$.

证明：
首先 $ac\equiv bc\,\,(mod\,\,n)\Rightarrow n|(ac-bc)=c(a-b)$，此时假设 $c(a-b)=kn$并令 $g=\gcd(n,c)$，同时除掉 $g$，得到：
$\frac{c}{g}(a-b)=\frac{kn}{g}$

由于 $\gcd\left(\frac{c}{g},\frac{n}{g}\right)=1$，必然有 $\frac{n}{g}|(a-b)$，即 $a\equiv b\,\,\left(mod\,\,\frac{n}{g}\right)$.
证毕.

这个性质补充了上面乘法满足消去律的条件.

定理2的推论：若 $\gcd(n,c)=1$且 $ac\equiv bc\,\,(mod\,\,n)$，则有 $a\equiv b\,\,(mod\,\,n)$.

简化剩余系：定义 $n$的简化剩余系为 $S_n$为 $n$完全剩余系的一个子集，且任意 $x\in S_n$满足 $\gcd(n,x)=1$.

同时，模意义下加法交换律，加法结合律，乘法交换律，乘法结合律，分配律仍然满足，即：
$a+b\equiv b+a\,\,(mod\,\,n)\\ a+b+c\equiv a+(b+c)\,\,(mod\,\,n)\\ ab\equiv ba\,\,(mod\,\,n)\\ abc\equiv a(bc)\,\,(mod\,\,n)\\ a(b+c)\equiv ab+ac\,\,(mod\,\,n)$

定理3： $n$的简化剩余系与模 $n$意义下的乘法构成一个群.

证明：
考虑一一证明它满足群的性质：
封闭性：若 $\gcd(n,x)=\gcd(n,y)=1$，则 $\gcd(n,xy\,\,mod\,\,n)=\gcd(n,xy)=1$.
结合律：显然.
单位元：单位元为 $1$.
可逆性：根据定理2有消去律，以此推出可逆性.
证毕.


三.快速幂与快速乘.

在取模的意义下，我们是有办法用计算机内置的整型变量存储一个幂 $a^k$的值的.于是现在就有了一个问题，如何快速求幂？

把 $k$按照二进制拆分，我们可以把 $a^k$分解为：
$a^k=\prod_{k\&2^{i}\neq 0}a^{2^{i}}$

例如 $3^{5}=3^{(101)_2}=3^{2^{2}}*3^{2^{0}}=3^{4}*3^{0}=243$.

代码如下：

int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

int Power(int a,int k,int p=mod){
  int res=1;
  for (;k;k>>=1,smul(a,a,p))
    if (k&1) smul(res,a,p);
  return res;
}

有时候模数过大时，直接乘法会把long long都给爆掉，此时还有一个与快速幂原理类似的快速乘，也就是用加法代替上面的乘法后的快速幂.

代码如下：

LL add(LL a,LL b,LL p=mod){return a+b>=p?a+b-p:a+b;}
LL sadd(LL &a,LL b,LL p=mod){a=add(a,b,p);}

LL mul(LL a,LL k,LL p=mod){
  LL res=0;
  for (;k;k>>=1,sadd(a,a,p))
    if (k&1) sadd(res,a,p);
  return res;
}

两个算法的时间复杂度均为 $O(\log k)$.

当然，我们知道 $a\,\,mod\,\,b=a-\left\lfloor\frac{a}{b}\right\rfloor b$，并且C++中还内置了一个非常大的实数类型long double，所以我们还可以写出一个用long double的 $O(1)$快速乘：

LL mul(LL a,LL b,LL p=mod){
  LL t=(long double)a/p*b+1e-8,res=a*b-t*p;
  return res<0?res+p:res;
}

四.剩余系与欧拉函数.

定理4：若 $\gcd(n,m)=1$，设 $S_{n},S_{m},S_{nm}$分别为 $n,m,nm$的完全剩余系，则有：
$S_{nm}=\{(an+bm)\,\,mod\,\,nm|a\in S_{m},b\in S_{n}\}$

证明：
显然集合 $S=\{(an+bm)\,\,mod\,\,nm|a\in S_{m},b\in S_{n}\}\subseteq S_{nm}$，此时我们只需要证明 $|S|=|S_{nm}|$，等价于证明不存在 $a,c\in S_{m},b,d\in S_{n}$满足 $an+bm\equiv cn+dm\,\,(mod\,\,nm)$，其中 $a\neq c$或 $b\neq d$.
假设存在，显然有：
$an+bm\equiv cn+dm\,\,(mod\,\,nm)\\ \Leftrightarrow nm|[n(a-c)+m(b-d)]\\ \Leftrightarrow m|(a-c)\wedge n|(b-d)\\ \Leftrightarrow a\equiv c\,\,(mod\,\,m)\wedge b\equiv d\,\,(mod\,\,n)$

假设不成立.
证毕.

定理5：若 $\gcd(n,m)=1$，设 $S_{n},S_{m},S_{nm}$分别为 $n,m,nm$的简化剩余系，则有：
$S_{nm}=\{(an+bm)\,\,mod\,\,nm|a\in S_{m},b\in S_{n}\}$

证明：
而当 $\gcd(n,m)=1$时，假设 $a$遍取 $m$的完全剩余系， $b$遍取 $n$的完全剩余系，则有：
$\gcd(nm,an+bm)=1\\ \Leftrightarrow \gcd(n,an+bm)=1\wedge \gcd(m,an+bm)=1\\ \Leftrightarrow \gcd(n,bm)=1\wedge \gcd(m,an)=1\\ \Leftrightarrow \gcd(n,b)=1\wedge \gcd(m,a)=1$

证毕.

定理5的推论： $\gcd(n,m)=1\Rightarrow \phi(nm)=\phi(n)\phi(m)$.

根据欧拉函数的积性，我们还可以推导出欧拉函数的计算公式：设 $n$的唯一分解式 $n=\prod_{i=1}^{k}p_i^{c_i}$，则有：
$\phi(n)=n\prod_{i=1}^{k}\frac{p_i-1}{p_i}$

证明：
$\phi(n)=\prod_{i=1}^{k}\phi(p_i^{c_i})\\ =\prod_{i=1}^{k}(p_i^{c_i}-p_i^{c_i-1})\\ =\prod_{i=1}^{k}p_i^{c_i}\frac{p_i-1}{p_i}\\ =n\prod_{i=1}^{k}\frac{p_i-1}{p_i}$

证毕.


五.欧拉定理.

欧拉定理： $\gcd(n,a)=1\Rightarrow a^{\phi(n)}=1\,\,(mod\,\,n)$.

证明：
设 $n$的简化剩余系为 $S_n$，由于 $S_n$和模 $n$意义下的乘法构成一个群，所以有：
$x\in S_n\Rightarrow ax\,\,mod\,\,n\in S_n\\ x,y\in S\wedge x\neq y\Rightarrow ax\not\equiv ay\,\,(mod\,\, n)$

那么显然 $S'_n=\{ax\,\,mod\,\,n|x\in S_n\}$与 $S_n$同是 $n$的简化剩余系.

那么就有：
$a^{\phi(n)}\prod_{x\in S_n}x\equiv \prod_{x\in S_n}ax\equiv \prod_{x\in S_n}x\,\,(mod\,\,n)$

可以同时去掉 $\prod_{x\in S_n}x$，得到 $a^{\phi(n)}\equiv 1\,\,(mod\,\,n)$.
证毕.

费马小定理：若 $n$为素数且 $a$不是 $n$的倍数，则有 $a^{n-1}\equiv 1\,\,(mod\,\,n)$.

欧拉定理的推论：当 $\gcd(a,n)=1$时， $a^k\equiv a^{k\,\,mod\,\,\phi(n)}\,\,(mod\,\,n)$.

扩展欧拉定理：若 $k\geq \phi(n)$，则 $a^{k}\equiv a^{k\,\,mod\,\,\phi(n)+\phi(n)}\,\,(mod\,\,n)$.

证明：
为了证明这个定理，我们先证明 $a$为素数时定理成立：
设 $n=a^{r}n'$，其中 $\gcd(a,n')=1$，此时有：
$a^{\phi(n')}\equiv 1\,\,(mod\,\,n')$

由于 $\phi(n')|\phi(n)$，有：
$a^{\phi(n)}\equiv 1\,\,(mod\,\,n')$

同时让两边和模数乘上 $a^{r}$，得到：
$a^{\phi(n)+r}\equiv a^{r}\,\,(mod\,\,n)$

于是有：
$a^{k+r}\equiv a^{k\,\,mod\,\,\phi(n)+r}\,\,(mod\,\,n)$

显然有 $k\geq \phi(n)=(a-1)a^{r-1}\phi(n')\geq r$，所以有：
$a^{k}\equiv a^{r+k-r}\equiv a^{r+\phi(n)+(k-r)\,\,mod\,\,\phi(n)}\equiv a^{r\,\,mod\,\,\phi(n)+(k-r)\,\,mod\,\,\phi(n)+\phi(n)}\equiv a^{k\,\,mod\,\,r+\phi(n)}\,\,(mod\,\,n)$

至此我们证明了 $a$为素数的情况.
那么对于素数的幂 $a=p^{c}$，有：
$p^{k}\equiv p^{k\,\,mod\,\,\phi(n)+\phi(n)}\,\,(mod\,\,n)\\ \Rightarrow (p^{k})^c\equiv (p^{k\,\,mod\,\,\phi(n)+\phi(n)})^{c}\,\,(mod\,\,n)\\ \Rightarrow a^{k}\equiv a^{k\,\,mod\,\,\phi(n)+\phi(n)}\,\,(mod\,\,n)$

对于任意一个数 $a$，直接写出它的唯一分解形式，会得到一些下面的式子：
$(p_i^{c_i})\equiv (p_i^{c_i})^{k\,\,mod\,\,\phi(n)+\phi(n)}\,\,(mod\,\,n)$

把左右两边分别相乘即可得到原定理.
证毕.


六.线性同余方程求解.

同余方程：在模意义下求解的方程称为同余方程.

一般来说，我们求模 $n$意义下同余方程的解都是在 $[0,n)$范围内的整数.

线性同余方程：形如 $\sum_{i=1}^{m}a_ix_i\equiv c\,\,(mod\,\,n)$的同余方程称为线性同余方程.

关于线性同余方程的求解，通常是将其转化为如下形式：
$\sum_{i=1}^{m}a_ix_i-nx=c$

然后就可以套线性丢番图方程的求解方法了.

与一般线性丢番图方程求解不同的是，这个问题是可以用一些技巧做到不爆long long的.

代码如下：

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

int Ex_gcd(int a,int b,int &x,int &y){
  if (!b) {x=1;y=0;return a;}
  int g=Ex_gcd(b,a%b,y,x);
  y-=a/b*x;
  return g;
}

int t[N+9];

bool Get_root(int *a,int n,int c,int p=mod,int *res){
  a[++n]=p;
  int g=a[1];
  res[1]=t[n]=1;
  for (int i=2;i<=n;++i) g=Ex_gcd(g,a[i],t[i-1],res[i]);
  if (c%g) return 0;
  c/=g;
  for (int i=n-1;i>=1;--i){
  	smul(t[i]+=(t[i]%=p)<0?p:0,t[i+1],p);
  	smul(res[i]+=(res[i]%=p)<0?p:0,t[i],p);
  }
  for (int i=1;i<=n;++i) smul(res[i],c,p);
  return 1;
}

七.模意义下的乘法逆元.

逆元：一般数论中的逆元是指在模 $n$意义下的乘法逆元，即对于一个整数 $a$，逆元是指一个满足 $ax\equiv 1\,\,(mod\,\,n)$的整数 $x$，通常情况下要求 $x$是 $[1,n)$内的整数.

通常来说，若模数 $n$没有特殊性质，则求逆元可以转化为线性同余方程来解决，即转化为：
$ax\equiv 1\,\,(mod\,\,n)\Leftrightarrow ax-ny=1$

同时，根据裴蜀定理，我们也能知道在 $\gcd(n,a)\neq 1$时， $a$在模 $n$意义下不存在逆元.

逆元的唯一性：在模 $n$意义下一个数 $a$只有最多一个逆元.

证明：
显然逆元定义转化后得到的式子通解为：
$x=x_0+kn$

它们在模 $n$意义下必然同余.
证毕.

在 $n$为素数的时候，一个优美的性质是，所有 $[1,n)$上的整数都存在模 $n$意义下的逆元.

可以用费马小定理来求解，或者套用模数为素数时逆元的递推公式.

逆元递推公式： $i^{-1}\equiv -\left\lfloor\frac{n}{i}\right\rfloor(n\,\,mod\,\,i)^{-1}\,\,(mod\,\,n)$.

证明：
$n\equiv 0\,\,(mod\,\,n)\\ \left\lfloor\frac{n}{i}\right\rfloor i+(n\,\,mod\,\,i)\equiv 0\,\,(mod\,\,n)\\ n\,\,mod\,\,i\equiv -\left\lfloor\frac{n}{i}\right\rfloor i\,\,(mod\,\,n)\\ i^{-1}\equiv -\left\lfloor\frac{n}{i}\right\rfloor(n\,\,mod\,\,i)^{-1}\,\,(mod\,\,n)$

证毕.

用这个递推公式可以在 $O(n)$的时间复杂度内求出 $[1,n]$在模一个质数意义下的逆元.

代码如下：

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

int n,inv[N+9];

void Get_inv(int p=mod){
  inv[1]=1;
  for (int i=2;i<=n;++i) inv[i]=mul(p-p/i,inv[p%i],p);
}

同时，我们还可以直接用公式递归求解 $n$的逆元.根据定理1得到这个做法的时间复杂度为 $O(\log n)$.

代码如下：

int mul(int a,int b,int p=mod){return (LL)a*b%p;}
int Get_inv(int n,int p=mod){return mul(p-p/n,Get_inv(p%n,p),p);}

美中不足的是，这个做法不能 $O(n)$预处理任意 $n$个数 $x_1,x_2,x_3,\cdots x_n$的逆元.但是我们有另一个离线求逆元的简单方法.

具体就是分三步走：
$x^{-1}=(\prod_{i=1}^{n}x_i)^{-1}\,\,mod\,\,p\\ mul_i\equiv (\prod_{j=1}^{i}x_j)^{-1}\equiv x_{i+1}mul_{i+1}\,\,(mod\,\,p)\\ x_i^{-1}\equiv mul_i\prod_{j=1}^{i-1}x_j\,\,(mod\,\,p)$

若 $p$为素数，可以在 $O(\log p)$的时间复杂度内求出 $x^{-1}\,\,mod\,\,p$.

时间复杂度 $O(n+\log p)$.

代码如下：

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}
int Power(int a,int k,int p=mod){int res=1;for (;k;k>>=1,smul(a,a,p)) if (k&1) smul(res,a,p);return res;}
int Get_inv(int a,int p=mod){return Power(a,p-2,p);}

int n,a[N+9],inv[N+9];

void Get_inv(int p=mod){
  inv[n]=1;
  for (int i=1;i<=n;++i) smul(inv[n],a[i],p);
  inv[n]=Get_inv(inv[n],p);
  for (int i=n-1;i>=1;--i) inv[i]=mul(inv[i+1],a[i+1],p);
  int t=1;
  for (int i=1;i<=n;++i) smul(inv[i],t,p),smul(t,a[i],p);
}

八.线性同余方程组与中国剩余定理.

线性同余方程组：由线性同余方程组成的方程组称为线性同余方程组.

这里我们主要解决如下的线性同余方程组：
$\left\{\begin{matrix} x\equiv a_1\,\,(mod\,\,m_1)\\ x\equiv a_2\,\,(mod\,\,m_2)\\ \vdots\\ x\equiv a_n\,\,(mod\,\,m_n) \end{matrix}\right.$

中国剩余定理：对于上面的线性同余方程组，若 $m_i$两两互素，则存在一个解 $x$满足：
$M_i=\frac{\prod_{j=1}^{n}m_j}{m_i},M_ix_i\equiv 1\,\,(mod\,\,m_i)\Rightarrow x=\sum_{i=1}^{n}a_ix_iM_i$

证明：
若 $i\neq j$，必然有 $M_i\equiv 0\,\,(mod\,\,m_j)$，否则必然有：
$x_iM_i\equiv 1\,\,(mod\,\,m_i)\Rightarrow a_ix_iM_i\equiv a_i\,\,(mod\,\,m_i)$

显然只要 $x_iM_i\equiv 1\,\,(mod\,\,m_i)$存在解，这个定理就可以用了.
此时根据 $m_i$两两互质，有 $\gcd(m_i,M_i)=1$，这个方程必然有解.
证毕.

这个东西求解线性同余方程组的时间复杂度为 $O(n\log m)$.

代码如下：

int add(int a,int b,int p){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p){return (LL)a*b%p;}
void sadd(int &a,int b,int p){a=add(a,b,p);}
void ssub(int &a,int b,int p){a=sub(a,b,p);}
void smul(int &a,int b,int p){a=mul(a,b,p);}

int Ex_gcd(int a,int b,int &x,int &y){
  if (!b) {x=1;y=0;return a;}
  int g=Ex_gcd(b,a%b,y,x);
  y-=a/b*x;
  return g;
}

int Get_inv(int a,int p){int res,y,g=Ex_gcd(a,p,res,y);return g^1?-1:(res%=p)<0?res+p:res;}

int CRT(int *a,int *m,int n){
  int res=0,mod=1;
  for (int i=1;i<=n;++i) mod*=m[i];
  for (int i=1;i<=n;++i)
    sadd(res,mul(a[i],mul(Get_inv(mod/m[i],m[i]),mod/m[i],mod),mod),mod);
  return res;
}

从上面的过程中可以看出，当 $m_i$不满足两两互质的时候，中国剩余定理就无法求解了.

那么怎么求解呢？我们可以考虑通过前 $i-1$个方程的解求出前 $i$个方程的解.

具体来说，若我们有了前 $i-1$个方程的解 $x$，设 $m=\mathrm{lcm}_{j=1}^{i-1}\{m_i\}$，那么前 $i-1$个方程的通解为 $x+km$，此时我们把问题变为如何求 $x+km\equiv a_{i}\,\,(mod\,\,m)$.

容易发现这是一个线性同余方程，直接用exgcd求解.

时间复杂度 $O(n\log m)$.

代码如下：

int add(int a,int b,int p){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p){return (LL)a*b%p;}
void sadd(int &a,int b,int p){a=add(a,b,p);}
void ssub(int &a,int b,int p){a=sub(a,b,p);}
void smul(int &a,int b,int p){a=mul(a,b,p);}

int Ex_gcd(int a,int b,int &x,int &y){
  if (!b) {x=1;y=0;return a;}
  int g=Ex_gcd(b,a%b,y,x);
  y-=a/b*x;
  return g;
}

int CRT(int *a,int *mo,int n){
  int res=a[1],mod=mo[1];
  for (int i=2;i<=n;++i){
  	int x,y,c=sub(a[i],res%mo[i],mo[i]),g=Ex_gcd(mod,mo[i],x,y);
  	if (c%g) return -1;
  	int t=mo[i]/g;
	x=mul((x%=t)<0?x+t:x,c/g,t)*mod;
  	mod*=mo[i]/g;sadd(res,x,mod);
  }
  return res;
}

九.威尔逊定理.

二次探测定理：对于一个素数 $n$，若有 $x$满足 $x^2\equiv 1\,\,(mod\,\,n)$，则必然有 $x=1$或 $x=n-1$.

证明：
首先 $n=2$时定理显然成立.
$x^2\equiv 1\,\,(mod\,\,n)\Leftrightarrow n|(x^2-1)\Leftrightarrow n|(x+1)(x-1)\Leftrightarrow n|(x+1)\vee n|(x-1)$

由于 $p$为素数，所以只能取 $x=1$或 $x=p-1$.
证毕.

威尔逊定理： $n$是素数 $\Rightarrow (n-1)!\equiv -1\,\,(mod\,\,n)$.

证明：
显然定理等价于 $n$是素数 $\Rightarrow (n-2)!\equiv 1\,\,(mod\,\,n)$.
令 $S=\{2,3,4,\cdots,n-2\}$，此时根据二次探测定理，对于任意 $x\in S$，不可能有 $x^2\equiv 1\,\,(mod\,\,n)$.

同时根据逆元的唯一性，就可以把 $S$中的元素两两配对使得 $xy\equiv 1\,\,(mod\,\,n)$，也就是说：
$\prod_{i=2}^{n-2}i\equiv (n-2)!\equiv 1\,\,(mod\,\,n)$

证毕.

威尔逊定理逆定理： $(n-1)!\equiv -1\,\,(mod\,\,n)\Rightarrow n$是素数.

证明：
首先我们知道 $n$为素数时 $(n-1)!\equiv -1\,\,(mod\,\,n)$，接下来只需要证明 $n$不为素数时不满足 $(n-1)!\equiv -1\,\,(mod\,\,n)$即可.
若 $n$不为素数，必然存在两个整数 $a,b\in (1,n)$满足 $ab=n$，即 $ab\equiv 0\,\,(mod\,\,n)$，分两类讨论：
1.若 $a\neq b$，则 $(n-1)!$中必然含有 $ab$， $(n-1)!\equiv 0\,\,(mod\,\,n)$.
2.若 $a=b$，除 $n=4$时 $(n-1)!\equiv 2\,\,(mod\,\,n)$外，必然有 $a>2$，此时 $(n-1)!$必然含有 $a(2a)$，即 $(n-1)!\equiv 0\,\,(mod\,\,n)$.
证毕.


十.组合数取模与Lucas定理.

关于组合数取模，首先有一个小定理.

定理6： $n$为素数时，若 $m$不为 $0$或 $n$，则有 $\binom{n}{m}\equiv 0\,\,(mod\,\,n)$.

证明：
暴力提出 $n$：
$\binom{n}{m}\equiv \frac{n!}{m!(n-m)!}\equiv n\frac{(n-1)!}{m!(n-m)!}\equiv 0\,\,(mod\,\,n)$

证毕.

至于为什么 $m=0$或 $m=n$时不行，那是因为这个时候在模意义下除 $0$了.

我们再来看一个被称为组合数取模的问题：给定 $n,m,p$，求 $\binom{n}{m}\,\,mod\,\,p$，其中 $n,m$很大但 $p$比较小.

Lucas定理：若 $p$为素数，则有 $\binom{n}{m}=\binom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}\binom{n\,\,mod\,\,p}{m\,\,mod\,\,p}\,\,(mod\,\,p)$.

证明：
写出组合数的生成函数：
$\sum_{i=0}^{n}\binom{n}{i}x^{i}=(1+x)^{n}$

根据费马小定理有：
$(1+x)^{p}\equiv 1+x\,\,(mod\,\,p)$

根据上式可以推出：
$(1+x)^{n}\equiv (1+x)^{\left\lfloor\frac{n}{p}\right\rfloor p}(1+x)^{n\,\,mod\,\,p}\equiv (1+x)^{\left\lfloor\frac{n}{p}\right\rfloor}(1+x)^{n\,\,mod\,\,p}\,\,(mod\,\,p)$

再次展开可以得到 ：
$\sum_{i=0}^{n}\binom{n}{i}x^{i}\equiv \sum_{i=0}^{\left\lfloor\frac{n}{p}\right\rfloor}\binom{\left\lfloor\frac{n}{p}\right\rfloor}{i}x^{i}\sum_{i=0}^{n\,\,mod\,\,p}\binom{n\,\,mod\,\,p}{i}x^{i}\equiv \sum_{i=0}^{\left\lfloor\frac{n}{p}\right\rfloor}\binom{\left\lfloor\frac{n}{p}\right\rfloor}{i}x^{ip}\sum_{i=0}^{n\,\,mod\,\,p}\binom{n\,\,mod\,\,p}{i}x^{i}\,\,(mod\,\,p)$

显然 $x^{m}$的系数与 $x^{\left\lfloor\frac{m}{p}\right\rfloor}$和 $x^{m\,\,mod\,\,p}$的系数之积同余.
证毕.

那么在 $p$为素数的时候，我们可以先在 $O(p)$的时间复杂度内预处理出阶乘与阶乘逆，之后就可以在 $O(\log n)$的时间复杂度内回答 $\binom{n}{m}\,\,mod\,\,p$了.

代码如下：

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

int inv[N+9],fac[N+9],ifac[N+9];

void Get_inv(int p=mod){
  inv[1]=1;
  fac[0]=fac[1]=1;
  ifac[0]=ifac[1]=1;
  for (int i=2;i<p;++i){
    inv[i]=mul(p-p/i,inv[p%i],p);
    fac[i]=mul(fac[i-1],i,p);
    ifac[i]=mul(ifac[i-1],inv[i],p);
  }
}

int Get_c(int n,int m,int p=mod){return n<m?0:mul(fac[n],mul(ifac[m],ifac[n-m],p),p);}

int Lucas(int n,int m,int p=mod){
  if (n<m) return 0;
  int res=1;
  for (;n&&m;n/=p,m/=p) smul(res,Get_c(n%p,m%p,p),p);
  return res;
}

但是 $p$不为素数时该怎么办呢？

显然，把 $p$唯一分解后 $p=\prod_{i=0}^{k}p_i^{c_i}$，若 $c_i=1$，直接对于每个素因子 $p_i$求 $\binom{n}{m}\,\,mod\,\,p_i$，最后CRT合并即可.

但是 $c_i$不为 $1$，即模数为素数幂 $p_i^{c_i}$的情况呢？

显然有 $\binom{n}{m}=\frac{n!}{m!(n-m)!}$，我们考虑分别计算三个阶乘后通过逆元求解.

但是，逆元只有在模数与需要求逆的数互质时才能求，所以对于阶乘中的数，我们需要分两部分来考虑，一部分是 $p_i$的倍数，另一部分不是 $p_i$的倍数.

显然对于不是 $p_i$倍数的数，我们注意到 $a\equiv a+p_i^{c_i}\,\,(mod\,\,p_i^{c_i})$.此时设 $f(n)$表示 $[1,n]$上的不是 $p_i$倍数的整数乘积，则有：
$f(n)\equiv f(p_i^{c_i})^{\left\lfloor\frac{n}{p_i^{c_i}}\right\rfloor}f(n\,\,mod\,\,p_i^{c_i})\,\,(mod\,\,p_i^{c_i})$

这个式子可以 $O(p^{c_i})$求解.

那么对于 $p_i$的倍数呢？观察一下它们的形式为：
$p_i,2p_i,3p_i,\cdots$

显然我们可以把 $p_i$先提出来，然后剩下的数变为：
$1,2,3,\cdots$

突然发现这个东西等价于求 $\left\lfloor\frac{n}{p}\right\rfloor !$，就是原来的问题，可以递归计算， $p_i$外的数的贡献解决.

然后对于 $p_i$，很容易计算出 $p_i$的数量，从而避免求逆，计算 $p_i$贡献的问题就解决了.

时间复杂度 $O(\sqrt{p}+\sum p_i^{c_i}\log n)$，可以粗略的估计为 $O(p\log p)$.

代码如下：

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}
int Power(int a,int k,int p=mod){int res=1;for (;k;k>>=1,smul(a,a,p)) if (k&1) smul(res,a,p);return res;}

int Ex_gcd(int a,int b,int &x,int &y){
  if (!b) {x=1;y=0;return a;}
  int g=Ex_gcd(b,a%b,y,x);
  y-=a/b*x;
  return g;
}

int Get_inv(int a,int p=mod){int res,y,g=Ex_gcd(a,p,res,y);return g^1?-1:(res%=p)<0?res+p:res;}

int d[C+9],c[C+9],cd;

void Get_d(int n){
  int now=n;
  for (int i=2;i*i<=n;++i)
    if (now%i==0)
      for (d[++cd]=i;now%i==0;now/=i) ++c[cd];
  if (now>1) d[++cd]=now,c[cd]=1;
}

int Get_fact(int n,int p,int pi){
  if (!n) return 1;
  int res=1,t=n%p;
  for (int i=1;i<p;++i)
    if (i%pi) smul(res,i,p);
  res=Power(res,n/p,p); 
  for (int i=1;i<=t;++i)
    if (i%pi) smul(res,i,p);
  return mul(res,Get_fact(n/pi,p,pi),p);
}

int Get_c(int n,int m,int p,int pi){
  if (n<m) return 0;
  int res=mul(Get_fact(n,p,pi),Get_inv(mul(Get_fact(m,p,pi),Get_fact(n-m,p,pi),p),p),p),cnt=0;
  for (int i=n/pi;i;i/=pi) cnt+=i;
  for (int i=m/pi;i;i/=pi) cnt-=i;
  for (int i=(n-m)/pi;i;i/=pi) cnt-=i;
  return mul(res,Power(pi,cnt,p),p);
}

int a[C+9],mo[C+9];

int CRT(){
  int res=a[1],mod=mo[1];
  for (int i=2;i<=cd;++i){
  	int x,y,c=sub(a[i],res%mo[i],mo[i]),g=Ex_gcd(mod,mo[i],x,y);
  	if (c%g) return -1;
  	int t=mo[i]/g;
	x=mul((x%=t)<0?x+t:x,c/g,t)*mod;
  	mod*=mo[i]/g;sadd(res,x,mod);
  }
  return res;
}

int Lucas(int n,int m,int p=mod){
  if (n<m) return 0;
  Get_d(p);
  for (int i=1;i<=cd;++i){
  	mo[i]=1;
    for (int j=1;j<=c[i];++j) mo[i]*=d[i];
    a[i]=Get_c(n,m,mo[i],d[i]);
  }
  return CRT();
}

十一.高次同余方程引入.

高次同余方程：次数不为 $1$的同余方程，在这里主要指以下两类同余方程：
$a^{x}\equiv c\,\,(mod\,\,n)\\ x^{a}\equiv c\,\,(mod\,\,n)$

其中第一类方程对应了在模意义下取对数，即求 $\log_{a}c \,\,mod\,\,n$，这个问题对应了离散对数；第二类方程对应了在模意义下开高次根，即求 $\sqrt[a]{c}\,\,mod\,\,n$，这个问题对应了高次剩余.

接下来将会详细讨论这两块内容.


十二.离散对数问题与BSGS算法.

离散对数问题：离散对数问题指的是求解第一类高次同余方程，即：
$a^{x}\equiv c\,\,(mod\,\,n)$

接下来我们讲解如何求解.

把 $x$写成 $x=ki-j$的形式，得到：
$a^{ki-j}\equiv c\,\,(mod\,\,n)$

先假设有 $\gcd(n,a)=1$，则根据上面定理2的推论，此时有：
$a^{ki}\equiv ca^{j}\,\,(mod\,\,n)\Rightarrow a^{ki-j}\equiv c\,\,(mod\,\,n)$

这个时候我们就可以把问题转化为第一个式子了.而对于第一个问题，先把所有 $ca^{j}\,\,mod\,\,n$插入一个容器中，然后枚举 $i$，找到在容器中第一个满足 $a^{ki}\,\,mod\,\,n$ $i$，并得到对应的 $j$，那么答案就是 $ki-j$.

显然取 $t=\sqrt{n}$最优.

若用map实现这个容器时间复杂度为 $O(\sqrt{n}\log n)$，用hash实现为 $O(\sqrt{n})$.

代码如下：

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

map<int,int>mp;

int BSGS(int a,int c,int p=mod){
  if (c==1) return 0;
  int siz=sqrt(p)+1,pw=1;
  for (int i=0;i<siz;++i) mp[mul(pw,c,p)]=i,smul(pw,a,p);
  a=pw;pw=1;
  for (int i=1;i<=siz;++i){
  	smul(pw,a,p);
  	if (mp.find(pw)==mp.end()) continue;
	return i*siz-mp[pw];
  }
  return -1;
}

然而在 $\gcd(n,a)\neq 1$的时候，在模意义下的乘法不满足消去律了，这个时候就不能套上面的BSGS算法了，怎么办？

考虑把式子转化成 $\gcd(n,a)=1$的形式.

首先排除 $a=0$和 $x=0$的情况，排除之后我们有 $a\in [1,n),x>0$.

此时必然有 $a|a^{x}$，可以把 $a^x$写成 $a^x=ax'$的形式，发现一个同余方程，根据裴蜀定理有解时必然有 $\gcd(n,a)|c$.

然后我们考虑有解时，设 $g=\gcd(n,a)$，根据定理2有：
$\frac{a}{g}a^{x-1}\equiv \frac{c}{g}\,\,\left(mod\,\,\frac{n}{g}\right)\Rightarrow a^{x}\equiv c\,\,(mod\,\,n)$

这样我们就消掉了一部分公因数，但只消一次是不够的，应该一直消到 $a$与模数的gcd为 $1$为止.

时间复杂度仍为 $O(\sqrt{n}\log n)$或 $O(\sqrt{n})$.

代码如下：

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

map<int,int>mp;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int BSGS(int a,int c,int p=mod){
  if (!a) return !c?1:-1;
  if (c==1) return 0;
  int res=0,t=1;
  for (int g=gcd(a,p);g^1;g=gcd(a,p)){
    if (c%g) return -1;
    c/=g;p/=g;
	smul(t,a/g,p);++res;
	if (t==c) return res;
  }
  int siz=sqrt(p)+1,pw=1;
  for (int i=0;i<siz;++i) mp[mul(pw,c,p)]=i,smul(pw,a,p);
  a=pw;pw=t;
  for (int i=1;i<=siz;++i){
  	smul(pw,a,p);
  	if (mp.find(pw)==mp.end()) continue;
	return res+i*siz-mp[pw];
  }
  return -1;
}

十三.阶相关.

阶：最小的满足 $a^{x}\equiv 1\,\,(mod\,\,n)$的正整数 $x$被称为 $a$在模 $n$意义下的阶，记为 $\delta_{n}a$.

阶的性质1：存在 $\delta_{n}a$的充分必要条件为 $\gcd(n,a)=1$，且存在时必然有 $\delta_{n}a|\phi(n)$.

证明：
第一部分： $\gcd(n,a)=1\Rightarrow \exists\delta_{n}a$.
可以用欧拉定理证明.
第二部分： $\exists\delta_{n}a\Rightarrow \gcd(n,a)=1$.
原命题等价于证明存在 $k$满足 $a^{k}\equiv 1\,\,(mod\,\,n)$.
由于 $k$为正整数，所以 $a|a^{k}$，设 $a^{k}=ax$，那么有：
$a^{k}\equiv 1\,\,(mod\,\,n)\Leftrightarrow ax-ny=1$

根据裴蜀定理，有解的条件为 $\gcd(n,a)=1$.
第三部分： $\delta_{n}a|\phi(n)$.
设 $\phi(n)=k\delta_{n}a+r$，其中 $0<r<\delta_{n}a$，那么有：
$a^{r}\equiv a^{k\delta_{n}a+r}\equiv 1\,\,(mod\,\,n)$

与阶的定义矛盾，原命题得证.
证毕.

阶的性质2： $a^x\equiv 1\,\,(mod\,\,n)\Rightarrow\delta_{n}a|x$.

证明与阶的性质1第三部分类似.

阶的性质3：若 $\gcd(n,a)=1$，则 $\{a^{i}\,\,mod\,\,n|0\leq i< \delta_{n}a\}\subseteq n$的简化剩余系.

证明：
设 $S$为 $n$的简化剩余系且 $a\in S$，那么 $a^{i}\,\,mod\,\,n\in S$，问题转化为证明 $i\neq j\Rightarrow a^{i}\not\equiv a^{j}\,\,(mod\,\,n)$，其中 $i,j\in [1,n)$且为整数.
不妨设 $i>j$，此时假设 $a^{i}\equiv a^{j}\,\,(mod\,\,n)$，根据定理2有：
$\gcd(n,a)=1\wedge a^{i}\equiv a^{j}\,\,(mod\,\,n)\Rightarrow a^{i-j}\equiv 1\,\,(mod\,\,n)$

显然此时必须有 $i=j$，否则 $\delta_{n}a$就应该为 $i-j$了.
证毕.

阶的性质4：
$\delta_{n}(a^{k})=\frac{\delta_{n}a}{\gcd(\delta_{n}a,k)}$

从群论的角度很容易证明.

现在我们来学习一下如何求解阶.

首先根据阶的性质1，我们只需要能在 $\gcd(n,a)=1$的时候求 $\delta_{n}a$就好了，并且 $\delta_{n}a|\phi(n)$.

那么我们只需要枚举一下 $\phi(n)$的约数并用快速幂判定即可.

时间复杂度 $O(\sqrt{n}+n^{\frac{1}{3}}\log n)$.

代码如下：

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}
int Power(int a,int k,int p=mod){int res=1;for (;k;k>>=1,smul(a,a,p)) if (k&1) smul(res,a,p);return res;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int Get_phi(int n){
  int res=n,now=n;
  for (int i=2;i*i<=n;++i)
    if (now%i==0)
      for (res=res/i*(i-1);now%i==0;now/=i);
  if (now>1) res=res/now*(now-1);
  return res;
}

int Get_delta(int a,int p=mod){
  if (gcd(a,p)^1) return -1;
  int phi=Get_phi(p),res=phi;
  for (int i=1;i*i<=phi;++i)
    if (phi%i==0){
      if (Power(a,i,p)==1) res=min(res,i);
	  if (i*i^phi&&Power(a,phi/i,p)==1) res=min(res,phi/i); 
    }
  return res;
}

十四.原根相关.

原根：定义 $g$为 $n$的原根，当且仅当 $\delta_{n}g=\phi(n)$.

原根的性质1：若 $g$为 $n$的原根，则 $\{g^{i}\,\,mod\,\,n|0\leq i<\phi(n)\}$是 $n$的简化剩余系，并且 $g^{i}\,\,mod\,\,n$两两不同.

根据阶的性质3即可证明.

原根的性质2：若 $g$为 $n$的原根，则 $g^{k}\,\,mod\,\,n$是 $n$的原根当且仅当 $\gcd(\phi(n),i)=1$.

根据阶的性质4即可证明.

原根的性质3：若一个数 $n$存在原根，则它的原根的数量为 $\phi(\phi(n))$.

证明：
若 $n$存在一个原根 $g$，则 $\{g^{i}\,\,mod\,\,n|0\leq i<\phi(n)\}$都满足 $g^{i\phi(n)}\equiv 1\,\,(mod\,\,n)$.
根据原根的性质2， $g^{i}\,\,mod\,\,n$是 $n$的原根需要满足 $\gcd(\phi(n),i)=1$，那么所有满足条件的数的数量为：
$\sum_{i=0}^{\phi(n)-1}[\gcd(\phi(n),i)=1]=\phi(\phi(n))$

证毕.

原根的存在性：设 $p$为任意奇素数，则只有 $2,4,p^{k},2p^{k}$存在原根，其中 $k$是某个正整数.

接下来我们来求原根.不过在这之前，我们需要先引入一个性质.

原根的性质4：设唯一分解 $n=\prod_{i=1}^{k}p_i^{c_i}$，则 $g$为 $n$的原根当且仅当 $\gcd(n,g)=1$且对于任意 $i$满足 $g^{\frac{n}{p_i}}\not\equiv 1\,\,(mod\,\,n)$.

很显然不证明了.

根据原根的性质4，不难写出一个时间复杂度为 $O(\sqrt{n}+g\log^2 n)$求原根算法，其中 $g$为最小原根.

貌似这已经是目前最快的求解原根算法了，一般 $g$都挺小的所以这个算法并没有非常慢.

代码如下：

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}
int Power(int a,int k,int p=mod){int res=1;for (;k;k>>=1,smul(a,a,p)) if (k&1) smul(res,a,p);return res;}

int Get_phi(int n){
  int res=n,now=n;
  for (int i=2;i*i<=n;++i)
    if (now%i==0)
      for (res=res/i*(i-1);now%i==0;now/=i);
  if (now>1) res=res/now*(now-1);
  return res;
}

int d[C+9],c[C+9],cd;

void Get_d(int n){
  cd=0;
  int now=n;
  for (int i=2;i*i<=n;++i)
    if (now%i==0)
      for (d[++cd]=i,c[cd]=0;now%i==0;now/=i) ++c[cd];
  if (now>1) d[++cd]=now,c[cd]=1;
}

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int Get_proot(int p=mod){
  Get_d(p);
  if (cd==1&&d[1]==2&&c[1]>2||cd==2&&(d[1]^2||c[1]>1)||cd>2) return -1;
  int phi=Get_phi(p);
  Get_d(phi);
  for (int res=1;res<p;++res)
    if (gcd(p,res)==1){
  	  int flag=1;
      for (int i=1;i<=cd;++i)
        if (Power(res,phi/d[i],p)==1) {flag=0;break;}
      if (!flag) continue;
      return res;
    }
}

十五.关于原根存在性的证明.

咕.


十六.离散对数.

离散对数：设 $g$为 $n$的原根，则称 $g^{x}\equiv c\,\,(mod\,\,n)$的解 $x$为 $c$在模 $n$意义下以 $g$为底的离散对数，记为 $\mathrm{ind}_{g}c\,\,(mod\,\,n)$.

离散对数可以通过BSGS算法求解，并且根据原根的性质1，在 $\gcd(n,c)=1$时离散对数必然有解.

定理7：代数上的log运算与离散对数性质基本相同，即：
$\mathrm{ind}_{g} (ab)\equiv \mathrm{ind}_{g}a+\mathrm{ind}_{g}b\,\,(mod\,\,n)\\ \mathrm{ind}_{g} a^{n}\equiv n\,\mathrm{ind}_{g}a\,\,(mod\,\,n)$

离散对数还可以求解第二类高次同余方程，即：
$x^{a}\equiv c\,\,(mod\,\,n)$

对两边取离散对数，得到：
$a\mathrm{ind}_{g}x\equiv \mathrm{ind}_{g}c\,\,(mod\,\,n)\\ \mathrm{ind}_{g}x\equiv a^{-1}\mathrm{ind}_{g}c\,\,(mod\,\,n)\\ x\equiv g^{a^{-1}\mathrm{ind}_{g}c}\,\,(mod\,\,n)$

十七.二次剩余与Cipolla算法.

二次剩余方程：定义高次同余方程 $x^{2}\equiv c\,\,(mod\,\,n)$为二次剩余方程，其中 $n$为奇素数.

二次剩余：称 $c$为 $n$的二次剩余，当且仅当二次剩余方程 $x^{2}\equiv c\,\,(mod\,\,n)$存在解.

我们先来看一看如何判定一个数是否为二次剩余.

勒让德记号：定义勒让德记号 $\left(\frac{c}{n}\right)$为：
$\left(\frac{c}{n}\right)= \left\{\begin{matrix} 0&n|c\\ 1&\exists x\nmid n,x^2\equiv c\,\,(mod\,\,n)\\ -1&\nexists x\nmid n,x^2\equiv c\,\,(mod\,\,n) \end{matrix}\right.$

欧拉准则： $\left(\frac{c}{n}\right)=c^{\frac{n-1}{2}}\,\,mod\,\,n$.

证明：
对于 $n|c$的情况显然正确.
若存在 $x\nmid n$满足 $x^2\equiv c\,\,(mod\,\,n)$，由于 $n$为素数，根据费马小定理有：
$c^{\frac{n-1}{2}}\equiv x^{n-1}\equiv 1\,\,(mod\,\,n)$

否则根据费马小定理，一定有：
$c^{n-1}\equiv 1\,\,(mod\,\,n)$

根据二次探测定理，此时有：
$c^{\frac{n-1}{2}}\equiv 1\,\,(mod\,\,n)\vee c^{\frac{n-1}{2}}\equiv -1\,\,(mod\,\,n)$

把 $c$写成一个 $n$的原根 $g$的幂的形式，即 $c\equiv g^{2k+1}\,\,(mod\,\,n)$，此时有：
$c^{\frac{n-1}{2}}\equiv g^{k(n-1)+\frac{n-1}{2}}\equiv g^{\frac{n-1}{2}}\,\,(mod\,\,n)$

根据原根的定义，能够使得 $g^{x}\equiv 1\,\,(mod\,\,n)$的 $x$必然不小于 $\phi(n)=n-1$，所以必然有：
$c^{\frac{n-1}{2}}\equiv -1\,\,(mod\,\,n)$

证毕.

有了欧拉准则，我们就可以在 $O(\log n)$的时间内判定一个数是否是模 $n$意义下的二次剩余了.

欧拉准则的推论：
$\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)\equiv \left(\frac{ab}{n}\right)$

接下来我们开始求二次剩余方程的一个解.

定理8：设 $\omega=(a^{2}-c)\,\,mod\,\,n$，其中 $a$是一个 $[1,n)$上的整数，若有 $\left(\frac{\omega}{n}\right)=-1$，则 $(a+\sqrt{\omega})^{\frac{n+1}{2}}$是 $x^{2}\equiv c\,\,(mod\,\,n)$的一个整数解.

证明：
先来证明一下 $(a+\sqrt{\omega})^{\frac{n+1}{2}}$是一个解，即 $(a+\sqrt{\omega})^{n+1}\equiv c\,\,(mod\,\,n)$.

考虑将 $(a+\sqrt{\omega})^{n}$二项式展开得到：
$(a+\sqrt{\omega})^{n}=\sum_{i=0}^{n}\binom{n}{i}a^{n-i}\omega^{\frac{i}{2}}$

根据定理6有：
$(a+\sqrt{\omega})^{n}\equiv a^{n}+\omega^{\frac{n}{2}}\,\,(mod\,\,n)$

根据费马小定理与欧拉准则有：
$(a+\sqrt{\omega})^{n}\equiv a-\sqrt{\omega}\,\,(mod\,\,n)$

所以最后有：
$(a+\sqrt{\omega})^{n+1}\equiv (a+\sqrt{\omega})(a-\sqrt{\omega})\equiv a^{2}-\omega\equiv c\,\,(mod\,\,n)$

然后我们来证明一下 $(a+\sqrt{\omega})^{\frac{n+1}{2}}$是个整数.

假设 $(a+\sqrt{\omega})^{\frac{n+1}{2}}\equiv xa+y\sqrt{\omega}\,\,(mod\,\,n)$，那么此时有：
$(xa+y\sqrt{\omega})^{2}\equiv x^{2}a^{2}+2xya\sqrt{\omega}+y^{2}\omega\equiv c\,\,(mod\,\,n)$

此时必然有 $x=0$

转载：https://blog.csdn.net/hzk_cpp/article/details/86773602