如何把一个4k+1的素数表达成两个整数的平方和
本帖最后由 nyy 于 2025-5-21 13:29 编辑如何笔算将某些数分拆为两个平方数之和
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=15803
(出处: 数学研发论坛)
https://bbs.emath.ac.cn/forum.php?mod=redirect&goto=findpost&ptid=15803&pid=78125
这儿有例子！
作者：东城居士
链接：https://www.zhihu.com/question/340796389/answer/1900975429948519641
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Don Zagier 的证明虽然非常巧妙，但并没有告诉我们如何寻找正整数 aaa 和 b.b.b. 是否有一种有效的算法求出 a,ba,ba,b 呢？对于这个问题，同样是在 1990 年 的 The American Mathematical Monthly 97 上，Stan Wagon 介绍了如下简单高效堪称天秀般的算法：首先求出 x2≡−1 (mod p)x^2\equiv-1~(mod ~p)x^2\equiv-1~(mod ~p) 的正整数解 x,x,x, 然后将 ppp 和 xxx 做辗转相除，则不超过 p\sqrt{p}\sqrt{p} 的两个最大的余数即为要求的 aaa 和 b.b.b. 比如 p=111111111111111111111113≡1 (mod 4),p=111111111111111111111113\equiv1~(mod ~4),p=111111111111111111111113\equiv1~(mod ~4), 求出 x2≡−1 (mod p)x^2\equiv-1~(mod ~p)x^2\equiv-1~(mod ~p) 的正整数解为 x=37673906709576022058672.x=37673906709576022058672.x=37673906709576022058672. 将 ppp 和 xxx 做辗转相除，可得余数分别为
这个算法很不错，虽然我不知道原理，发上来共享一下，不知道对于不是素数的整数是否成立！
Clear["Global`*"];(*mathematica11.2,win7(64bit)Clear all variables*)
(*4k+1素数*)
p=10^20+129
(*找到x^2=-1(mod p),随机选择一个a,使得a是非剩余,然后计算得到x*)
Do==-1,a=k;Break[]],{k,2,10^10}];
Print;
x=PowerMod;(*x^2=(a^((p-1)/4))^2=a^((p-1)/2)=-1(mod p)*)
(*准备辗转相除法*)
k=0;(*计数,辗转相除法中小于根号p的余数的个数*)
{a,b}={p,x}(*辗转相除法最初两个数的初始赋值*)
out={};(*用来保存小于根号p的最大的两个整数*)
While>0&&k<2,
r=Mod;(*求余数*)
{a,b}={b,r};(*得到新的被除数与除数*)
If,out=Append;k=k+1]
]
Print[{out,p,Total-p}](*打印出两个数与素数,并且检验a^2+b^2-p是否等于零*)
代码写出来了，虽然是比较丑的代码，但是能用！ nyy 发表于 2025-5-21 13:21
代码写出来了，虽然是比较丑的代码，但是能用！
{{
8734299514697096415092324422262172643487651173596610058044551075223059534652741558693062858574717874,
4869498124813486982231377956355473573990401367667605534476012902371537410710789858816644285044662191
},
10^200+357,
0}
10^200+357写成两个整数的平方和 nyy 发表于 2025-5-21 13:25
{{
87342995146970964150923244222621726434876511735966100580445510752230595346527415586930628585747 ...
有价值的是上面那个算法！
那个算法比较神奇！ nyy 发表于 2025-5-21 22:11
有价值的是上面那个算法！
那个算法比较神奇！
这个算法思想很赞，你的代码可以优化，比如使用NestWhile
秀出你的代码！ 本帖最后由 northwolves 于 2025-5-23 09:55 编辑
f := (a = NestWhile != -1 &];
b = PowerMod;
NestWhileList[{Mod[#[], #[]], #[]} &,Sort[{p, b}], #[]^2 > p &][[-1]]);
f
{4869498124813486982231377956355473573990401367667605534476012902371537410710789858816644285044662191,8734299514697096415092324422262172643487651173596610058044551075223059534652741558693062858574717874} Let p be a prime number of the form 4k+1. Fermat's theorem asserts that p is a sum of two squares, p=x2+y2.
There are different proofs of this statement (descent, Gaussian integers,...). And recently I've learned there is the following explicit formula (due to Gauss): x=12(2kk)(modp), y=(2k)!x(modp) (|x|,|y|<p/2). But how to prove it?
https://math.stackexchange.com/questions/74132/explicit-formula-for-fermats-4k1-theorem
这个算法直接给出解了！但是非常难算，不实用！ northwolves 发表于 2025-5-23 09:26
{4869498124813486982231377956355473573990401367667605534476012902371537410710789858816644285044662 ...
NestWhile[(1 + #) &, 2, (JacobiSymbol[#, p] != -1) &]
个人认为，你的代码应该写成这样。
后面的是一个函数，所以这行代码应该有两个&
按照标准写法是这样，不知道你的怎么回事。
看别人的代码费劲。
尤其是一行代码，且没注释没缩进的代码 一句代码
f:=NestWhileList[{Mod[#[],#[]],#[]}&,Sort[{p,PowerMod!=-1&],(p-1)/4,p]}],#[]^2>p&][[-1]]; How to prove that all primes of the form4k+1can be represented by the sum of two squares in only one way regardless of the order?
https://math.stackexchange.com/questions/2855583/how-to-prove-that-all-primes-of-the-form-4k1-can-be-represented-by-the-sum-of