轉載注明來源：https://www.cnblogs.com/syc233/p/13741831.html

---

二次剩余，之前從數競同學那聽到過這個東西，覺得在OI中沒啥用。直到今天T1考了二次剩余，我才流下了沒有數理基礎的眼淚。

---

二次剩余，其實就是模意義下開根。

給定常數 (n) ，解同余方程：

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

當存在 (x) 滿足上式時，則 (n) 是模 (p) 的二次剩余。

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

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

基本結論

這里只討論 (p) 為奇素數的情況。

兩個二次剩余的乘積必然還是二次剩余

證明略。

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

證明略。

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

對于同余方程 (x^2equiv n) ，假設有兩個解 (x_1,x_2) ，則易證 (x_1+x_2equiv 0) ，即 (x_1) 和 (x_2) 互為相反數。

那么這樣的解的對數有 (p+1) 對，每一個 (n) 對應了兩個解，那么 (n) 有 (frac{p+1}{2}) 個。

歐拉準則

勒讓德符號 ({displaystyle ({frac {a}{p}})}) 定義：

[({frac {a}{p}})=
egin{cases}
0 & a equiv 0\
1 & a
ot equiv 0,exists xin (x^2 equiv a)\
-1 & forall xin (x^2
ot 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 imesfrac{p-1}{2}) ，則 (k) 是偶數， (n) 開根的結果是 (g^{frac{k}{2}}) 。

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

證畢。

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

先找出一個數 (a) ，滿足 (a^2-n) 為二次非剩余，隨機出一個數再判斷即可。

令 (i^2equiv a^2-n) ，類比復數的定義，將所有數定義成 (A+Bi) 的形式。

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

證明：

相當于證明 ((a+i)^{p+1} equiv n) 。

則有：

[egin{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}
]

由盧卡斯定理可得：

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

由費馬小定理有 (a^p equiv a) 。則：

[egin{aligned}
(a+i)(a^p+i^p)&equiv (a+i)(a+i imes (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)^2equiv n,B
ot =0) ，那么：

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

因為式子左邊虛部為 (0) ，所以式子右邊虛部也應該為 (0) ，則 (A=0) 。

得到 (i^2equiv n imes B^{-2}) ，因為右邊是兩個二次剩余，所以 (i^2) 也是二次剩余，與 (i) 的定義矛盾，所以 (B=0) 。

證畢。

---

P5491 【模板】二次剩余

( ext{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
",x1);
		else printf("%lld %lld
",min(x1,x2),max(x1,x2));
	}
	return 0;
}

總結

以上是生活随笔為你收集整理的总结「二次剩余」的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。