二次剩余
定义
存在正整数 a a a a 2 ≡ n ( m o d p ) {a}^2\equiv n\pmod{p} a 2 ≡ n ( m o d p ) n n n p p p p p p
前提
对于一个存在的正整数 a a a n n n a p − 1 2 ≡ 1 ( m o d p ) {a}^{\frac{p-1}{2} }\equiv1\pmod{p} a 2 p − 1 ≡ 1 ( m o d p )
由费马小定理知对于任意的正整数 n n n n p − 1 ≡ 1 ( m o d p ) {n}^{p-1}\equiv 1\pmod{p} n p − 1 ≡ 1 ( m o d p ) a 2 ≡ n ( m o d p ) {a^2}\equiv n\pmod{p} a 2 ≡ n ( m o d p ) a ≡ n 1 2 ( m o d p ) a\equiv {n}^{\frac{1}{2} }\pmod{p} a ≡ n 2 1 ( m o d p ) a p − 1 2 ≡ 1 ( m o d p ) {a}^{\frac{p-1}{2} }\equiv1\pmod{p} a 2 p − 1 ≡ 1 ( m o d p )
如果一个正整数不是二次剩余，那么他就是非二次剩余。
解数
对于 a 2 ≡ n ( m o d p ) a^2\equiv n \pmod{p} a 2 ≡ n ( m o d p ) p p p
− p − 1 2 , − p − 1 2 + 1 , ⋯ , − 1 , 1 , ⋯ , p − 1 2 − 1 , p − 1 2 -\frac{p-1}{2},-\frac{p-1}{2}+1,\cdots,-1,1,\cdots ,\frac{p-1}{2}-1,\frac{p-1}{2} − 2 p − 1 , − 2 p − 1 + 1 , ⋯ , − 1 , 1 , ⋯ , 2 p − 1 − 1 , 2 p − 1
此时 n n n ( − p − 1 2 ) 2 , ( − p − 1 2 + 1 ) 2 , ⋯ , ( − 1 ) 2 , ( 1 ) 2 , ⋯ , ( p − 1 2 − 1 ) 2 , ( p − 1 2 ) 2 (-\frac{p-1}{2})^2,(-\frac{p-1}{2}+1)^2,\cdots,(-1)^2,(1)^2,\cdots,(\frac{p-1}{2}-1)^2,(\frac{p-1}{2})^2 ( − 2 p − 1 ) 2 , ( − 2 p − 1 + 1 ) 2 , ⋯ , ( − 1 ) 2 , ( 1 ) 2 , ⋯ , ( 2 p − 1 − 1 ) 2 , ( 2 p − 1 ) 2
而对于 ( − p − 1 2 ) 2 = ( p − 1 2 ) 2 (-\frac{p-1}{2})^2=(\frac{p-1}{2})^2 ( − 2 p − 1 ) 2 = ( 2 p − 1 ) 2 p − 1 2 \frac{p-1}{2} 2 p − 1 n n n p − 1 2 \frac{p-1}{2} 2 p − 1 p p p p − 1 2 \frac{p-1}{2} 2 p − 1 p − 1 2 \frac{p-1}{2} 2 p − 1
这就意味着只会有 p − 1 2 \frac{p-1}{2} 2 p − 1 a 2 ≡ n ( m o d p ) a^2\equiv n\pmod{p} a 2 ≡ n ( m o d p ) n n n a 1 ≡ − n , a 2 ≡ n ( m o d p ) a_1\equiv-n,a_2\equiv n\pmod{p} a 1 ≡ − n , a 2 ≡ n ( m o d p )
Euler 判别法
现在考虑如何判别 ω 2 {\omega}^2 ω 2 ( ω 2 ) p − 1 ≡ 1 ( m o d p ) {(\omega}^{2})^{p-1}\equiv1\pmod{p} ( ω 2 ) p − 1 ≡ 1 ( m o d p ) ( ω 2 ) p − 1 − 1 ≡ 0 ( m o d p ) {(\omega}^{2})^{p-1}-1\equiv0\pmod{p} ( ω 2 ) p − 1 − 1 ≡ 0 ( m o d p ) ( ω p − 1 − 1 ) ( ω p − 1 + 1 ) ≡ 1 ( m o d p ) ({\omega}^{p-1}-1)({\omega}^{p-1}+1)\equiv1\pmod{p} ( ω p − 1 − 1 ) ( ω p − 1 + 1 ) ≡ 1 ( m o d p ) ω \omega ω ω p − 1 ≡ 1 ( m o d p ) {\omega}^{p-1}\equiv1\pmod{p} ω p − 1 ≡ 1 ( m o d p ) ω \omega ω ω p − 1 ≡ − 1 ( m o d p ) {\omega}^{p-1}\equiv -1\pmod{p} ω p − 1 ≡ − 1 ( m o d p ) d d d d p − 1 2 ≡ − 1 ( m o d p ) d^{\frac{p-1}{2} }\equiv -1\pmod{p} d 2 p − 1 ≡ − 1 ( m o d p ) Euler \text{Euler} Euler
解法
参考了神仙 yyb 的博客 。
考虑构造一个复数 ω = a 2 − n \omega=\sqrt{a^2-n} ω = a 2 − n ω 2 {\omega}^2 ω 2 2 2 2 Euler \text{Euler} Euler ω 2 {\omega}^{2} ω 2
那么 n = a 2 − ω 2 = ( a − ω ) ( a + ω ) n=a^2-{\omega}^2=(a-\omega)(a+\omega) n = a 2 − ω 2 = ( a − ω ) ( a + ω ) a − ω , a + ω a-\omega,a+\omega a − ω , a + ω
对于 a − ω a-\omega a − ω ω p ≡ − ω ( m o d p ) {\omega}^{p}\equiv-\omega\pmod{p} ω p ≡ − ω ( m o d p ) a − ω ≡ a p + ω p ( m o d p ) a-\omega\equiv{a}^{p}+{\omega}^{p}\pmod{p} a − ω ≡ a p + ω p ( m o d p )
对于 a + ω {a+\omega} a + ω ( a + ω ) p ≡ a p + ω p ( m o d p ) (a+\omega)^p\equiv{a}^{p}+{\omega}^{p}\pmod{p} ( a + ω ) p ≡ a p + ω p ( m o d p ) p p p ( n 0 ) , ( n n ) \binom{n}{0},\binom{n}{n} ( 0 n ) , ( n n ) ( a + ω ) p + 1 ≡ ( a p + ω p ) ( a + ω ) ≡ ( a + ω ) ( a − ω ) = n ( m o d p ) (a+\omega)^{p+1}\equiv(a^p+{\omega}^{p})(a+\omega)\equiv(a+\omega)(a-\omega)=n\pmod{p} ( a + ω ) p + 1 ≡ ( a p + ω p ) ( a + ω ) ≡ ( a + ω ) ( a − ω ) = n ( m o d p )
那么对于 a 2 ≡ n ( m o d p ) {a}^{2}\equiv n\pmod{p} a 2 ≡ n ( m o d p ) ( a + ω ) p + 1 ≡ n ( m o d p ) (a+\omega)^{p+1}\equiv n\pmod{p} ( a + ω ) p + 1 ≡ n ( m o d p ) a ≡ ( a + ω ) p + 1 2 ( m o d p ) {a}\equiv(a+\omega)^{\frac{p+1}{2} }\pmod{p} a ≡ ( a + ω ) 2 p + 1 ( m o d p ) a ≡ ( a + ω ) p + 1 2 ≡ a p + 1 2 + ω p + 1 2 ≡ ω p + 1 2 ( m o d p ) a\equiv (a+\omega)^{\frac{p+1}{2} }\equiv a^{\frac{p+1}{2} }+{\omega}^{\frac{p+1}{2} }\equiv {\omega}^{\frac{p+1}{2} }\pmod{p} a ≡ ( a + ω ) 2 p + 1 ≡ a 2 p + 1 + ω 2 p + 1 ≡ ω 2 p + 1 ( m o d p ) ω p + 1 2 {\omega}^{\frac{p+1}{2} } ω 2 p + 1 n n n p p p
现在考虑证明 ω p ≡ − ω ( m o d p ) {\omega}^{p}\equiv-\omega\pmod{p} ω p ≡ − ω ( m o d p ) ω \omega ω ω p − 1 ≠ 1 ( m o d p ) {\omega}^{p-1}\ne 1\pmod{p} ω p − 1 = 1 ( m o d p ) ≠ \ne = ω 2 {\omega}^{2} ω 2 ( ω 2 ) p − 1 ≡ 1 ( m o d p ) ({\omega}^{2})^{p-1}\equiv1\pmod{p} ( ω 2 ) p − 1 ≡ 1 ( m o d p ) ω p − 1 ≡ − 1 ( m o d p ) {\omega}^{p-1}\equiv-1\pmod{p} ω p − 1 ≡ − 1 ( m o d p ) ω p ≡ − ω ( m o d p ) {\omega}^{p}\equiv-\omega\pmod{p} ω p ≡ − ω ( m o d p )
实现
注意复数运算法则。
模板题：洛谷-P5491 [模板]二次剩余
放一份代码：
#define int long long
while(t--)
{
scanf("%lld%lld",&n,&p);
if(n==0){puts("0");continue;}
if(qpow(n,p>>1)!=1){puts("Hola!");continue;}
k=rand()%(p-1)+1,w=Abs(k*k-n);//k表示复数的数值
while(qpow(w,p>>1)==1) k=rand()%(p-1)+1,w=Abs(k*k-n);//Euler判别法
int ans1=Cpow((Complex){k,1},(p>>1)+1).x,ans2=p-ans1;//复数快速幂
if(ans1>ans2) swap(ans1,ans2);
printf("%lld %lld\n",ans1,ans2);
}
