勾股数通项公式

ryderyang · 2025-07-07 07:22:02 · 算法·理论

我们需要找到所有满足 a^2+b^2=c^2 的正整数 (a,b,c)，其中 a、b、c 互质，在这样的三元组叫做本原勾股数。如果允许 a、b、c 有除 1 以外的其他公因数，则所有的解可以表示为：

其中 (a_0,b_0,c_0) 是一组本原勾股数。

所以，我们只需要研究本原勾股数就行了。

观察一下

我们可以先观察一下勾股数表格，可以发现，a 和 b 不会同时为奇数。接下来，我们可以尝试证明这一点。

首先，如果 a 和 b 都是奇数，那么 c 就应该是偶数。

• - $a^2 \equiv 1\times 1 \pmod 4$，$b^2 \equiv 3 \times 3 \pmod 4$。 - $c^2 \equiv 2 \pmod 4
• - $a^2 \equiv 3\times 3 \pmod 4$，$b^2 \equiv 1 \times 1 \pmod 4$。 - $c^2 \equiv 2 \pmod 4
• - $a^2 \equiv 3\times 3 \pmod 4$，$b^2 \equiv 3 \times 3 \pmod 4$。 - $c^2 \equiv 2 \pmod 4

但是，c^2 应该是 4 的倍数，前后矛盾了，所以 a 和 b 不可能同时是奇数。

数学推导

在这里，我们不妨设：

• 那么，c 就是奇数。

我们的方程是：

转化一下：

我们可以设 b=2 \times k，那么有：

两边同时除以 4：

在这里，我们可以设 m=\frac{c-a}{2}，n=\frac{c+a}{2}。

那么，有：

因为 a 和 c 互质，所以 m 和 n 也互质，不然 a 和 c 就会有公因数 \gcd(m,n)。

因为 n 和 m 互质，并且 n \times m 是完全平方数，所以 n 和 m 也是完全平方数。

我们设 m=s^2，n=t^2，那么就有：

• 但是，有三个约束条件：

举个例子

这里就设 t=7，并且 s=4。

那么就有：