高斯整数与平方和问题

高斯整数


Definition 1.1
高斯整数是定义在复数域上的,实部和虚部均为整数的复数集,遵循复数运算法则
形式化的,我们把满足$z=a+bi,其中a,b\in Z$的复数$z$称为高斯整数(Guassian Integers)

Definition 1.2
定义高斯整数$z=a+bi$的$norm$为$N(z)=a^2+b^2$
特别地,定义$norm$等于$1$的高斯整数为$unit$,即单位元

Definition 1.3
对于高斯整数$x,y$,若存在高斯整数$a$使得$ax=y$,则称$x$为$y$的因子,记作$x|y$

Lemma 1.1
对于高斯整数$a,b$,$N(ab)=N(a)N(b)$

证明:设$a=a_1+a_2 i,b=b_1+b_2 i$,则

$LHS=(a_1 b_1 -a_2 b_2)^2+(a_1 b_2+a_2 b_1)^2=a_1^2 b_1^2+a_1^2 b_2^2+a_2^2 b_1^2+a_2^2 b_2^2$

$RHS=(a_1^2+a_2^2)(b_1^2+b_2^2)=a_1^2 b_1^2+a_1^2 b_2^2+a_2^2 b_1^2+a_2^2 b_2^2$

故$LHS=RHS$,引理成立

注:上述证明中,形如$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$的式子称为斐波那契恒等式
根据该恒等式可以得到柯西不等式及其取等条件

Lemma 1.2
对于高斯整数$a,b$,若$a|b$,则$N(a)|N(b)$,且逆命题不成立

证明:

(1)若$a|b$,设$b=az$,则$N(b)=N(az)=N(a)N(z)$,故$N(a)|N(b)$,命题成立

(2)若$N(a)|N(b)$,设$zN(a)=N(b)$,而$z$不一定能表示成$N(z)$的形式,故逆命题不成立

  

高斯素数


Definition 2.1
若高斯整数$z$不是单位元,且除自身及单位元外没有其他因子,则称$z$为高斯素数(Guassian Prime Integers)
比如说$2=(1+i)(1-i)$,故$2$不是高斯素数,而$3$不能继续分解,是高斯素数

Theorem 2.1
若素数$P$满足丢番图方程$x^2+y^2=P$无解,则$P$为高斯素数

(1)证明充分性:若$P$为素数且$(a,b)$是丢番图方程$x^2+y^2=P$的一组解

则$P=a^2+b^2=(a+bi)(a-bi)$,$P$不是高斯素数

(2)证明必要性:若$P$不是高斯素数,设$P=(x+yi)(a+bi)=ax-by+(bx+ay)i$

由于$P$是整数,故$ax-by=P$且$bx+ay=0$,得到$(a^2+b^2)x=aP$

由于$a+bi$不是单位元,$a^2+b^2\neq 1$,且P为素数,故$a^2+b^2=P$

故$P$不是高斯素数时,上述方程有解

Lemma 2.1
若高斯整数z满足N(z)是素数,则z是高斯素数

证明:若$z$不是高斯整数,则存在非单位元$a,b$满足$z=ab$

则$N(z)=N(ab)=N(a)N(b)$,故$N(z)$不是素数

注:引理2.1和定理2.1都是采用证明逆否命题的方式间接证明原命题

Theorem 2.2

高斯整数的代数基本定理(Fundermental Theorem of Arithmetic for Guassian Integers)
若$z$是高斯整数,不考虑单位元的影响,存在唯一的高斯素数分解方式使得$z=\prod z_i^{q_i}$

证明:根据代数基本定理,$N(z)=\prod N(z_i)^{q_i}$是唯一的,故$z=\prod z_i^{q_i}$是唯一的

注:在代数基本定理中$10=2\times5$,若考虑$-1$的话$10=(-2)\times(-5)$,分解不唯一
所以在代数基本定理中不考虑$-1$的影响,类似的,这里也不考虑单位元的影响

Lemma 2.2
$a^2+b^2\equiv 3(mod 4)$恒不成立

证明:(1)若$4|a^2$,则$a^2\equiv 0(mod 4)$

