高斯整数

实部与虚部都为整数的复数称为高斯整数，即$a=(x+yi)\ (x,y\in Z)$

$a$的范为$N(a)=\mid a^2\mid =x^2+y^2$，可证明$N(\alpha\beta)=N(\alpha)N(\beta)$

若$\alpha,\beta$为高斯整数，那么他们加、减、乘后仍是高斯整数（但除不一定）

下文中的希腊字母均代表高斯整数

$\overline{\alpha}$为$\alpha$的共轭复数

若**$\alpha$整除$\beta$**，是指存在高斯整数$\gamma$使得$\beta=\alpha\gamma$，例:$(2-i)(5+3i)=13+i$，故$2-i\mid 13+i$

$1、-1、i、-i$为高斯整数的单位，能整除任意高斯整数

对于$\alpha$，他的全部相伴为$1\alpha、-1\alpha、i\alpha、-i\alpha$

高斯素数

定义：若非零高斯整数$\pi$不是单位，而且只能够被单位和他的相伴整除，则称之为高斯素数（即$\pi$恰有8个因子--4个单位和4个相伴）

定理1

若$p$为有理素数，且$N(\pi)=p$，则$\pi、\overline{\pi}$是高斯素数，$p$一定不是高斯素数

注：判断$\alpha$是否为高斯素数，即证明是否存在$\alpha=(a+bi)(c+di)\ a,b,c,d\in Z$且$(a+bi)$或$(c+di)$不为单位或$\alpha$的相伴

注2：存在$p$（如：2）为有理素数但不是高斯素数的复数（因为$2=(1+i)(1-i)$）

定理2

$\gamma$为非零高斯整数，且$\gamma$不是单位，则

1. $\gamma$能够表示成一些高斯素数的乘积
2. 该分解在某种意义上来说是唯一的

$\gamma=\pi_1\pi_2...\pi_s=\rho_1\rho_2...\rho_t$

其中$\pi_i、\rho_i$都是高斯素数，则有$s=t$，且重新编号后可使得$\pi_i$和$\rho_i$是相伴的

定理3（通过高斯整数证明）

若有理素数$p$型如$4k+1(k\in Z^+)$，则$p$可以表示为两个有理整数的平方和

与四平方和定理一起使用(?)

定理4

若$p$为有理素数，则可按如下法则分解

1. 若$p=2$，则$p=-i(1+i)^2=i(1-i)^2$
2. 若$p\equiv3\pmod{4}$，则$p=\pi$是高斯素数
3. 若$p\equiv1\pmod{4}$，则$p=\pi\pi'$，其中$\pi$和$\pi'$是不相伴的高斯素数，且$N(\pi)=N(\pi')=p$

定理5

对于正整数$n=2^mp_1^{e_1}p_2^{e_2}...p_s^{e_s}q_1^{f_1}q_2^{f_2}...q_t^{f_t}$

其中$p$为$4k+1$的素数，$q$为$4k+3$的素数，$e_i$为非负整数，$f_i$为非负偶数，那么有

$4(e_1+1)(e_2+1)...(e_s+1)$种方法将$n$表示为两个有理整数的平方和（此处次序不同或符号不同都被认为是不同的表示法）

引入：要求方程$a^2+b^2=n$的解的个数，只需要计算$n$分解成共轭高斯整数的乘积$n=(u+iv)(u-iv)$的方法数（$a^2+b^2=n\Leftrightarrow (a+bi)(a-bi)=n$）

据说看这个视频 (opens new window)有助于理解该定理

例题 洛谷2508/BZOJ1041 (opens new window)

题目：求一个给定的圆$\left(x^{2}+y^{2}=r^{2}\right)$的半径$r$ ，在圆周上有多少个点的坐标是整数。$(r\le2\cdot10^9)$

分析如下，令$v=r^2$，出现在$v$的分解中型如$4k+3$的素数一定成对出现，套用定理5的公式即可

#include <bits/stdc++.h>
#define ll long long

using namespace std;
ll r;

int main(){
    cin >> r;
    if(r == 0){cout<<1<<endl;return 0;}
    ll ans = 1;
    while(r % 2 == 0) r>>=1;
    for(ll i=3; i*i<=r; i+=2){
        ll cnt = 0;
        while(r%i==0) cnt++, r/=i;
        if(cnt > 0 && (i%4==1))
            ans *= (cnt*2 + 1);
    }
    if(r > 1 && (r%4==1)) ans *= 3;
    cout << (4 * ans) << endl;
}

恐怖如斯

参考

《初等数论及其应用》

高斯整数、高斯素数、费马平方和定理 (opens new window)