如何把一个4k+1的素数表达成两个整数的平方和

nyy

4k+1素数的最小非负剩余有多大？

nyy

hejoseph 发表于 2025-5-24 18:51
手工计算方法：以 $\sqrt{29}$ 得到的循环连分数 $[1,2,10,2,1]$ 为 $x$，根据计算结果能得到
\begin{align ...

一般连分数的递推公式与简单连分数的递推公式类似。

对于一般连分数[a_0;a_1,a_2,\cdots,a_n]，设其第k个渐近分数为\frac{p_k}{q_k}，则有以下递推公式：

p_0 = a_0，q_0 = 1

p_1 = a_0a_1 + 1，q_1 = a_1

当k\geq2时：

p_k = a_kp_{k - 1}+p_{k - 2}

q_k = a_kq_{k - 1}+q_{k - 2}

这个递推公式对于有限连分数和无限连分数都适用。在无限连分数的情况下，通过不断迭代这个递推公式，可以得到一系列渐近分数，这些渐近分数会逐渐逼近连分数所表示的实数。

nyy

nyy 发表于 2025-5-24 18:54
4k+1素数的最小非负剩余有多大？

应该是最小非负非剩余！
用来寻找上面的x的
其中x^2=-1(mod p)

nyy

northwolves 发表于 2025-5-23 23:03
NestWhile当然可以的

1. Clear["Global`*"];(*mathematica11.2,win7(64bit)Clear all variables*)
   
2. (*子函数,用来把p=4k+1型的素数表达成两个正整数的平方和*)
   
3. f[p_]:=Module[{a,x},
   
4.     If[Mod[p,4]!=1,Print["素数必须是4k+1型"];Return[False]];
   
5.     a=NestWhile[(1+#)&,2,JacobiSymbol[#,p]!=-1&];(*依次从2 3 4 5 6...当中找到p的第一个非剩余,为找x^2=-1(mod p)打基础*)
   
6.     x=PowerMod[a,(p-1)/4,p];(*x^2=(a^((p-1)/4))^2=a^((p-1)/2)=-1(mod p)*)
   
7.     NestWhile[{#[[2]](*new被除数*),Mod[#[[1]](*old被除数*),#[[2]](*old除数*)](*new除数*)}&,{p,x}(*初始被除数与除数*),#[[1]]^2>=p&(*被除数最终必须<根号p,除数是小于被除数的*)](*不断辗转相除法,找到小于根号p的两个余数*)
   
8. ]
   
9. f[10^200+357]
   

复制代码

求解结果
{873429951469709641509232442226217264348765117359661005804455107522305\
9534652741558693062858574717874, \
4869498124813486982231377956355473573990401367667605534476012902371537\
410710789858816644285044662191}