二次剩余&二次同余式&二次互反律

二次剩余

P5491 【模板】二次剩余

可以理解为开根。

$$x^2\equiv n(\mod p)$$

注意：这里的 $p$ 是奇素数。

非 $0$ 数 $n$ 是二次剩余当且仅当 $x^2\equiv n$ 有解。

而如果 $x^2\equiv n$ 无解，那么就是非二次剩余。

我们现在假设有解，如果有多组解，设有其中两个不相等的解为 $x_0,x_1$，那么就有：

$$x_0^2\equiv x_1^2(\mod p)$$ $$(x_0-x_1)(x_0+x_1)\equiv 0(\mod p)$$

因为 $x_0\not= x_1$，所以 $(x_0+x_1)\equiv0(\mod p)$

也就是说 $x_0,x_1$ 互为相反数，那么任意两个解都互为相反数。就会发现，只有两个解，且互为相反数。

因为 $p$ 是奇数，所以模意义下的两个数不会相等。

简而言之：如果二次剩余有解，有且仅有两个解，且满足 $(x_0+x_1)\equiv0(\mod p)$。

那么一对相反数对应一个二次剩余，而且二次剩余两两不同。其中一半 $\frac{p-1}{2}$ 是二次剩余，剩下一半 $\frac{p-1}{2}$ 是非二次剩余。

欧拉准则

前置知识：

原根

$$a^r\equiv 1(\mod p)$$

如果 $a$ 是模 $p$ 的原根，$\varphi(p)\mid r$。

在阶的定义中，如果 $r=\varphi(p)$ 那么 $a$ 是模 $m$ 的一个原根。而如果 $a$ 是 $k$ 的 $n$ 次幂的话：$k^{nr}\equiv 1(\mod p)$，此时的 $r$ 仍然是阶，但是 $a$ 可以换成 $k^n$，由于 $r=\varphi(p)$，所以 $\varphi(p)\mid r$。

欧拉准则是用来快速判断一个数 $n$ 是否为二次剩余的。

如果 $n=0$，那么直接返回 $0$ 就行了。

如果 $n\not=0$。

先来看费马小定理：$n^{p-1}\equiv1(\mod p)$，题目中说明了 $p$ 是奇素数，所以 $p-1$ 是偶数。

那么就有 $n^{2(\frac{p-1}{2})}\equiv 1(\mod p)$。

$$n^{2(\frac{p-1}{2})}-1\equiv 0(\mod p)$$ $$(n^{\frac{p-1}{2}}+1)(n^{\frac{p-1}{2}}-1)\equiv0(\mod p)$$

当 $n^{\frac{p-1}{2}}\equiv1(\mod p)$ 时，假设 $g$ 是模 $p$ 意义下的原根，那么 $n=g^k$，现在有：$g^{k\frac{p-1}{2}}\equiv1(\mod p)$。

根据我们再前置知识中推出的 $\varphi(p)\mid r$，就有 $\varphi(p)\mid k\frac{p-1}{2}$，因为 $p$ 是素数，所以 $\varphi(p)=p-1$，得出 $p-1\mid k\frac{p-1}{2}$。

$$p-1\mid k\frac{p-1}{2}$$ $$p-1\mid \frac{k}{2}(p-1)$$

不难看出 $k$ 一定是偶数，是偶数就说明能开根，设 $x=g^{\frac{k}{2}}=\sqrt{n}$，所以 $n$ 是二次剩余（有解）。

当 $n^{\frac{p-1}{2}}\equiv -1(\mod p)$
时，是非二次剩余（无解，负数开方不是实数）。

• 勒让德符号

$$\big(\frac{n}{p}\big) =\begin{cases} 1(\text{ $n$ 是二次剩余})\\ -1(\text{ $n$ 是非二次剩余})\\ 0(\text{ $n=0$ }) \end{cases}$$

其中 $p$ 是奇素数，这是个积性函数。

Cipolla

现在找到一个 $a$ 满足 $a^2-n$ 是非二次剩余。由于非二次剩余和二次剩余的数量接近 $\frac{p}{2}$，如果随机找的话，期望是 $2$ 两次找到一个（代码用的是暴力方法寻找）。

现在我们新定义 $i^2\equiv a^2-n$，很显然不可避免地会出现 $i^2=-x_i$ 那么我们就要用复数（实部和虚部）来表示每个数。

$$i^2\equiv a^2-n\equiv n^{\frac{p-1}{2}}(\mod p)$$ $$a^2-i^2\equiv n(\mod p)$$ $$(a-i)(a+i)\equiv n(\mod p)$$

根据费马小定理：

$$a^{p-1}\equiv 1(\mod p)$$

所以：$a^p\equiv a(\mod p)$

又有：

$$i^p=i(i^2)^\frac{p-1}{2}=i\times -1=-i$$

那么：

$$(a^p+i^p)(a+i)\equiv n(\mod p)$$ $$\because(A+B)^p\equiv A^p+B^p(\mod p)$$

（其他项都会出现含 $p$ 的项，模后就没了。二项式定理）

$$\therefore (a+i)^{p+1}\equiv n(\mod p)$$ $$\therefore (a+i)^{\frac{p+1}{2}}\equiv \sqrt{n} (\mod p)$$

$(a+i)^{\frac{p+1}{2}}$ 就是其中的一个解，而它的相反数就是另一个解。

