转载注明来源：https://www.cnblogs.com/syc233/p/13741831.html

二次剩余，之前从数竞同学那听到过这个东西，觉得在OI中没啥用。直到今天T1考了二次剩余，我才流下了没有数理基础的眼泪。

二次剩余，其实就是模意义下开根。

给定常数 \(n\) ，解同余方程：

\[x^2 \equiv n \ ({\rm{mod}} \ p) \]

当存在 \(x\) 满足上式时，则 \(n\) 是模 \(p\) 的二次剩余。

否则 \(n\) 是模 \(p\) 的二次非剩余。

为了方便，下面的同余式均省略 \(({\rm{mod}} \ p)\) 。

基本结论

这里只讨论 \(p\) 为奇素数的情况。

两个二次剩余的乘积必然还是二次剩余

证明略。

二次剩余的逆元还是二次剩余

证明略。

满足 “ \(n\) 是模 \(p\) 的二次剩余“ 的 \(n\) 有 \(\frac{p+1}{2}\) 个

对于同余方程 \(x^2\equiv n\) ，假设有两个解 \(x_1,x_2\) ，则易证 \(x_1+x_2\equiv 0\) ，即 \(x_1\) 和 \(x_2\) 互为相反数。

那么这样的解的对数有 \(p+1\) 对，每一个 \(n\) 对应了两个解，那么 \(n\) 有 \(\frac{p+1}{2}\) 个。

欧拉准则

勒让德符号 \({\displaystyle ({\frac {a}{p}})}\) 定义：

\[({\frac {a}{p}})= \begin{cases} 0 & a \equiv 0\\ 1 & a \not \equiv 0,\exists x\in \Z (x^2 \equiv a)\\ -1 & \forall x\in \Z(x^2\not \equiv a) \end{cases} \]

欧拉准则：

\[n^{\frac{p-1}{2}}\equiv (\frac{n}{p}) \]

那么若 \(n\) 是二次剩余，则 \(n^{\frac{p-1}{2}}=1\) 。

证明：

由费马小定理 \(n^{p-1}\equiv 1\) ，则 \((n^{\frac{p-1}{2}})^2 \equiv 1\) 。那么 \(n^{\frac{p-1}{2}}\) 是 \(1\) 模 \(p\) 意义下开根的结果，则 \(n^{\frac{p-1}{2}}=\pm 1\) 。

若 \(n^{\frac{p-1}{2}}=1\) ，则令 \(n=g^k\) ，其中 \(g\) 为 \(p\) 的原根。

则有 \((g^k)^{\frac{p-1}{2}}\equiv 1\) ，因为 \(g^{p-1}\equiv 1\) 且 \(g\) 是原根，那么有 \(p-1|k\times\frac{p-1}{2}\) ，则 \(k\) 是偶数， \(n\) 开根的结果是 \(g^{\frac{k}{2}}\) 。

所以 \(n^{\frac{p-1}{2}}=1\) 时，\(n\) 是二次剩余，否则 \(n\) 是二次非剩余。

证毕。

求解 \(x^2 \equiv n \ ({\rm{mod}} \ p)\)

先找出一个数 \(a\) ，满足 \(a^2-n\) 为二次非剩余，随机出一个数再判断即可。

令 \(i^2\equiv a^2-n\) ，类比复数的定义，将所有数定义成 \(A+Bi\) 的形式。

那么 \((a+i)^{\frac{p+1}{2}}\) 是原方程的一个解。

证明：

相当于证明 \((a+i)^{p+1} \equiv n\) 。

则有：

\[\begin{aligned} (a+i)^{p+1}&\equiv (a+i)^p(a+i) \equiv n\\ &\equiv (a+i)\sum_{k=0}^{p}{p \choose i}a^ki^{p-k} \end{aligned} \]

由卢卡斯定理可得：

\[\begin{aligned} (a+i)^{p+1}&\equiv (a+i)(a^p+i^p) \end{aligned} \]

由费马小定理有 \(a^p \equiv a\) 。则：

\[\begin{aligned} (a+i)(a^p+i^p)&\equiv (a+i)(a+i\times (i^2)^{\frac{p-1}{2}})\\ &\equiv (a+i)(a-i)\\ &\equiv a^2-i^2\\ &\equiv a^2-(a^2-n)\\ &\equiv n \end{aligned} \]

得证 \((a+i)^{p+1} \equiv n\) 。

证毕。

\((a+i)^{\frac{p+1}{2}}\) 中虚部一定为 \(0\) 。

证明：

假设存在 \((A+Bi)^2\equiv n,B\not =0\) ，那么：

\[\begin{aligned} (A+Bi)^2&\equiv A^2+2ABi+B^2i^2\equiv n\\ A^2+B^2i^2-n&\equiv -2ABi \end{aligned} \]

因为式子左边虚部为 \(0\) ，所以式子右边虚部也应该为 \(0\) ，则 \(A=0\) 。

得到 \(i^2\equiv n\times B^{-2}\) ，因为右边是两个二次剩余，所以 \(i^2\) 也是二次剩余，与 \(i\) 的定义矛盾，所以 \(B=0\) 。

证毕。

P5491 【模板】二次剩余

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;

template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

lxl n,p,w;

struct Complex
{
	lxl x,y;
	Complex(lxl x,lxl y):x(x),y(y){}
	Complex(){}
	inline Complex operator * (const Complex &T)const
	{
		return Complex((x*T.x%p+y*T.y%p*w%p)%p,(x*T.y%p+y*T.x%p)%p);
	}
};

inline lxl fmi(lxl a,lxl b)
{
	lxl res(1);
	a%=p;
	while(b>0)
	{
		if(b&1) (res*=a)%=p;
		(a*=a)%=p;
		b>>=1;
	}
	return res;
}

inline Complex cfmi(Complex a,lxl b)
{
	Complex res(1,0);
	while(b>0)
	{
		if(b&1) res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}

inline lxl Sqrt(lxl n,lxl p) // 在模 p 意义下开根
{
	n=(n%p+p)%p;
	if(!n) return 0;
	if(fmi(n,(p-1)>>1)!=1) return -1;
	lxl a;
	while(1)
	{
		a=rand()%p;
		w=(a*a%p-n+p)%p;
		if(fmi(w,(p-1)>>1)!=1) break;
	}
	return cfmi(Complex(a,1),(p+1)>>1).x;
}

int main()
{
	// freopen("P5491.in","r",stdin);
	int T;read(T);
	while(T--)
	{
		read(n),read(p);
		lxl x1=Sqrt(n,p),x2=(p-x1)%p;
		if(!~x1) puts("Hola!");
		else if(x1==x2) printf("%lld\n",x1);
		else printf("%lld %lld\n",min(x1,x2),max(x1,x2));
	}
	return 0;
}