Finding all Pythagorean triples

This post mainly concerns the age old question of classifying all right-angled triangles with integer sides. In other words, we wish to find all integer solutions for the equation \[ X^2 + Y^2 = Z^2. \tag{1} \] An observant reader may have noticed that if $(X, Y, Z)$ is a solution, then so is $(kX, kY, kZ)$ for any integer $k$, and vice versa. This means that we can discard all common factors of $X, Y, Z$, and focus on solving $(1)$, with the added condition $\gcd(X, Y, Z) = 1$. Such solutions are called primitive solutions. You may remember a parameterized expression for these solutions, but do you know how to derive it? This is what we will be discussing here. There are multiple ways of arriving at the parametrization, but the one we'll use traverses the poetic bridge between numbers and geometry (the two divine deities of mathematics) with such ease, that it definitely makes it the best among them all.

Rational hunt

There is another simplification we can make: barring the trivial $(0, 0, 0)$ solution, we'll always have $Z \neq 0$. This allows us to divide equation $(1)$ by $Z^2$, set $x = X/Z$, $y = Y/Z$, and look at the equation \[ x^2 + y^2 = 1. \tag{1*} \] Now, we are looking for rational solutions $(x, y)$. Such solutions are called rational points on the unit circle.

Clearly, $(-1, 0)$ is such a point; where can we go from here? Suppose that $(u, v)$ is another rational point. Here's a neat trick: join these two points using a straight line. Its equation must be \[ y = \frac{v}{u + 1}(x + 1). \] This has slope $t = v / (u + 1)$, and intersects the $y$-axis at $(0, t)$. Specifically, the slope $t$ is rational (it is simple enough to check that $u + 1 \neq 0$). Crucially, the converse is true; given a rational slope $t$, one can draw a corresponding line through $(-1, 0)$, with equation \[ y = t(x + 1). \] Where does this intersect our unit circle? Plugging this into $(1*)$, we have \[ x^2 + t^2(x + 1)^2 = 1, \qquad x = -1,\;\frac{1 - t^2}{1 + t^2}. \] The new point obtained this way, \[ (x, y) = \left(\frac{1 - t^2}{1 + t^2}, \frac{2t}{1 + t^2}\right), \tag{2} \] is most definitely rational. Thus, by drawing all such lines with rational slope $t$, we can be sure that we have accounted for every rational point on our circle!

You can explore the the geometry of this construction using this Desmos animation.

Integer hunt

[This section will use very basic modular arithmetic. For those who aren't familiar, $a\equiv b\pmod m$ simply means "$a$ leaves a remainder $b$ when divided by $m$" or "$(a-b)$ is divisible by $m$". The only properties that we will be using are that congruences can be added and multiplied almost as if they were ordinary equations, and that square numbers are always either $0$ or $1$ modulo $4$. It may be a nice exercise to try and verify these properties.]

We're not quite done yet! Translating these rational solutions $(x, y)$ into primitive integer solutions $(X, Y, Z)$ requires a few more tricks. First we claim that $X, Y$ cannot both be even; if they were, then $X^2 + Y^2 = Z^2$ would be even, hence $Z$ would be even. This would violate $\gcd(X, Y, Z) = 1$. Next, we claim that both $X, Y$ cannot be odd; this uses the standard argument using remainders upon division by $4$. Note that if $X, Y$ are both odd, they can leave remainders $1, 3$ upon division by $4$; formally, $X, Y \equiv 1, 3 \pmod{4}$. Squaring, we have $X^2, Y^2 \equiv 1 \pmod{4}$, hence their sum $X^2 + Y^2 = Z^2 \equiv 2 \pmod{4}$. However, since $X, Y$ are both odd, $Z$ must be even, hence leave a remainder $0$ upon division by $4$ - a contradiction!

Thus, we can proceed by assuming that $X$ is odd, $Y$ is even. Given a rational point $(x, y)$ parameterized by $t$, write $t = m/n$ in lowest terms, i.e. $\gcd(m, n) = 1$. Plugging this into $(2)$, we have \[ x = \frac{X}{Z} = \frac{m^2 - n^2}{m^2 + n^2}, \qquad y = \frac{Y}{Z} = \frac{2mn}{m^2 + n^2}. \] Comparing the numerators and denominators, there must be some integer $k$ such that \[ kX = m^2 - n^2, \qquad kY = 2mn, \qquad kZ = m^2 + n^2. \] Note that $k$ cannot be on the other side, since $\gcd(X, Y, Z) = 1$! Now, $k$ divides both $m^2 - n^2$ and $m^2 + n^2$, hence divides both the sum and difference $2m^2$, $2n^2$. However $\gcd(m, n) = 1$ by choice, i.e. they share no common factors, hence $k$ cannot divide both $m^2, n^2$. This forces $k$ to divide $2$, narrowing things down to $k = 1, 2$. We can show that $k = 2$ fails, since $2X = m^2 - n^2$ gives $2 \equiv m^2 - n^2 \pmod{4}$ (recall that $X$ is odd) which is impossible from $m^2, n^2 \equiv 0, 1 \pmod{4}$.

This allows us to comfortably plug in $k = 1$, hence \[ (X, Y, Z) = (m^2 - n^2, 2mn, m^2 + n^2) \tag{*} \] for coprime $m, n$, one odd and the other even. These are the solutions with odd $X$, even $Y$; interchanging their roles gives the other half of the solutions, with even $X$, odd $Y$.

Rational points, lines, conics

With great power, comes great terminology! Here,

1. Rational points are those of the form $(p, q)$ with $p, q$ rational.
2. Rational lines are those of the form $ax + by + c = 0$ with $a, b, c$ rational.
3. Rational conics are those of the form $ax^2 + bxy + cy^2 + dx + fy + g = 0$ with $a, b, c, d, f, g$ rational.

Following are a couple of simple observations.

1. A line passing though two rational points is a rational line.
2. Two rational lines intersect at a rational point.

Here are a couple of simple exercises to ponder.

1. Try and find a non-rational line that passes through exactly one rational point, and a non-rational line that passes through no rational points.
2. Do two rational conics always intersect at rational points?

Generalization

The reader might have already noticed the crucial role our point $(-1,0)$ and line $y = t(x + 1)$ played in the method we exhibited. While such a line is typically easy to find, a smart choice of a 'starting point' is quite difficult: indeed, such a choice may not even exist! Without a smart choice, things can turn out to be really messy, as in this answer which tries to find rational points on the circle $x^2+y^2=10$.

Can you show that the circle $x^2 + y^2 = 3$ has no rational points whatsoever? A hint is to look at the corresponding integer equation, modulo $3$.

A more general question is to find out whether we have any rational point on a general rational conic. The theorem that governs this goes back to the genius of Legendre. His theorem states that the equation \[ aX^2 + bY^2 = cZ^2 \] has integer solutions if and only if there is an $m$ depending in a simple fashion on $a, b, c$, such that the congruence \[ aX^2 + bY^2 \equiv cZ^2 \pmod{m} \] has a solution in integers $X, Y, Z$ relatively prime to $m$. A proof of this, though worth sharing, is worthy of its own post.