现在我们还要证明一下，结果一定不存在虚部。

假设我们的存在 $(A+Bi)^2\equiv n(\mod p)$，其中 $B$ 是虚部且 $B\not= 0$。

$$A^2+B^2i^2+2ABi\equiv n(\mod p)$$ $$A^2+B^2i^2-n\equiv-2ABi(\mod p)$$

左边没有虚部了（平方后是实数），所以右边的虚部为 $0$，$AB=0$。

因为 $B\not=0$，所以 $A=0$，那么 $B^2i^2\equiv n(\mod p)$。

$$i^2\equiv nB^{-2}(\mod p)$$

$B^2$ 是实数，逆元也是实数，$nB^{-2}$ 是实数。此时 $i^2$ 变成了二次剩余，矛盾。

所以 $B=0$。

代码

虽然证明很复杂，但是代码很好写，主要是套公式。

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<map> 
#include<unordered_map>
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar(); 
  }
  return k*f;
}
const int o_o=1e6+10;
long long k_m(long long a,long long b,long long m_d){//快速幂 
  long long r_s=1;
  while(b){
    if(b&1)r_s=(r_s*a)%m_d;
    a=(a*a)%m_d;
    b>>=1;
  }
  return r_s%m_d;
}
struct po{//复数 
  long long x;//实数部分 
  long long y;//虚数部分 
}p_p[o_o];
long long m_d,n;
long long i_2;//虚数单位的平方 
po c_h(po a,po b,long long m_d){//复数乘法 
  return {(a.x*b.x+a.y*b.y%m_d*i_2)%m_d,(a.x*b.y+a.y*b.x)%m_d};
}
long long p_k(po a,long long b,long long m_d){//复数快速幂 
  po r_s={1,0};
  while(b){
    if(b&1)r_s=c_h(r_s,a,m_d);
    a=c_h(a,a,m_d);
    b>>=1;
  }
  return (r_s.x%m_d+m_d)%m_d;
}
long long f_i(long long n,long long m_d){
  if(k_m(n,(m_d-1)>>1,m_d)==m_d-1)return -1;//不符合要求 
  int k_k=1;
  //枚举 a，使得 a 的平方减 n 是非二次剩余 
  //套结论公式 
  while(k_k<=m_d&&k_m(i_2=(1ll*k_k*k_k-n+m_d)%m_d,(m_d-1)>>1,m_d)==1)k_k++;
  
  //套结论公式 
  return p_k({k_k,1},m_d+1>>1,m_d);//找到答案，计算结果 
}
int main(){
  int t=r_r();
  while(t--){
    n=r_r(),m_d=r_r();
    if(!n){//如果 n 为 0 那么 x 只能等于 0  
      puts("0");
      continue;
    }
    long long x=f_i(n,m_d);//查找结果 
    if(x==-1)puts("Hola!");//无解 
    else{//有解（两解） 
      if(x>(m_d>>1))x=m_d-x;//注意输出顺序要递增 
      printf("%lld %lld\n",x,m_d-x);
    }
  }
  return 0;
}

一般二次同余式

$$ax^2+bx+c\equiv 0(\mod p)$$

其中 $a\not\equiv 0(\mod p)$

$p$ 可以分解成 $p_1^{a_1}p_2^{a_2}…p_k^{a_k}$，所以二次同余式等价于：

$$\begin{cases} ax^2+bx+c\equiv0(\mod p_1^{a_1})\\ ax^2+bx+c\equiv0(\mod p_2^{a_2})\\ \vdots\\ ax^2+bx+c\equiv0(\mod p_k^{a_k})\\ \end{cases}$$

我们先看第一个式子：

$$ax^2+bx+c\equiv0(\mod p_1^{a_1})$$

两边同时乘 $4a$：

$$4a^2x^2+4abx+4ac\equiv0(\mod p_1^{a_1})$$ $$(2ax+b)^2-b^2+4ac\equiv0(\mod p_1^{a_1})$$ $$(2ax+b)^2\equiv b^2-4ac(\mod p_1^{a_1})$$

$a,b,c$ 都是常数，设 $n=b^2-4ac,k=2ax+b$ 那么就有：

$$k^2\equiv n(\mod p_1^{a_1})$$

当 $p_1$ 是奇素数时，这就是二次剩余。

因为 $p_i$ 都是素数。所以只有 $p_i=2$ 的情况要单独讨论。

将所有的式子都处理后，用 中国剩余定理 处理就可以了。

二次互反律

这里直接放结论了，证明过程过于复杂。

上面介绍了勒让德符号，我们这里使用这种符号来表示二次互反律。

$$\big(\frac{n}{p}\big) =\begin{cases} 1(\text{ $n$ 是二次剩余})\\ -1(\text{ $n$ 是非二次剩余})\\ 0(\text{ $n=0$ }) \end{cases}$$

其中 $p$ 是奇素数，是个积性函数。

对于奇素数 $p,q$：

$$\big(\frac{p}{q}\big)\big(\frac{q}{p}\big)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$

还有两个辅助定理：

• $$\big(\frac{-1}{p}\big)=(-1)^{\frac{p-1}{2}}$$
• $$\big(\frac{2}{p}\big)=(-1)^{\frac{p^2-1}{8}}$$