称一个正整数三元组 \((a,b,c)\) 为一组本原勾股数，当且仅当其满足 \(a^2+b^2=c^2\) 且 \(\gcd(a,b,c)=1\)。
不是本原勾股数的勾股数被称作派生勾股数。
任意本原勾股数 \((a,b,c)\) 的任意 \(k\) 倍对应着一组勾股数 \((ka,kb,kc)\)。同时一组勾股数 \((a,b,c)\) 唯一对应着一组本原勾股数，即 \((\frac{a}{\gcd(a,b,c)},\frac{b}{\gcd(a,b,c)},\frac{c}{\gcd(a,b,c)})\)。
-
引理 1：若 \((a,b,c)\) 为本原勾股数，则 \(a,b\) 奇偶性不同且 \(c\) 为奇数。
证明：若 \(a,b\) 奇偶性相同，则必有 \(a^2+b^2=c^2\) 为偶数，则 \(c\) 为偶数，\(c^2\) 为 \(4\) 的倍数。
若 \(a,b\) 均为偶数，则 \(2|\gcd(a,b,c)\)，矛盾。
若 \(a,b\) 均为奇数，注意到奇数的平方模 \(4\) 余 \(1\)，故 \(a^2+b^2\equiv 2\not\equiv c^2\pmod 4\)，矛盾。
-
引理 2：若 \((a,b,c)\) 为本原勾股数，则 \(\gcd(a,b)=\gcd(a,c)=\gcd(b,c)=1\)。
证明：根据 \(a^2+b^2=c^2\)，若 \(a,b,c\) 中有二者是 \(k\)（\(k>1\)）的倍数，则剩下一者也会是 \(k\) 的倍数。
-
定理 1（欧几里得公式）：使用如下方法可以找出所有本原勾股数：
\[\begin{aligned} a&=m^2-n^2\\ b&=2mn\\ c&=m^2+n^2 \end{aligned} \]其中 \(m>n\geq 1\)，\(m,n\) 互质且 \(m,n\) 奇偶性不同。
证明：
首先证明任意本原勾股数都能被表示成定理形式：
设 \((a,b,c)\) 为本原勾股数，由引理1，不妨设 \(a\) 为奇数，\(b\) 为偶数，\(c\) 为奇数。
设 \(b=2k\)，则：
\[\begin{aligned} a^2+(2k)^2&=c^2\\ 4k^2&=(c+a)(c-a) \end{aligned} \]注意到 \(c+a,c-a\) 均为偶数，于是得到：
\[k^2=\frac{c+a}{2}\cdot \frac{c-a}{2} \]考虑 \(\gcd(\frac{c+a}{2},\frac{c-a}{2})\)：
\[\gcd(\frac{c+a}{2},\frac{c-a}{2})=\gcd(\frac{c+a}{2},a)\leq \gcd(c+a,a)=\gcd(c,a)=1 \]于是 \(\gcd(\frac{c+a}{2},\frac{c-a}{2})=1\)，那么 \(\frac{c+a}{2},\frac{c-a}{2}\) 应该各自都是平方数。
接下来令 \(m=\sqrt{\frac{c+a}{2}},n=\sqrt{\frac{c-a}{2}}\) 即可。
再证明任意满足定理形式的 \((a,b,c)\) 都是本原勾股数：
只需证明 \(\gcd(a,b,c)=1\) 即可。分别考虑 \(\gcd(a,b),\gcd(b,c),\gcd(a,c)\)：
\[\begin{aligned} \gcd(a,b)&=\gcd(m^2-n^2,2mn)\\ &=\gcd(m^2-n^2,mn)\\ &\leq \gcd(m^2-n^2,m)\gcd(m^2-n^2,n)=1\\ \gcd(b,c)&=\gcd(m^2+n^2,2mn)\\ &=\gcd(m^2+n^2,mn)\\ &\leq \gcd(m^2+n^2,m)\gcd(m^2+n^2,n)=1\\ \gcd(a,c)&=\gcd(m^2-n^2,m^2+n^2)\\ &=\gcd(2m^2,m^2+n^2)\\ &=\gcd(m^2,m^2+n^2)\\ &=\gcd(m^2,n^2)=1 \end{aligned} \]其中一些步骤中能把 \(\gcd(x,2y)\) 直接变成 \(\gcd(x,y)\) 的原因是 \(x,2y\) 奇偶性不同。
-
定理 2：\(a,b,c\) 均不超过 \(N\) 的本原勾股数的数量不超过 \(N\)。
证明： 考虑 \(c=m^2+n^2\leq N\) 的限制，那么本原勾股数数量的一个上界是：
\[\sum_{m=1}^{\sqrt N}\sqrt{N-m^2}< N \]
接下来不加证明的给出两个类似的定理，因为我也不会证。
-
定理 3：\(a,b,c\) 均不超过 \(N\) 的勾股数的数量为 \(O(N\log N)\)。
但实际上，通过程序暴力计算，发现当 \(N=10^9\) 时，勾股数的数量也只是 \(6N\) 左右，因为这玩意常数实在是太小了。
-
定理 4：\(a,b\) 均不超过 \(N\) 的勾股数的数量为 \(O(N\log N)\)。
这些结论可以应用于计算方程的解数。比如对于一个三元方程，若能通过换元把它化为 \(A^2+B^2=C^2\) 的形式，我们就能在较低的复杂度内找到方程的所有范围内的解。
标签：frac,gcd,定理,股数,本原,一些,aligned,性质 From： https://www.cnblogs.com/ez-lcw/p/16843070.html