浅谈二次剩余

二次剩余是数论基本概念之一，它是初等数论中非常重要的结果。
什么是二次剩余呢？简单来说就是如果存在一个整数$x$，使得x2≡n(modp)x^2≡n(mod\ p)x2≡n(mod p)，那么则称$n$是模$p$的二次剩余。
有一种很巧妙的办法，可以得出一个数是否是模$p$的二次剩余。这个办法是勒让德符号(np)(\frac{n}{p})(pn​)。

如果$n$是模$p$的二次剩余，那么(np)=1(\frac{n}{p})=1(pn​)=1；
如果$n$不是模$p$的二次剩余，那么(np)=−1(\frac{n}{p})=-1(pn​)=−1；
如果$p|n$，则(np)=0(\frac{n}{p})=0(pn​)=0

这里有一个结论：(np)=np−12(\frac{n}{p})=n^{\frac{p-1}{2}}(pn​)=n2p−1​ （前提是$p$是奇质数）

证明：（不看也无所谓）
①如果$n$是模$p$的二次剩余，那么n\sqrt nn​与$p$互质，那么根据费马小定理(n)p−1≡1(modp)(\sqrt n)^{p-1}≡1(mod\ p)(n​)p−1≡1(mod p)。
②如果$n$不是模$p$的二次剩余，那么因为$p$是奇质数，所以根据扩欧可知对于$i\in [1,p-1]$，都有一个$j\in [1,p-1]$使其满足$ij\equiv n(modp)$。所以我们可以把$1,2\dots \dots p-1$分成p−12\frac{p-1}{2}2p−1​对，每对的乘积在模$p$下都是$n$，那么(p−1)!≡np−12(modp)(p-1)!≡n^{\frac{p-1}{2}}(mod\ p)(p−1)!≡n2p−1​(mod p)，根据威尔逊定理有$(p-1)!\equiv -1(modp)$，所以np−12≡−1(modp)n^{\frac{p-1}{2}}≡-1(mod\ p)n2p−1​≡−1(mod p)
③如果$p|n$，那么显然np−12≡0(modp)n^{\frac{p-1}{2}}≡0(mod\ p)n2p−1​≡0(mod p)

定理：对于方程x2≡n(modp)x^2≡n(mod\ p)x2≡n(mod p)，有p−12\frac{p-1}{2}2p−1​个不同的$n$,使得该方程有解。

证明：若有两个数$u$和$v$均满足它们的平方在$p$时同余，那么必然有$p|(u+v)(u-v)$。由于$p$不可能整除$u-v$，那么可以得出$p$整除$u+v$。这个结论反过来也是成立的，因此共有p−12\frac{p-1}{2}2p−1​种不同的平方。且每一个$p$的二次剩余恰好有两个解。

那么怎么求一个二次剩余呢？我们可以按照下面的方法:

在$[0,p-1]$随机挑选一个数，称其为$a$，定义w=a2−nw=a^2-nw=a2−n，若(wp)=−1(\frac{w}{p})=-1(pw​)=−1，那么(a+w)p+12(a+\sqrt w)^{\frac{p+1}{2}}(a+w​)2p+1​就是一组二次剩余。

证明：(a+w)p=∑i=0p(Cpiap−i)(Cpp−i(w)i)(a+\sqrt w)^{p}=\sum_{i=0}^{p}(C_{p}^{i}a^{p-i})(C_{p}^{p-i}(\sqrt w)^{i})(a+w​)p=∑i=0p​(Cpi​ap−i)(Cpp−i​(w​)i)，由于$p$是质数，所以除了Cp0C^{0}_{p}Cp0​和CppC_{p}^{p}Cpp​为$1$外，所有的Cpi(i∈[1,p−1])C_{p}^{i}(i∈[1,p-1])Cpi​(i∈[1,p−1])模$p$等于$0$,所以(a+w)p≡ap+wp(modp)(a+\sqrt w)^{p}≡a^p+\sqrt w^p\ (mod\ p)(a+w​)p≡ap+w​p (mod p)。
由费马小定理可得ap≡a(modp)a^p≡a(mod\ p)ap≡a(mod p),又因为(wp)=−1(\frac{w}{p})=-1(pw​)=−1即wp−12=−1w^{\frac{p-1}{2}}=-1w2p−1​=−1,所以wp=−w\sqrt w^{p}=-\sqrt ww​p=−w​
所以(a+w)p≡ap+wp(modp)≡a−w(modp)(a+\sqrt w)^{p}≡a^p+\sqrt w^p\ (mod\ p)≡a-\sqrt w(mod\ p)(a+w​)p≡ap+w​p (mod p)≡a−w​(mod p)
所以(a+w)p+1≡(a+w)p(a+w)≡(a−w)(a+w)≡a2−w≡n(a+\sqrt w)^{p+1}≡(a+\sqrt w)^{p}(a+\sqrt w)≡(a-\sqrt w)(a+\sqrt w)≡a^2-w≡n(a+w​)p+1≡(a+w​)p(a+w​)≡(a−w​)(a+w​)≡a2−w≡n

有了最后一个定理，我们就可以通过随机选择a的值来找到一个满足条件的解。可以证明找到正解所需的次数的期望只有2（然而我并不是特别会证）。所以随机取a的值可以很快地找到一个解。

部分代码：

struct field{int x,y;field(int a=0,int b=0){x=a;y=b;}
};
field operator*(field a,field b){return field(a.x*b.x%p+a.y*b.y%p*w%p,a.x*b.y%p+a.y*b.x%p);}int ran(){static int seed=23333;return seed=((((((ll)seed^20030927)%p+330802)%p*9410)%p-19750115+p)%p^730903)%p;
}int pows(int a,int b){int base=1;while(b){if(b&1) base=base*a%p;a=a*a%p;b/=2;}return base;
}field powfield(field a,int b){field base=field(1,0);while(b){if(b&1) base=base*a;a=a*a;b/=2;}return base;
}int legander(int x){int a=pows(x,(p-1)/2);if(a+1==p) return -1;return a;
}int surplus(int x){int a;if(legander(x)==-1) return 0;while(1){a=ran()%p;w=((a*a-x)%p+p)%p;if(legander(w)==-1) break;}field b=field(a,1);b=powfield(b,(p+1)/2);return b.x;
}