勾股数的一些性质

王熙文 · 2024-09-20 16:31:43 · 算法·理论

勾股数是指 a^2+b^2=c^2 的 (a,b,c)。

结论：当 \gcd(a,b)=1 且 a 为偶数时（若 a,b 都为奇数，则一定不存在 c，否则可以通过交换 a,b 让 a 变为偶数），一定存在 (m,n) 使得 a=2mn,b=m^2-n^2,c=m^2+n^2。

注意：通过 (m,n) 生成的 a,b 不一定满足 \gcd(a,b)=1。

证明：

因为 \gcd(a,b)=1 且 \gcd(b,c)|a，所以 \gcd(b,c)=1。

将 a^2+b^2=c^2 变为 a^2=(c-b)(c+b)。因为 a^2 一定是 4 的倍数，且 c-b 与 c+b 同奇偶（否则无法求出 b,c），所以 c-b 和 c+b 都是偶数。设 x=\dfrac{c-b}{2},y=\dfrac{c+b}{2}。因为 \gcd(x,y)|(x+y)（即 c），\gcd(x,y)|(y-x)（即 b）且 \gcd(b,c)=1，所以 \gcd(x,y)=1。

因为 xy=\dfrac{a^2}{4} 是完全平方数且 \gcd(x,y)=1，所以 x 和 y 分别是完全平方数。构造 m=\sqrt{x},n=\sqrt{y} 即可，代入即可得到 a=2mn,b=m^2-n^2,c=m^2+n^2。同时，因为 b+c=2m^2，所以 m 一定 =\sqrt{x}，同理可知 m 一定 =\sqrt{y}，所以 m,n 是唯一的。

结论：a,b,c\le n 的勾股数的个数为 \mathcal O(n\log n)。

证明：

所有勾股数都可以通过将 \gcd(a,b)=1 的勾股数的每个数扩大若干倍得到。

考虑枚举 \gcd(a,b)=1 的勾股数的 m,n，则个数为 \mathcal O(\sum\limits_{i=1}^{\sqrt{n}} \sum\limits_{j=1}^{i-1} \dfrac{n}{i^2+j^2})。因为 j^2<i^2，所以删掉 j^2 不会影响量级，个数为 \mathcal O(\sum\limits_{i=1}^{\sqrt{n}} i \cdot \dfrac{n}{i^2})=\mathcal O(n\log n)。

错误的实现得到了正确的结果：因为公式要求 a 是偶数，所以如果 b 是奇数，生成的数 (x,y,z) 要交换一下顺序变为 (y,x,z)。但判断的地方判成了 y 是否是奇数。但将生成的数去重后仍然得到了正确的结果。

原因：当 m^2-n^2 是奇数，k 是偶数时，a=k(m^2-n^2),b=2mnk 的数生成不到。接下来要证明它们可以通过别的方式生成出来。只需要证明 k=2 时存在 x,y 使得 a=2xy,b=x^2-y^2，剩下的都可以通过扩倍达到。a=2(m+n)(m-n)，因此很自然地设 x=m+n,y=m-n，发现恰好满足 b=4mn，因此所有勾股数都可以被生成。