A Pythagorean triple is a set of integers a, b, and c such that
a^2 + b^2 = c^2
We want primitive triples, those where a, b and c do not have a common factor.
Euclid presents a formula for that: take any two integers n > m > 0, then
a = n^2 - m^2
c = n^2 + m^2
One more restriction: m and n must not have any common factor, they should be co-prime, otherwise the triple will not be primitive.
It is easy to show that when a, b, and c are found in this way, they satisfy the Pythagorean equation.
The trick is to see where this comes from, and more importantly, to show that it describes all such triples.
Derivation
I found a very nice derivation in Maor (The Pythagorean theorem). We start by investigating the properties of a, b and c.
For example a and b cannot both be even, for in that case, c will also be even, and then there is a common factor.
Recall that any even number can be written as 2k, and any odd number as 2k + 1 for positive integer k (or k = 0 for n = 1), so it is easy to see that if n is even, so is n^2. And if n is odd then so is n^2 as well. Therefore an even perfect square implies an even integer square root, and an odd square implies an odd root.
In the case where a and b are both odd, c must be even, since odd plus odd equals even. To see a problem with this re-write the equation
(2i + 1)^2 + (2j + 1)^2 = (2k)^2
The left-hand side is not a multiple of 4, but the right-hand side is. This is impossible. Hence one of a or b must be even and the other odd. Let a be odd. Then b can be written as b = 2t for some integer t. We have
(2t)^2 = c^2 - a^2 = (c + a)(c - a)
Every a, b and c must satisfy this equation. Furthermore, we see that there is a factor of 4 on the left-hand side, hence we can get a divisor of 2 for each factor on the right:
t^2 = (c + a)/2 . (c - a)/2
a and c are both odd:
c = 2k + 1
so their sum and difference are even, since
2k + 1 - 2i - 1 = 2(k - i)
After canceling the factor of 2 we get
(c - a)/2 = k - i
Thus both of these factors on the right-hand side are integers, while the left-hand side (t^2) is a perfect square.
Key step
Here's the last step. We claim that these two terms do not have a common factor.
Whenever x and y have a common factor, so do their sum and difference since x + y = fp + fq = f(p + q). and so on. The converse is also true.
But the sum and difference for these terms are:
(c + a)/2 - (c - a)/2 = a
On the supposition that (c+a)/2 and (c-a)/2 did have a common factor, then they would share that common factor with both c and a. Since we know that a and c (at least the particular ones we're interested in) do not have a common factor, neither do these two terms.
So the two terms have no common factor and yet multiply together to give a perfect square.
t cannot be prime itself (because there would not be two different factors).
So clearly there are two factors m^2 and n^2 (m and n not necessarily prime), and both terms are perfect squares! Write:
m^2 = (c - a)/2
n^2 - m^2 = a
And
mn = t
Since b^2 = 4t^2, b = 2t = 2mn.
These properties of m and n follow from the standard rules about factors, applied to a, b and c. Therefore, any triple a, b, and c can be written in terms of an integer m and n by this method.
I checked this by using a Python script to search the entire space of squares below an arbitrary limit, for those which sum to give another square, keeping only those triples of squares with no common factors.
I tested each triple by taking the even member, dividing by 2, and then finding its factors. This gives candidate pairs m and n with 2mn = b. Then, just check for whether n^2 - m^2 = a.
The gist is here.
It is interesting to see which patterns among the triples come from which choices of m and n.
