4k+1素数的最小非负剩余有多大？
hejoseph 发表于 2025-5-24 18:51
手工计算方法：以 $\sqrt{29}$ 得到的循环连分数 $$ 为 $x$，根据计算结果能得到
\begin{align ...
一般连分数的递推公式与简单连分数的递推公式类似。
对于一般连分数，设其第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 发表于 2025-5-24 18:54
4k+1素数的最小非负剩余有多大？
应该是最小非负非剩余！
用来寻找上面的x的
其中x^2=-1(mod p)
northwolves 发表于 2025-5-23 23:03
NestWhile当然可以的
Clear["Global`*"];(*mathematica11.2,win7(64bit)Clear all variables*)
(*子函数,用来把p=4k+1型的素数表达成两个正整数的平方和*)
f:=Module[{a,x},
If!=1,Print["素数必须是4k+1型"];Return];
a=NestWhile[(1+#)&,2,JacobiSymbol[#,p]!=-1&];(*依次从2 3 4 5 6...当中找到p的第一个非剩余,为找x^2=-1(mod p)打基础*)
x=PowerMod;(*x^2=(a^((p-1)/4))^2=a^((p-1)/2)=-1(mod p)*)
NestWhile[{#[](*new被除数*),Mod[#[](*old被除数*),#[](*old除数*)](*new除数*)}&,{p,x}(*初始被除数与除数*),#[]^2>=p&(*被除数最终必须<根号p,除数是小于被除数的*)](*不断辗转相除法,找到小于根号p的两个余数*)
]
f
求解结果
{873429951469709641509232442226217264348765117359661005804455107522305\
9534652741558693062858574717874, \
4869498124813486982231377956355473573990401367667605534476012902371537\
410710789858816644285044662191}