数论 | 勾股数组

2019-03-01 本文已影响0人 0与1的邂逅

前言

勾股定理想必大家都不陌生，它表明任一个直角三角形的两条直角边长的平方和等于斜边长的平方。其公式形式如下：

$a^2+b^2=c^2$
勾股定理还有另一个名称——毕达哥拉斯定理，相应的直角三角形也称为毕达哥拉斯三角形。

对于不直到勾股定理的童鞋，也没什么关系，因为这里不是要讨论直角三角形，而是要探讨勾股数组（也称毕达哥拉斯三元组）。

勾股数组

定义：
一般地，若三角形三边长a，b，c都是正整数，且满足a，b的平方和等于c的平方，那么数组（a，b，c）称为勾股数组。勾股数组是人们为了解出满足勾股定理的不定方程的所有整数解而创造的概念。

举些例子：

(3,4,5) (5,12,13) (6,8,10) (7,24,25) (8,15,17) (9,40,41) (10,24,26) (11,60,61)

上面的例子只是一部分，这使我们想到一个问题：
$是否存在无穷多个勾股数组，$ $即满足方程a^2+b^2=c^2的自然数三元组（a,b,c）。$ 这个问题的答案是肯定的，如果取勾股数组(a,b,c)，用整数d乘它，则得到新的勾股数组(da,db,dc)，这是成立的。因为 $(da^2)+(db^2)=d^2(a^2+b^2)=d^2c^2=(dc)^2$ 但是，显然这些新的勾股数组并不令人感兴趣，我们转而关注没有（大于1）公因数的三元组，这些三元组有一个专属名称——本原勾股数组。

本原勾股数组

本原勾股数组(简写为PPT)是一个三元组(a,b,c)，其中a,b,c没有公因数，且满足
$a^2+b^2=c^2$ ——摘自Joseph H. Silverman《数论概论》(第三版)

下面给出一些本原勾股数组。

(3,4,5) (5,12,13) (8,15,17) (7,24,25)
(20,21,29) (9,40,41) (12,35,37) (11,60,61)
(28,45,53) (33,56,65) (16,63,65)

观察上面的本原勾股数组，我们可以发现似乎a与b的奇偶性不同，且c总是奇数。

这些猜想是正确的，来看看如何证明。

首先，如果a与b都是偶数，则c也是偶数。这意味着a、b、c有公因数2，所以该三元组不是本原的。

其次，假设a、b都是奇数，那么c必是偶数。证明如下：
假定存在整数x、y、z使得 $a=2x+1,b=2y+1,c=2z$ 将其带入方程 $a^2+b^2=c^2$ 得 $(2x+1)^2+(2y+1)^2=(2z)^2$ $=>4x^2+4x+4y^2+4y+2=4z^2$ $=>2x^2+2x+2y^2+2y+1=2z^2$ 最后一个等式说的是，一个奇数等于一个偶数，这是不可能的，所以a与b不能都是奇数。
我们已证明a、b不可能都是偶数，也不可能都是奇数，故a、b的奇偶性不同。
再由方程 $a^2+b^2=c^2$ 可得c是奇数。(根据奇数的平方还是奇数，偶数的平方还是偶数)

问题转换

考虑到a、b的互换性，可以将问题转换成求解方程 $a^2+b^2=c^2,其中a是奇数,b是偶数,a、b、c没有公因数$ 的所有自然数解。我们使用的工具是因式分解和整除性。

如果(a,b,c)是本原勾股数组，则可以进行因数分解 $0a^2=c^2-b^2=(c-b)(c+b)$

下面举一些例子，注意我们总是取a为奇数且b为偶数。

观察上面的例子，我们发现：

c-b 与 c+b 没有大于1的公因数，即 c-b 与 c+b 互素
(注意：a|b 其实就是 b%a=0，表示a整除b)

c-b 与 c+b 都是平方数
（本人很弱，暂时还搞不懂如何证明）

勾股数组定理

根据上面的分析，我们记 ${c+b=s^2 } , {c-b=t^2}$ 其中s>t≥1是没有大于1的公因数的奇数。

联立上面两个关于b和c的方程，解得 $b=\frac{s^2-t^2}2,c=\frac{s^2+t^2}2$

于是， $a=\sqrt{(c-b)(c+b)}=st$

重新进行整理，可得到勾股数组定理。

勾股数组定理：
每个本原勾股数组(a,b,c)（其中a为奇数，b为偶数）都可从如下公式得出： $a=st,b=\frac{s^2-t^2}2,c=\frac{s^2+t^2}2$ 其中s>t≥1是没有大于1的公因数的奇数。
特别的，如果取t=1，则得到三元组 $(s,\frac{s^2-1}2,\frac{s^2+1}2)$ ，它的b与c恰好仅相差1。

下表列出了s≤9时所有可能的三元组。

写在最后

参考资料：

Joseph H. Silverman《数论概论》(第三版)
博客：https://www.luogu.org/blog/lhc/TheStoryOfPythagoreanTriples
百度百科

本人很弱，如有错误，欢迎指正。