已知勾股数斜边c求整数直角边a、b的方法（含大位数场景）

先明确精确解的必要前提 #

首先得搞清楚：不是所有数都能当勾股数的斜边。根据数论结论，一个正整数c能作为勾股数的斜边，当且仅当在它的素因数分解中，每个形如4k+3的素数的指数都是偶数。比如7是4×1+3型素数，如果c里包含7的奇数次幂，那肯定不存在整数a,b满足$a^2 + b^2 = c^2$。

但对于2048位且无法因式分解的c，你根本没法验证这个条件——不知道素因子结构，直接给精确解的计算设了第一个障碍。

精确解法的困境（针对无法因式分解的大c） #

如果c确实满足上述条件，理论上存在整数a,b，但要找到它们，核心依赖于c的因式分解或者c的两平方表示：

• 欧几里得公式告诉我们，所有本原勾股数（a,b,c互质）都可以表示为$a=m^2-n2$，$b=2mn$，$c=m²⁺ⁿ2$（其中m>n>0，互质且一奇一偶）。如果c是本原勾股数的斜边，那它必须是4k+1型素数或这类素数的乘积，且能写成两个平方数的和。
• 对于合数c，需要把它分解成若干个4k+1型素数、平方数、以及2的乘积，再组合每个素因子的两平方表示，最终得到c的两平方表示，进而生成a,b。

但问题来了：你的c是2048位且无法因式分解的。目前数论算法中，找大整数的两平方表示本质上依赖于素因数分解（比如Cornacchia算法需要知道c的素因子）。如果c是合数且分解不出来，没有已知高效算法能直接找到a,b——这难度和因式分解这个NP-hard问题相当，甚至可以说，找到a,b等价于完成c的部分因式分解（因为$a^2+b2=(a+bi)(a-bi)$，这是高斯整数环里的分解，对应整数环里c的分解）。

如果c是4k+1型大素数（无法分解的话，大概率是素数或强伪素数），还有一线希望：可以用Cornacchia算法找m,n使得$c=m²⁺ⁿ2$，进而得到a,b。但该算法需要先找到c的一个二次剩余（比如找x使得$x^2≡-1 \mod c$），这一步对大素数可以用Tonelli-Shanks算法，但如果c是合数且无法分解，Tonelli-Shanks也没法用。

近似解法的可行思路 #

如果精确解找不到或者不存在，可找整数a,b使得$a^2+b2$尽可能接近$c^2$，误差尽可能小：

• 贪心调整法：先取a为最接近$c/\sqrt{2}$的整数（因为当a=b时，$2a^2=c2$，所以a近似等于$c/\sqrt{2}$），然后计算$b^2=c2 - a^{2$，看b是否接近整数。如果不是，就逐步调整a（±1），直到$b}2$最接近完全平方数。对于2048位的数，调整次数不会太多——c/√2附近的a，微小变化会让$b^2$的变化量为$2a±1$，很快就能找到最接近的平方数。
• 模运算筛选法：先用模运算排除不可能的a，缩小搜索范围：
  • 若c是奇数，$c^2≡1 \mod4$，则$a^2+b2≡1 \mod4$，因此a和b必须一奇一偶；若c是偶数，$c^2≡0 \mod4$，则a和b必须同为偶数。
  • 再用模3、模5等规则筛选：比如平方数mod3只能是0或1，所以$a^2+b2$要么都为0 mod3，要么一个0一个1，不符合的a直接排除。
• 连分数展开法：将问题转化为找有理点$(a/c, b/c)$尽可能接近单位圆上的点，通过对√2的连分数展开，找到最优有理近似，进而得到近似的a,b值。

总结 #

• 如果c不满足勾股数斜边的必要条件（4k+3型素数指数为偶），精确解不存在；
• 如果c满足条件但无法因式分解，当前没有高效的精确解法——这本质上和大整数因式分解的难度绑定，2048位的数目前在无特殊情况下无法快速分解；
• 近似解法可通过贪心调整、模运算筛选或连分数展开找到接近的整数对，能保证$a^2+b2$和$c^2$的误差极小。

内容的提问来源于stack exchange，提问作者Gabe Kurtis