本帖最后由 hejoseph 于 2025-5-23 10:50 编辑
设 $n$ 是 $4k+1$ 型素数，把 $\sqrt{n}$ 表示为循环连分数，循环节 $a_1,a_2,\cdots,a_{2m+1}$，把循环连分数 $$ 表示为
\[
\frac{p+\sqrt{n}}{q}
\]
的形式，则有 $n=p^2+q^2$。
例如 $\sqrt{5}$ 表示为循环连分数为 $$，循环节只有一位 $4$，循环连分数 $$ 值为
\[
2+\sqrt{5}
\]
所以 $5=1^2+2^2$。
$\sqrt{29}$ 表示为循环连分数为 $$，循环节为 $2,1,1,2,10$，循环连分数 $$ 值为
\[
\frac{2+\sqrt{29}}{5}
\]
所以 $29=2^2+5^2$。
hejoseph 发表于 2025-5-23 10:29
设 $n$ 是 $4k+1$ 型素数，把 $\sqrt{n}$ 表示为循环连分数，循环节 $a_1,a_2,\cdots,a_{2m+1}$，把循环连 ...
你真牛！人工智能给了我类似的回答，但是他的回答只涉及到连分数。
然后搞出的结果，但是他的很多都是错的，
然后我让人工智能搞了一个比较大的素数，
结果他穷举起来。把人恶心了！
你的这个让我看明白了！至少看明白其中的过程
hejoseph 发表于 2025-5-23 10:29
设 $n$ 是 $4k+1$ 型素数，把 $\sqrt{n}$ 表示为循环连分数，循环节 $a_1,a_2,\cdots,a_{2m+1}$，把循环连 ...
你的这个办法具有理论意义，但没有实际操作意义，
因为随着p的增大，计算量惊人的增加。
ContinuedFraction这是对应的mathematica函数，
你可以用p=10^20+129试试看
hejoseph 发表于 2025-5-23 10:29
设 $n$ 是 $4k+1$ 型素数，把 $\sqrt{n}$ 表示为循环连分数，循环节 $a_1,a_2,\cdots,a_{2m+1}$，把循环连 ...
按照你的办法，先得到根号97的连分数。
ContinuedFraction
得到
{9, {1, 5, 1, 1, 1, 1, 1, 1, 5, 1, 18}}
FromContinuedFraction[{0, {1, 1, 1, 5, 1, 18, 1, 5, 1, 1, 1}}]
得到
\[\frac{1}{9} \left(\sqrt{97}-4\right)\]
nyy 发表于 2025-5-23 11:53
按照你的办法，先得到根号97的连分数。
得到
Clear["Global`*"];(*mathematica11.2,win7(64bit)Clear all variables*)
p=601
aa=ContinuedFraction(*开根号的连分数*)
partb=aa[](*循环节*)
nn=Length(*循环节长度*)
mm=Floor(*长度的一半,取下整*)
bb={0,Join],partb[]]}(*对称的连分数*)
cc=FromContinuedFraction
以601为例子。
得到
\[\frac{1}{5} \left(\sqrt{601}-24\right)\]
本帖最后由 nyy 于 2025-5-23 20:24 编辑
我明白了！
1楼里面的代码利用了拉格朗日恒等式，
一个是向量的内积。一个是向量的外积，
https://www.zhihu.com/question/429904466/answer/2509408995
针对的是这儿的
如何笔算将某些数分拆为两个平方数之和
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=15803
(出处: 数学研发论坛)
NestWhile当然可以的
f :=NestWhile[{Mod[#[], #[]], #[]} &, {PowerMod, p}, #[]^2 > p &]; f
将单质数表为两数平方和的最快速算法
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=2836
(出处: 数学研发论坛)
原来这个问题在论坛上已经出现十几年了
我有一个疑问：x^2=-1(mod p)在0到p之间有两个x，
难道这两个x，都能导致写成平方和？
手工计算方法：以 $\sqrt{29}$ 得到的循环连分数 $$ 为 $x$，根据计算结果能得到
\begin{align*}
5+\frac{1}{2+\dfrac{1}{1+\dfrac{1}{x}}}=\sqrt{29}&\iff 2+\frac{1}{1+\dfrac{1}{x}}=\frac{1}{\sqrt{29}-5}=\frac{\sqrt{29}+5}{4}\\
&\iff 1+\frac{1}{x}=\frac{1}{\dfrac{\sqrt{29}+5}{4}-2}=\frac{\sqrt{29}+3}{5}\\
&\iff x=\frac{1}{\dfrac{\sqrt{29}+3}{5}-1}=\frac{\sqrt{29}+2}{5}
\end{align*}
或者直接用解方程的方法
\begin{align*}
x&=1+\frac{1}{2+\dfrac{1}{10+\dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{x}}}}}=1+\frac{1}{2+\dfrac{1}{10+\dfrac{1}{2+\dfrac{x}{x+1}}}}=1+\frac{1}{2+\dfrac{1}{10+\dfrac{x+1}{3x+2}}}\\
&=1+\frac{1}{2+\dfrac{3x+2}{31x+21}}=1+\frac{31x+21}{65x+44}=\frac{96x+65}{65x+44}
\end{align*}
整理就得
\[
5x^2-4x-5=0
\]
解这个方程就得（舍去负根）
\[
x=\frac{2+\sqrt{29}}{5}
\]
第一种方法较为简单。