称一个正整数三元组 (a,b,c)(a,b,c)(a,b,c) 为一组本原勾股数，当且仅当其满足 a2+b2=c2a^2+b^2=c^2a2+b2=c2 且 gcd(a,b,c)=1\gcd(a,b,c)=1gcd(a,b,c)=1。
不是本原勾股数的勾股数被称作派生勾股数。
任意本原勾股数 (a,b,c)(a,b,c)(a,b,c) 的任意 kkk 倍对应着一组勾股数 (ka,kb,kc)(ka,kb,kc)(ka,kb,kc)。同时一组勾股数 (a,b,c)(a,b,c)(a,b,c) 唯一对应着一组本原勾股数，即 (agcd(a,b,c),bgcd(a,b,c),cgcd(a,b,c))(\frac{a}{\gcd(a,b,c)},\frac{b}{\gcd(a,b,c)},\frac{c}{\gcd(a,b,c)})(gcd(a,b,c)a,gcd(a,b,c)b,gcd(a,b,c)c)。
引理 1：若 (a,b,c)(a,b,c)(a,b,c) 为本原勾股数，则 a,ba,ba,b 奇偶性不同且 ccc 为奇数。
证明：若 a,ba,ba,b 奇偶性相同，则必有 a2+b2=c2a^2+b^2=c^2a2+b2=c2 为偶数，则 ccc 为偶数，c2c^2c2 为 444 的倍数。
若 a,ba,ba,b 均为偶数，则 2∣gcd(a,b,c)2|\gcd(a,b,c)2∣gcd(a,b,c)，矛盾。
若 a,ba,ba,b 均为奇数，注意到奇数的平方模 444 余 111，故 a2+b2≡2≢c2(mod4)a^2+b^2\equiv 2\not\equiv c^2\pmod 4a2+b2≡2≡c2(mod4)，矛盾。
引理 2：若 (a,b,c)(a,b,c)(a,b,c) 为本原勾股数，则 gcd(a,b)=gcd(a,c)=gcd(b,c)=1\gcd(a,b)=\gcd(a,c)=\gcd(b,c)=1gcd(a,b)=gcd(a,c)=gcd(b,c)=1。
证明：根据 a2+b2=c2a^2+b^2=c^2a2+b2=c2，若 a,b,ca,b,ca,b,c 中有二者是 kkk（k>1k>1k>1）的倍数，则剩下一者也会是 kkk 的倍数。
定理 1（欧几里得公式）：使用如下方法可以找出所有本原勾股数：
a=m2−n2b=2mnc=m2+n2
\begin{aligned}
a&=m^2-n^2\\
b&=2mn\\
c&=m^2+n^2
\end{aligned}
abc=m2−n2=2mn=m2+n2
其中 m>n≥1m>n\geq 1m>n≥1，m,nm,nm,n 互质且 m,nm,nm,n 奇偶性不同。
证明：
首先证明任意本原勾股数都能被表示成定理形式：
设 (a,b,c)(a,b,c)(a,b,c) 为本原勾股数，由引理1，不妨设 aaa 为奇数，bbb 为偶数，ccc 为奇数。
设 b=2kb=2kb=2k，则：
a2+(2k)2=c24k2=(c+a)(c−a)
\begin{aligned}
a^2+(2k)^2&=c^2\\
4k^2&=(c+a)(c-a)
\end{aligned}
a2+(2k)24k2=c2=(c+a)(c−a)
注意到 c+a,c−ac+a,c-ac+a,c−a 均为偶数，于是得到：
k2=c+a2⋅c−a2
k^2=\frac{c+a}{2}\cdot \frac{c-a}{2}
k2=2c+a⋅2c−a
考虑 gcd(c+a2,c−a2)\gcd(\frac{c+a}{2},\frac{c-a}{2})gcd(2c+a,2c−a)：
gcd(c+a2,c−a2)=gcd(c+a2,a)≤gcd(c+a,a)=gcd(c,a)=1
\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(2c+a,2c−a)=gcd(2c+a,a)≤gcd(c+a,a)=gcd(c,a)=1
于是 gcd(c+a2,c−a2)=1\gcd(\frac{c+a}{2},\frac{c-a}{2})=1gcd(2c+a,2c−a)=1，那么 c+a2,c−a2\frac{c+a}{2},\frac{c-a}{2}2c+a,2c−a 应该各自都是平方数。
接下来令 m=c+a2,n=c−a2m=\sqrt{\frac{c+a}{2}},n=\sqrt{\frac{c-a}{2}}m=2c+a,n=2c−a 即可。
再证明任意满足定理形式的 (a,b,c)(a,b,c)(a,b,c) 都是本原勾股数：
只需证明 gcd(a,b,c)=1\gcd(a,b,c)=1gcd(a,b,c)=1 即可。分别考虑 gcd(a,b),gcd(b,c),gcd(a,c)\gcd(a,b),\gcd(b,c),\gcd(a,c)gcd(a,b),gcd(b,c),gcd(a,c)：
gcd(a,b)=gcd(m2−n2,2mn)=gcd(m2−n2,mn)≤gcd(m2−n2,m)gcd(m2−n2,n)=1gcd(b,c)=gcd(m2+n2,2mn)=gcd(m2+n2,mn)≤gcd(m2+n2,m)gcd(m2+n2,n)=1gcd(a,c)=gcd(m2−n2,m2+n2)=gcd(2m2,m2+n2)=gcd(m2,m2+n2)=gcd(m2,n2)=1
\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(a,b)gcd(b,c)gcd(a,c)=gcd(m2−n2,2mn)=gcd(m2−n2,mn)≤gcd(m2−n2,m)gcd(m2−n2,n)=1=gcd(m2+n2,2mn)=gcd(m2+n2,mn)≤gcd(m2+n2,m)gcd(m2+n2,n)=1=gcd(m2−n2,m2+n2)=gcd(2m2,m2+n2)=gcd(m2,m2+n2)=gcd(m2,n2)=1
其中一些步骤中能把 gcd(x,2y)\gcd(x,2y)gcd(x,2y) 直接变成 gcd(x,y)\gcd(x,y)gcd(x,y) 的原因是 x,2yx,2yx,2y 奇偶性不同。
定理 2：a,b,ca,b,ca,b,c 均不超过 NNN 的本原勾股数的数量不超过 NNN。
证明： 考虑 c=m2+n2≤Nc=m^2+n^2\leq Nc=m2+n2≤N 的限制，那么本原勾股数数量的一个上界是：
∑m=1NN−m2 \sum_{m=1}^{\sqrt N}\sqrt{N-m^2}< N m=1∑NN−m2 接下来不加证明的给出两个类似的定理，因为我也不会证。 定理 3：a,b,ca,b,ca,b,c 均不超过 NNN 的勾股数的数量为 O(NlogN)O(N\log N)O(NlogN)。 但实际上，通过程序暴力计算，发现当 N=109N=10^9N=109 时，勾股数的数量也只是 6N6N6N 左右，因为这玩意常数实在是太小了。 定理 4：a,ba,ba,b 均不超过 NNN 的勾股数的数量为 O(NlogN)O(N\log N)O(NlogN)。 这些结论可以应用于计算方程的解数。比如对于一个三元方程，若能通过换元把它化为 A2+B2=C2A^2+B^2=C^2A2+B2=C2 的形式，我们就能在较低的复杂度内找到方程的所有范围内的解。