本原勾股数组的参数化

直角三角形三边都是整数，这组数就叫勾股数。方程 $a^2+b^2=c^2$ 看起来像几何，真正要回答的却是三问：整数解长什么样、本原解有没有漏、怎么按参数把它们全部生成出来。下面把形式、证明和代码放在一起。

本原是什么意思

正整数 $a,b,c$ 满足

就称为一组勾股数，也叫勾股数组。对应的直角三角形三边都是整数。最熟的是 $3,4,5$，因为 $9+16=25$。把三边同时乘正整数 $k$，得到 $6,8,10$ 或 $9,12,15$，它们仍是勾股数，但只是同一形状的放大。

若 $\gcd(a,b,c)=1$，就叫本原勾股数组。本原解是种子：任意正整数解都可以写成某组本原解再乘一个 $k$。具体做法是先令 $k=\gcd(a,b,c)$，再看 $($，后者一定本原。所以只要把本原解分类清楚，全部勾股数就都有了。

还可以再说强一点：本原时 $a,b,c$ 两两互素。若素数 $p$ 同时整除 $a$ 和 $b$，则 $p$ 整除 $c^2$，从而整除 ，与本原矛盾。若 同时整除 和 ，则 整除 ，从而整除 ，同样矛盾。对 与 同理。因此本原不只是“三个数没有公共因子”，而是任意两个都没有公共因子。

本原解的形状

本原勾股数组里，$a$ 和 $b$ 不能都是奇数。先看平方数模 $4$ 只可能是 $0$ 或 $1$：偶数 $2\ell$ 的平方是 $4\ell^2$，奇数 的平方是 。两个奇数平方相加模 余 ，但没有任何平方数模 余 。所以 不可能。于是直角边一奇一偶，斜边 必为奇数——两个偶数平方相加是偶数，一奇一偶相加是奇数。

也不能两条直角边都是偶数：那会有公因子 $2$，直接不是本原。所以本原时奇偶模式是固定的：一奇一偶加一条奇数斜边。

约定把偶数那条直角边写成 $b$。则存在整数 $m>n>0$，满足

• $m$ 与 $n$ 一奇一偶
• $\gcd(m,n)=1$

使得

若希望偶数边在 $a$ 上，把 $a$ 与 $b$ 对调即可。所有本原解（不计两条直角边的顺序）都是这个样子，没有遗漏，也没有重复：不同的 $(m,n)$ 给出不同的三元组。

一般正整数解是再乘正整数 $k$：

这里 $m>n>0$ 仍要一奇一偶且互素，否则会把本该由 $k$ 承担的公因子算进参数里，造成重复枚举。

为什么参数必须互素、一奇一偶

先看必要性，后面证明充分性时会再碰到它们。

若 $m,n$ 有奇素数公因子 $p$，则 $p$ 同时整除 $a,b,c$，不是本原。若 $m,n$ 都是偶数，同样有公因子 $2$。

若 $m,n$ 都是奇数，则 $m^2-n^2$ 与 $m^2+n^2$ 都是偶数， 和 都偶数，三边有公因子 ，仍不是本原。模 也能看出来：奇数平方 ，差与和都 ，偶数平方却 ，两边对不上“本原且 为奇数”的设定。

因此本原参数必须互素，并且奇偶相反。这两个条件合在一起，还保证了 $m-n$ 与 $m+n$ 都是奇数，并且互素。证明互素并不难：若素数 $p$ 同时整除 $m-n$ 和 $m+n$，则 整除它们的和 与差 。但 是奇数，，于是 整除 和 ，与 矛盾。后面写 时会用到这一点。

从平方差推到两个平方

设 $(a,b,c)$ 本原，$b$ 偶数，$a,c$ 奇数。把方程改写成

$c-a$ 与 $c+a$ 都是正偶数。令

则 $v>u>0$，并且

关键是 $u$ 与 $v$ 互素。若素数 $p$ 同时整除二者，则 $p$ 整除 $v-u=a$ 和 $v+u=c$，从而整除 ，于是 整除 ，与两两互素矛盾。

$a$ 与 $c$ 都是奇数，所以 $u+v=c$ 为奇数，故 $u,v$ 一奇一偶。于是 $uv$ 是平方，且 $\gcd (u,v)=1$。互素的两个正整数乘积是平方，则它们各自都是平方。这是算术基本定理的直接推论：把 、 写成素因子幂的乘积，每个素数只能出现在其中一边；乘积里每个指数必须是偶数，所以每一边的指数各自已经是偶数。

也可以从唯一分解想：正整数是平方，当且仅当每个素因子指数为偶数。互素把素因子集合拆成不相交的两堆，于是每一堆自己就得是平方。

因此存在正整数 $m>n\ge 1$，使

从而

也就是 $b=2mn$。

还要核对 $m,n$ 的条件。$\gcd(u,v)=1$ 推出 $\gcd(m,n)=1$。$u,v$ 一奇一偶推出 不能都是奇数，互素又排除了都是偶数，故一奇一偶。 来自 。

反过来，任意满足这三个条件的 $m,n$，代入后是代数恒等式：

还要确认得到的是本原解。$a=m^2-n^2$ 与 $c=m^2+n^2$ 都是奇数， 是偶数，奇偶已经对了。若素数 同时整除 和 ，则 整除 和 。，故 整除 和 ，与互素矛盾。于是 ，从而 。形式既充分又必要。

不同的 $(m,n)$ 也不会撞车。由 $c+a=2m^2$、$c-a=2n^2$，参数被三边唯一确定。所以枚举满足条件的参数对，就是在无重复地遍历全部本原解。

单位圆上的有理点

同一件事可以用几何再说一遍。两边同除以 $c^2$：

本原勾股数一一对应于单位圆上的有理点（第一象限）。从点 $(-1,0)$ 向圆上另一点 $(x,y)$ 作直线，设斜率为 $t$。直线方程是 $y=t(x+1)$，代入 $$，整理后丢掉已知交点 ，得到

$t$ 是有理数时，右边分子分母都是有理数，交点就是有理点；反过来，有理点与 $(-1,0)$ 的连线斜率也是有理数。于是单位圆上的有理点被一个有理参数 $t$ 扫完。取 $t=n/m$，通分就回到

这就是参数化的几何来源。前面用平方差做的代数证明，和这里用直线扫圆，描述的是同一组公式。连分数出现在下一步：若要找很接近某个方向的有理点，就把该斜率的渐近分数代进去，得到圆上很好的有理逼近，也就是接近某个实直角三角形的勾股数组。这里只点到关系，不展开算法。

手算例子

例一：最小的本原解

$m=2$，$n=1$。已有 $m>n$，一奇一偶，$\gcd(2,1)=1$。

这就是 $3,4,5$。

例二：再往下几组

$m=3$，$n=2$，条件满足：

$5^2+12^2=25+144=169=13^2$。

$m=4$，$n=1$ 给出 $15,8,17$，偶数边是较小的那条。验算：$225+64=289=17^2$。， 给出 ，因为 。， 给出 ，两直角边已经很接近：。

注意 $m=5$，$n=4$ 也合法，得到 $9,40,41$。同一层 $m$ 可以对应多个 $n$，只要奇偶相反且互素。$m=5$ 时 与 都和 同为奇数，应丢掉；其中 会给出非本原的 。筛掉同奇偶之后，这一层只留下 和 。

例三：公式能算，但不是本原

$m=3$，$n=1$ 都是奇数。公式仍给出 $8,6,10$，约去 $2$ 才是 $3,4,5$。这就是参数奇偶相同会丢掉本原性的实例。若直接拿去枚举本原解，会重复，也会混进非本原。

$m=6$，$n=3$ 不互素，得到 $27,36,45$，是 $3,4,5$ 的 $9$ 倍。公因子可以预先看见：。

例四：从三边反推参数

已知 $20,21,29$。先看 $\gcd=1$，且 $20$ 偶数，故 $b=20=2mn$，所以 $mn=10$。又 ，。两式相加：，，；于是 。检查：，一奇一偶，互素。对得上。

一般做法：本原且 $b$ 偶数时，

两者都应该是整数。这正是前面 $v=m^2$、$u=n^2$ 的还原。

若给的是非本原，例如 $12,16,20$，先除掉 $k=\gcd=4$，得到本原核 $3,4,5$，再反推 $m=2$、。不要对 直接开方： 是平方， 也是平方，看起来像 、，但那对参数不互素，对应的正是把 吃进了 。两种写法表示同一组数，枚举时只保留互素的那一种。

一份可直接用的实现

下面生成斜边不超过 $N$ 的全部本原勾股数组，以及全部（含非本原）勾股数组。本原枚举只跑满足条件的 $(m,n)$；全部解再乘 $k$。

跑一下就能对上前面的手算。枚举对 $m=O(\sqrt N)$ 扫 $n$，再筛互素与奇偶，生成到很大的 $N$ 也够用。外层循环的真实尺度是 $m\le \sqrt{N}$，因为最小的 是 。输出时把较小的直角边放到前面，避免把 和 当成两组。

若题目改成“直角边不超过 $N$”或“周长不超过 $N$”，只要把判断从 $c$ 换成 $a$、$b$ 或 $a+b+c$。参数形式不用改，改的是停机条件。

面积，以及和连分数的一点关系

直角边为 $a,b$ 时面积是 $ab/2$。本原且 $b=2mn$ 时

这是一个三次型。问面积等于给定整数 $S$ 的直角三角形有哪些，就是在分解这个式子，和因数分解、同余接得上。例如本原面积为 $6$ 的只有 $3,4,5$；面积为 $30$ 的有 $5,12,13$。整数边且整数面积的三角形里，勾股数是最整齐的一类，因为直角已经把海伦公式收成了 $ab/2$。

连分数出现在逼近里。单位圆参数 $t$ 若取某个无理斜率的渐近分数，得到的有理点会非常接近那个方向。想让两直角边接近，相当于 $m^2-n^2$ 接近 $2mn$，也就是 $m/n$ 接近 $1+\sqrt{2}$。Pell 方程 的解正好给出 的好逼近，于是得到接近等腰的勾股数组：例如 已经比较接近， 更近。不必把连分数整套搬过来，只要记得参数 越接近 一类单位，三角形就越接近等腰。

写代码时容易踩的坑

$m,n$ 必须一奇一偶。只写 $\gcd(m,n)=1$ 不够，$3$ 与 $1$ 互素，却给出 $6,8,10$。

不要把 $k$ 和 $(m,n)$ 的角色混掉。生成全部解时，先枚举本原再乘 $k$；若允许 $m,n$ 不互素或不限奇偶，同一组 $(a,b,c)$ 会被生成多次。

$a=m^2-n^2$ 可能比 $b=2mn$ 更大，也可能更小。比较或输出时约定 $a\le b$，否则列表里会以为多了一组。

斜边限制是 $m^2+n^2\le N$，不是 $m\le \sqrt N$。 接近 时 ，循环上界要比 更大一些；用 本身判断最稳。上面用 做外层截止，是因为 时 。

本原的定义是 $\gcd(a,b,c)=1$，不是“有一条边为素数”。$20,21,29$ 三边都合数，仍然本原。

$n$ 从 $1$ 起且 $m>n$，不要取 $n=0$：那会得到 $b=0$，退化成线段，不是三角形。

判断本原时用 $\gcd(a,b,c)$，不要只看 $\gcd(a,b)$。虽然本原时两者等价，但若输入已经乘过 $k$，只检查两条直角边会漏掉斜边里的因子——实践上三条一起求最省事。

生成后最好抽几组验算 $a^2+b^2=c^2$，并确认本原列表里没有偶数的 $c$。这两条能挡住绝大多数实现错误。

和更高次方程的边界

费马大定理说 $n\ge 3$ 时 $x^n+y^n=z^n$ 没有正整数解。$n=2$ 之所以有无穷多解，正是因为单位圆是有理曲线，能被一条有理斜率的直线扫完。次数升高后不再是亏格 ，有理点就稀了。勾股数的参数化是这条分界线上最整齐的一侧。

所以不必把 $a^2+b^2=c^2$ 看成小学奥数。它是二次不定方程里可以彻底列完的那一层。把本原条件、参数形式和枚举三件事分开，手算和代码就会对得上。