将4n+1型素数表为二平方和

hbghlyj

一個正整數 $n$ 是兩個平方之和，若且唯若所有$n$的符合$p≡3\pmod4$的質因數 $p$ 有偶數次方。
例子：98=2×7² 滿足 p≡3(mod 4) 的 p 只有 7，而 $v_7(98)=2$ 是偶數，所以 98 可以寫成兩個平方之和。

---

用Mathematica可以在$\mathbb{Z}[i ]$上FactorInteger
例如FactorInteger[13, GaussianIntegers -> True]得出$13=2^2+3^2$
但是能否不依赖于Mathematica内置的FactorInteger，用数学知识重新写一个函数？

如何将素数 p=4n+1 表为二平方和？

按照wstein.org/edu/2010/414/projects/hoon_kwon.pdf 的方法，先由Lemma 2.6. 求出$m$使得$p\mid m^2+1$
例如$n=3$，$p=4n+1=13$，以上求出$m=5$，满足$p\mid m^2+1$.

再按照Theorem 2.7. 求 $p$ 与 $m\pm i$ 的 GCD，就能将 $p$ 分解了。用Mathematica可以在$\mathbb{Z}[i ]$上求GCD。

1. gaussianIntegerFactor[p_ /; PrimeQ[p] && Divisible[p - 1, 4]] :=
2. Module[{m = Fold[Mod[#1 #2, p] &, Range[(p - 1)/2]]},
3.   ReIm[GCD[m + I, p]]]

Copy the Code

gaussianIntegerFactor[5]
得到$5=1^2+2^2$

gaussianIntegerFactor[13]
得到$13=2^2+3^2$

gaussianIntegerFactor[17]
得到$17=1^2+4^2$

gaussianIntegerFactor[29]
得到$29=2^2+5^2$

hbghlyj

Wikipedia上有一个神奇的算法。

... apply the Euclidean algorithm with $ p $ and $ x $. Denote the first two remainders that are less than the square root of $ p $ as $ a $ and $ b $. Then it will be the case that $ a^{2}+b^{2}=p $.

这个算法只需在$\mathbb{Z}$上求GCD，不需要像上面那样在$\mathbb{Z}[i ]$上求GCD。如何证明呢？