二次剩余与高斯整数
C3H5ClO
2020-08-03 16:14:10
## 前置知识
1.基础的复数知识
2.基础的数论定理
3.一点点离散数学
4.一点点抽象代数（如果你只学算法，那么不用知道；如果想了解原理，可以去[维基百科](https://zh.wikipedia.org/)）
## 观前提醒
本文含有大量数论知识和证明，萌新完全阅读需要至少1小时。全文的证明都加了引用，对证明不感兴趣的读者可以选择性跳过。
# 二次剩余
对于正整数 $n$，奇质数$p\nmid n$，如果存在正整数 $x$ 使 $x^2\equiv n\pmod{p}$，则 $n$ 为模 $p$ 的二次剩余。
以下的$a\equiv b$均指$a\equiv b\pmod{p}$。
定义勒让德符号$(\frac{n}{p})=\begin{cases}
1 & n是p的二次剩余\\
-1 & n不是p的二次剩余\\
0 & p|n
\end{cases}$
定理1：$(\frac{n}{p})\equiv n^{\frac{p-1}{2}}$。
>证明：
>
>1.若$n$是模$p$的二次剩余，则根据费马小定理，$n^{\frac{p-1}{2}}=(\sqrt n)^{p-1}\equiv1$
>
>2.若$n$不是模$p$的二次剩余，则根据扩展欧几里得算法，对于$i\in[1,p-1]$都有唯一的$j\in[1,p-1],i\neq j$满足$ij\equiv n$。这样的数对一共有$\frac{p-1}{2}$个，因此$n^{\frac{p-1}{2}}\equiv (p-1)!$。根据威尔逊定理，$(p-1)!\equiv-1$，那么$n^{\frac{p-1}{2}}\equiv-1$。
>
>3.若$p|n$，显然有$p|n^{\frac{p-1}{2}},n^{\frac{p-1}{2}}\equiv0$。
定理2：$[1,p-1]$中有$\frac{p-1}{2}$个二次剩余。
>证明：设$x,y\in[1,p-1],x\neq y,x^2\equiv y^2$，则$(x+y)(x-y)\equiv0$。由于$0<|x-y|<p$，必定是$x+y\equiv 0$。这样的数对$(x,y)$共有$\frac{p-1}{2}$个，因此共有$\frac{p-1}{2}$个二次剩余。
根据上述证明，发现剩余系中的二次剩余与实数的平方根具有统一性：要么没有；要么有一个平方根(0)；要么有一对平方根，它们互为相反数。
## 求二次剩余的方法
问题：已知正整数$n,p$（$p$为奇质数），求所有数$x$，使$x^2\equiv n$。[题目链接](https://www.luogu.com.cn/problem/P5491)
在$[0,p-1]$中随机产生一个数$a$，令$w=a^2-n$，若$(\frac{w}{p})=-1$，$(a+\sqrt w)^{\frac{p+1}{2}}$是$x$的一个解。
>证明：首先，显然有$\binom{p}{x}\equiv 0,x\in[1,p-1]$。因此，$(a+\sqrt w)^p=\sum_{i=0}^p\binom{p}{i}a^i(\sqrt w)^{p-i}\equiv a^p+(\sqrt w)^p$。根据费马小定理，$a^p\equiv a$。根据定理1，$(\sqrt w)^p=\sqrt ww^{\frac{p-1}{2}}\equiv -\sqrt w$。因此，$(a+\sqrt w)^{p+1}\equiv(a+\sqrt w)(a-\sqrt w)=a^2-w=n$
这里就出现了一个问题：$w$明明是非二次剩余，怎么还会有$\sqrt w$呢？这里我们需要用到扩域的思想。定义$\mathbb{Z}_p[\sqrt w]=\{a+b\sqrt w\mid a,b\in\mathbb{Z}\cap[0,p)\}$，根据$(a_1+b_1\sqrt w)(a_2+b_2\sqrt w)\%p=(a_1a_2+b_1b_2w)\%p+(a_1b_2+b_1a_2)\%p\sqrt w$，在$\mathbb{Z}_p[\sqrt w]$上定义乘法，可以实现快速幂。
由于$[1,p-1]$中有一半是二次剩余，因此随机的期望次数为2。这种做法可以求出一个二次剩余的解，另一个解是它的相反数。
代码如下：
```cpp
inline int ksm(int a,int b)
{
int c=1;
while(b){if(b&1)c=1ll*c*a%MOD; a=1ll*a*a%MOD; b>>=1;}
return c;
}
inline int lrd(int x){return ksm(x,MOD>>1);}//勒让德符号
struct cplx
{
int x,y;
inline friend cplx operator *(cplx a,cplx b)
{
return {(1ll*a.x*b.x+1ll*a.y*b.y%MOD*w)%MOD,(1ll*a.x*b.y+1ll*a.y*b.x)%MOD};
}
inline friend cplx operator ^(cplx a,int b)
{
cplx c={1,0};
while(b){if(b&1)c=c*a; a=a*a; b>>=1;}
return c;
}
}a;
void solve()
{
scanf("%d%d",&n,&MOD); n%=MOD;
x=lrd(n);
if(x==MOD-1)printf("Hola!\n");
else if(!x)printf("0\n");
else
{
x=rand()%(MOD-1)+1; w=(1ll*x*x-n+MOD)%MOD;
while(lrd(w)<=1)x=rand()%MOD,w=(1ll*x*x-n+MOD)%MOD;
a={x,1}; a=a^(MOD+1>>1);
ans1=a.x; ans2=MOD-a.x; if(ans1>ans2)swap(ans1,ans2);
printf("%d %d\n",ans1,ans2);
}
}
```
# 高斯整数
高斯整数集合$\mathbb{Z}[i]=\{a+bi\mid a,b\in\mathbb{Z}\}$，其中$i^2=-1$
几何意义：复平面上的整点
高斯整数环是欧几里得整环，同样满足裴蜀定理、欧几里得引理、唯一分解定理等基础的数论定理。
高斯整数的可逆元群$U(\mathbb{Z}[i])=\{1,i,-1,-i\}$。
高斯整数$u=a+bi$的共轭复数$\bar u=a-bi$，可逆元的共轭复数是可逆元。
性质：$\overline{u+v}=\bar u+\bar v,\overline{uv}=\bar u\bar v,\overline{\frac{u}{v}}=\frac{\bar u}{\bar v}$，直接展开即可证明。
高斯整数的范数$\|a+bi\|=a^2+b^2$，可逆元的范数为1。
性质：$\|ab\|=\|a\|\|b\|$，直接展开即可证明。
## 费马平方和定理
定理表述：奇质数能表示为两个平方数之和的充分必要条件是该质数被4除余1。
接下来给出欧拉对这个定理的证明。
>将可以表示为两个整数平方和的数定义为平方分解数。
>
>定理1：平方分解数的积是平方分解数。
>
>>证明：$(a^2+b^2)(p^2+q^2)=(ap+bq)^2+(aq-bp)^2=(ap-bq)^2+(aq+bp)^2$
>
>定理2：平方分解数被素平方分解数整除的商是平方分解数。
>
>>证明：$(ap+bq)(ap-bq)=a^2p^2-b^2q^2=a^2(p^2+q^2)-q^2(a^2+b^2)$
>>
>>由于$p^2+q^2|a^2+b^2$，因此$p^2+q^2|(ap+bq)(ap-bq)$。$p^2+q^2$是质数，则它整除其中一个因子，不妨设$p^2+q^2|ap+bq$，另一种情况同理。$(p^2+q^2)^2|(a^2+b^2)(p^2+q^2)=(ap+bq)^2+(aq-bp)^2$，则
>>有$(p^2+q^2)^2|(aq-bp)^2$，那么$p^2+q^2|aq-bp$
>>
>>因此，$\frac{a^2+b^2}{p^2+q^2}=\frac{(a^2+b^2)(p^2+q^2)}{(p^2+q^2)^2}=(\frac{ap+bq}{p^2+q^2})^2+(\frac{aq-bp}{p^2+q^2})^2$
>
>定理3：平方分解数被非平方分解数整除的商必有一个非平方分解因子。
>
>>证明：设$a=x\prod p_i$，$a$是平方分解数，$x$是非平方分解数。如果$p_i$均是平方分解数，根据定理2，用$p_i$一个个去除$a$，所得结果$x$也是平方分解数，与假设矛盾。
>
>定理4：如果$a$和$b$互素，则$a^2+b^2$的所有因子都是平方分解数。
>
>>这一步的证明运用了无穷递降法。
>>
>>证明：假设$x|a^2+b^2,a=mx+c,b=nx+d(c,d\in[-\frac{x}{2},\frac{x}{2}])$
>>
>>$a^2+b^2=(m^2+n^2)x^2+2(mc+nd)x+c^2+d^2$，则$x|c^2+d^2$。设$gcd(c,d)=g$，由于$a\perp b$，则$g\perp x$。设$e=\frac{c}{g},f=\frac{d}{g}$，则$x|e^2+f^2,e\perp f$。设$xy=e^2+f^2$，则$xy\le c^2+d^2\le(\frac{x}{2})^2+(\frac{x}{2})^2=\frac{x^2}{2},y\le \frac{x}{2}$。若$x$不是平方分解数，根据定理3，$y$必有一个非平方分解因子，设为$x'$，则$x'\le y\le \frac{x}{2}<x$。因此，如果存在一个非平方分解数$x$是一对互素数平方和的因数，就必定存在一个非平方分解数$x'<x$是另一对互素数平方和的因数。而正整数$x$不可能无穷减小，因此假设不成立，$x$必为平方分解数。
>
>定理5a：形为$4n+1$的素数是平方分解数。
>
>>证明：设$p=4n+1$。根据费马小定理，$\forall x\in[1,4n],p|x^{4n}-1$，则$p|(x+1)^{4n}-x^{4n}$，那么有$p|(x+1)^{2n}+x^{2n}$或$p|(x+1)^{2n}-x^{2n}$。假设$\exists x,p|(x+1)^{2n}+x^{2n}$，根据定理4，$p$是平方分解数。否则，$\forall x\in[1,4n],p|(x+1)^{2n}-x^{2n}=\Delta x^{2n}$，根据整除可加减的性质，$x^{2n}$的任意阶差分都可以被$p$整除。因此，$p|\Delta^{2n} x^{2n}=(2n)!$，而$p|(2n)!$显然不成立。因此这种情况不存在，$p$必为平方分解数。
>
>定理5a证明了充分性，还需要证明必要性。
>
>定理5b：形为$4n+3$的数不是平方分解数。
>
>>证明：完全平方数模4只可能为0或1，因此不存在两个完全平方数之和模4为3。
>
>至此，我们证明了费马平方和定理：奇质数是平方分解数的充分必要条件是该质数形为$4n+1$。
## 高斯素数
高斯整数环的素元称为高斯素数。
1.高斯素数的共轭复数是高斯素数。
> 证明：设$p$是高斯素数，$\bar p=uv,u,v\not\in U(\mathbb{Z}[i])$，则$p=\overline{uv}=\bar u\bar v$，与$p$是高斯素数矛盾。
2.$a+bi$是高斯素数当且仅当下列条件之一成立：
(1)$a,b$一个为0，另一个的绝对值为$4k+3$型素数。根据费马平方和定理，显然成立。
(2)$a^2+b^2$为$4k+1$型素数或$2$
>证明：设$u=a+bi,u\bar u=p$。设$u=de,1<\|d\|,\|e\|<\|u\|$。那么$p=u\bar u=de\bar d\bar e=(d\bar d)(e\bar e)$，其中$d\bar d,e\bar e$均为大于1的正整数，与$p$是质数矛盾。
## 定义带余除法
$a,b,q,r$均为高斯整数，$a=qb+r$，那么必定存在一组$q,r$使得$\|r\|\le \frac{1}{2}\|b\|$。我们把$q$称为$a$整除$b$的商，把$r$称为$a$整除$b$的余数。
>证明：假设$\frac{a}{b}=x+yi,q=x'+y'i$，其中 $x'=\lfloor x+\frac{1}{2}\rfloor,y'=\lfloor y+\frac{1}{2}\rfloor$，则有$|x-x'|\le\frac{1}{2},|y-y'|\le\frac{1}{2}$。
>$r=a-qb=b((x-x')+(y-y')i)$
>$\|(x-x')+(y-y')i\|=(x-x')^2+(y-y')^2\le\frac{1}{2}$
>$\|r\|=\|b\|\|(x-x')+(y-y')i\|\le\frac{1}{2}\|b\|$
上述证明同时也是求商和余数的算法。
因此，可以对两个高斯整数进行辗转相除法，算出它们的最大公因数。代码如下：
```cpp
inline cplx operator /(cplx a,cplx b)
{
double x=b.x*b.x+b.y*b.y;
return {round((a.x*b.x+a.y*b.y)/x),round((a.y*b.x-a.x*b.y)/x)};
}
inline cplx operator %(cplx a,cplx b){return a-a/b*b;}
inline cplx gcd(cplx a,cplx b)
{
while(b.x||b.y)a=a%b,swap(a,b);
return a;
}
```
## 分解4n+1型素数
[题目链接](https://loj.ac/problem/6465)
设$p=4n+1,p=u\bar u$。首先注意到$k^2\equiv-1\Leftrightarrow p|(k+i)(k-i)$，则$u=gcd(p,k+i)$。由于$[1,p-1]$中一半的数是二次剩余，随机一个$t\in[1,p-1]$使$t^{\frac{p-1}{2}}\equiv -1$，则$k=t^{\frac{p-1}{4}}=t^n$。随机成功概率为$\frac{1}{2}$，期望随机次数为2。
## 构造二平方和
问题：求$x^2+y^2=n$的所有整数解。
考虑将$n$分解为共轭复数的积，令$u=x+yi$，则$n=u\bar u$
1.将$n$在$\mathbb{R}$内质因数分解。
2.对$4n+3$型质数，若次数为偶数，则在$u$与$\bar u$中均分，只有1种分法；若次数为奇数，则不存在方案使$u$与$\bar u$共轭，方程无解。
3.将$4n+1$型质数分解。假设$p=v\bar v$，则$p^k=v^k\bar v^k$，为了让$u$与$\bar u$共轭，分配方案需要使分配给$u$与$\bar u$的$v$与$\bar v$次数之和相等，即将$v^i\bar v^{k-i}$分配给$u$，剩下的分配给$\bar u$，共有$k+1$种分法。
4.将$2$分解为$(1+i)(1-i)$。由于$\frac{1+i}{1-i}=i$，无论分配方案如何，分配给$u$与$\bar u$的都是$(1+i)^k$乘以可逆元，方案本质相同，因此随便怎么分配都一样，只有1种分法。
5.最终还可以将$u$分别乘以4个可逆元，得到$(x,y)(-x,-y)(-y,x)(y,-x)$4个解。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int z,p[105],a[105],cnt,x,y,ans1,ans2[1000005][2];
struct cplx
{
ll x,y;
inline friend cplx operator -(cplx a,cplx b){return {a.x-b.x,a.y-b.y};}
inline friend cplx operator *(cplx a,cplx b){return {a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
inline friend cplx operator /(cplx a,cplx b)
{
double x=b.x*b.x+b.y*b.y;
return {round((a.x*b.x+a.y*b.y)/x),round((a.y*b.x-a.x*b.y)/x)};
}
inline friend cplx operator %(cplx a,cplx b){return a-a/b*b;}
inline friend cplx operator ^(cplx a,int b)
{
cplx c={1,0};
while(b){if(b&1)c=c*a; a=a*a; b>>=1;}
return c;
}
}u1[105],u2[105],u;
inline cplx gcd(cplx a,cplx b)
{
while(b.x||b.y)a=a%b,swap(a,b);
return a;
}
inline int rand_int(){return rand()<<15^rand();}
inline int ksm(int a,int b,int MOD=1e9)
{
int c=1;
while(b){if(b&1)c=1ll*c*a%MOD; a=1ll*a*a%MOD; b>>=1;}
return c;
}
inline void addans(int x,int y){ans2[++ans1][0]=x; ans2[ans1][1]=y;}
void dfs(int step,cplx s)
{
if(step>cnt)
{
addans(s.x,s.y);
addans(-s.x,-s.y);
addans(-s.y,s.x);
addans(s.y,-s.x);
return;
}
if(p[step]==2||(p[step]&3)==3)dfs(step+1,s*u1[step]);
else
{
cplx x=u2[step]^a[step];
for(int i=0;i<=a[step];i++)dfs(step+1,s*x),x=x/u2[step]*u1[step];
}
}
int main()
{
scanf("%d",&z);
for(int i=2;i*i<=z;i++)
if(z%i==0)
{
p[++cnt]=i;
while(z%i==0)z/=i,a[cnt]++;
}
if(z>1)p[++cnt]=z,a[cnt]=1;
for(int i=1;i<=cnt;i++)
if(p[i]==2)u1[i]=(cplx){1,1}^a[i];
else if((p[i]&3)==1)
{
while(1)
{
x=rand_int()%(p[i]-1)+1;
if(ksm(x,p[i]>>1,p[i])==p[i]-1)break;
}
x=ksm(x,p[i]>>2,p[i]); u={p[i],0};
u1[i]=gcd(u,{x,1});
u2[i]=u/u1[i];
}
else if(a[i]&1){printf("0\n"); return 0;}
else u1[i]={ksm(p[i],a[i]>>1),0};
dfs(1,{1,0});
printf("%d\n",ans1);
for(int i=1;i<=ans1;i++)printf("%d %d\n",ans2[i][0],ans2[i][1]);
}
```
## 求平方分解方案数
令$f(n)=\sum_{i=1}^{\lfloor\sqrt n\rfloor}\sum_{j=0}^{\lfloor\sqrt n\rfloor}[i^2+j^2=n]$
则方案数为$4f(n)$。
根据构造二平方和的方法，$n$中每个素因子的方案可以分开考虑，因此$f(n)$是积性函数。其中：
$f(p^k)=\begin{cases}
1 & p=2\\
k+1 & p=4n+1\\
[k\%2=0] & p=4n+3
\end{cases}$
可以使用改动过的min25筛快速求前缀和。具体见[题目链接](https://loj.ac/problem/3069)
# 完结撒花！
### 参考资料
[维基百科](https://zh.wikipedia.org/)
[浅谈二次剩余](https://blog.csdn.net/stevensonson/article/details/85845334)
[高斯整数](https://www.cnblogs.com/tempestT/p/12288833.html)