(2)若$4$不是$a^2$的因子,设$a=\prod p_i^{q_i}$,则$a^2=\prod p_i^{2q_i}$

由欧拉定理得$a^2\equiv \prod pi^{2q_i\%\phi(4)}\equiv \prod pi^{2q_i\%2}\equiv 1(mod 4)$

故$a^2 \equiv 0或1(mod 4)$,$a^2+b^2\equiv 0或1或2(mod 4)$

Lemma 2.3
若$q$是素数,且$q\equiv 3(mod 4)$,则$q$为高斯素数

证明:设$q=z_1 z_2$,且$z_1=a+bi$,则

$N(q)=q^2=N(z_1)N(z_2)$,而$N(z_1)=a^2+b^2\not\equiv 3(mod 4)$

故$N(z_1)\neq q$,因此必然有$N(z_1)=1$或$N(z_2)=1$

Lemma 2.4
若$q$为素数,且$q\equiv 1(mod 4)$,则存在高斯素数$z$使得$q=z\overline{z}$

证明:由于$q\equiv 1(mod 4)$,所以$(-1)^{\frac{q-1}{2}}=1$,故$-1$是模$q$意义下的二次剩余

故存在整数$c$满足$c^2\equiv -1(mod q)$,因此$q|(c+i)(c-i)$

但$(c+i)$和$(c-i)$都不能整除$q$,故$q$不是高斯素数,因此存在$z_1,z_2$,使得$q=z_1 z_2$

而$N(q)=q^2=N(z_1)N(z_2)$,故$N(z_1)=N(z_2)=q$,所以$z_1,z_2$互为共轭

  

平方和问题


Problem 3.1
求丢番图方程$a^2+b^2=n$的整数解$(a,b)$的个数

设$z=a+bi$,则$z\overline{z}=a^2+b^2=n$,所以问题就变成了求乘积为$n$的共轭高斯整数的数目

我们把$n$按照如下方式分解:$n=2^a \prod p_i^{q_i} \prod p_j^{q_j}$,其中$p_i \equiv 1(mod4)$,$p_j \equiv 3(mod 4)$

那么我们只需要把这些因子划分成两部分使得这两部分乘积的$norm$相等,划分的方案数就是答案

由Lemma2.3可知,$p_j$已经是高斯素数,不能继续分解

只能均分到这两部分,显然如果存在$q_j$是偶数,则方程无解

由Lemma2.4可知,$p_i$可以继续分解为两个共轭高斯整数

设$p_i=z\overline{z}$,则$p_i^{q_i}=z^{q_i}\overline{z}^{q_i}$

而复数相乘满足$norm$相乘,辐角相加,故分配时$z$与$\overline{z}$对两边模长的贡献是相同的

所以只需要保证两边分配的$z$和$\overline{z}$的总数相同即可

例如$5^2=(2+i)^2 (2-i)^2$,则分配方案如下:

(1)左边:$(2+i)(2+i)$  右边:$(2-i)(2-i)$

(2)左边:$(2+i)(2-i)$  右边:$(2-i)(2+i)$

(3)左边:$(2-i)(2-i)$  右边:$(2+i)(2+i)$

可以看出,$p_i^{q_i}$项共有$(q_i+1)$种分配方案,所以$\prod p_i^{q_i}$的贡献就是$\prod(q_i+1)$

而在Theorem2.2中,我们提到高斯整数分解时可以通过乘以单位元得到不同的分解方案

例如$5=(2+i)(2-i)=(-2-i)(-2+i)=(-1+2i)(-1-2i)=(1-2i)(1+2i)$

在考虑单位元的情况下,高斯整数就有4种分解方案,所以答案应该是$4\prod(q_i+1)$

最后我们再考虑$2^a$项的问题,注意到$2=(1+i)(1-i)=i(1-i)^2$

所以只能把$(1-i)$均等分配到两边,而$i$作为单位元不影响答案,故$2^a$只有一种分配方案

问题至此完美解决,最终的答案就是$4\prod(p_i+1)$

  

参考文献


当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器