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

hejoseph

设 $n$ 是 $4k+1$ 型素数，把 $\sqrt{n}$ 表示为循环连分数，循环节 $a_1,a_2,\cdots,a_{2m+1}$，把循环连分数 $[a_{m+1},a_{m+2},\cdots,a_{2m+1},a_1,\cdots,a_m]$ 表示为
\[
\frac{p+\sqrt{n}}{q}
\]
的形式，则有 $n=p^2+q^2$。
例如 $\sqrt{5}$ 表示为循环连分数为 $[2,4]$，循环节只有一位 $4$，循环连分数 $[4]$ 值为
\[
2+\sqrt{5}
\]
所以 $5=1^2+2^2$。
$\sqrt{29}$ 表示为循环连分数为 $[5,2,1,1,2,10]$，循环节为 $2,1,1,2,10$，循环连分数 $[1,2,10,2,1]$ 值为
\[
\frac{2+\sqrt{29}}{5}
\]
所以 $29=2^2+5^2$。

nyy

hejoseph 发表于 2025-5-23 10:29
设 $n$ 是 $4k+1$ 型素数，把 $\sqrt{n}$ 表示为循环连分数，循环节 $a_1,a_2,\cdots,a_{2m+1}$，把循环连 ...

你真牛！人工智能给了我类似的回答，但是他的回答只涉及到连分数。
然后搞出的结果，但是他的很多都是错的，
然后我让人工智能搞了一个比较大的素数，
结果他穷举起来。把人恶心了！
你的这个让我看明白了！至少看明白其中的过程

nyy

hejoseph 发表于 2025-5-23 10:29
设 $n$ 是 $4k+1$ 型素数，把 $\sqrt{n}$ 表示为循环连分数，循环节 $a_1,a_2,\cdots,a_{2m+1}$，把循环连 ...

你的这个办法具有理论意义，但没有实际操作意义，
因为随着p的增大，计算量惊人的增加。
ContinuedFraction[97^(1/2)]这是对应的mathematica函数，
你可以用p=10^20+129试试看

nyy

hejoseph 发表于 2025-5-23 10:29
设 $n$ 是 $4k+1$ 型素数，把 $\sqrt{n}$ 表示为循环连分数，循环节 $a_1,a_2,\cdots,a_{2m+1}$，把循环连 ...

按照你的办法，先得到根号97的连分数。

1. ContinuedFraction[97^(1/2)]

复制代码

得到
{9, {1, 5, 1, 1, 1, 1, 1, 1, 5, 1, 18}}

1. FromContinuedFraction[{0, {1, 1, 1, 5, 1, 18, 1, 5, 1, 1, 1}}]

复制代码

得到
\[\frac{1}{9} \left(\sqrt{97}-4\right)\]

nyy

nyy 发表于 2025-5-23 11:53
按照你的办法，先得到根号97的连分数。

得到

1. Clear["Global`*"];(*mathematica11.2,win7(64bit)Clear all variables*)
   
2. p=601
   
3. aa=ContinuedFraction[p^(1/2)](*开根号的连分数*)
   
4. partb=aa[[2]](*循环节*)
   
5. nn=Length[partb](*循环节长度*)
   
6. mm=Floor[nn/2](*长度的一半,取下整*)
   
7. bb={0,Join[partb[[mm+1;;nn]],partb[[1;;mm]]]}(*对称的连分数*)
   
8. cc=FromContinuedFraction[bb]
   

复制代码

以601为例子。
得到
\[\frac{1}{5} \left(\sqrt{601}-24\right)\]

nyy

我明白了！
1楼里面的代码利用了拉格朗日恒等式，
一个是向量的内积。一个是向量的外积，

https://www.zhihu.com/question/429904466/answer/2509408995

针对的是这儿的
如何笔算将某些数分拆为两个平方数之和
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=15803
(出处: 数学研发论坛)

northwolves

NestWhile当然可以的

1. f[p_] :=NestWhile[{Mod[#[[2]], #[[1]]], #[[1]]} &, {PowerMod[2, (p - 1)/4, p], p}, #[[2]]^2 > p &]; f[10^200 + 357]

复制代码

nyy

将单质数表为两数平方和的最快速算法
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=2836
(出处: 数学研发论坛)

原来这个问题在论坛上已经出现十几年了

nyy

我有一个疑问：x^2=-1(mod p)在0到p之间有两个x，
难道这两个x，都能导致写成平方和？

hejoseph

手工计算方法：以 $\sqrt{29}$ 得到的循环连分数 $[1,2,10,2,1]$ 为 $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}
\]
第一种方法较为简单。