Congruent Numbers Part III

Before demonstrating the claims made in Part I and Part II on this topic, let me mention two simple facts about integer solutions to . First, if some number divides both and , it also clearly divides . So and have a common factor if and only if , , and do. Or saying it another way, and are relatively prime if and only if , , and are. From now on I always assume that this is true for , , and .

The second fact is that and have opposite parity, that is, one is even and the other odd. It’s clear that and can’t both be even, since then they would have a common factor of 2. To see that and can’t both be odd, note that the square of an odd number is so the square of an odd number is congruent to 1 modulo 4. This means that if and are both odd, the left side of is congruent to 2 modulo 4. But then the right-hand side is even, so is of the form and is congruent to 0 modulo 4, contradiction.

With these two facts out of the way, let me show that a Pythagorean triple is always of the form

(1) $\begin{eqnarray*} A &=& 2PQ \\ B &=& P^2 - Q^2 \qquad (\mbox{with } P > Q) \nonumber \\ C &=& P^2 + Q^2 \nonumber \end{eqnarray*}$

It is easy to check that if , and can be written this way in terms of and then . But where does the formula come from, and why are there always such and ?

A Pythagorean triple can be thought of as a point on a unit circle:

(2) $\begin{equation*}\arraycolsep=1.4pt \begin{array}{ccccc} A^2 & + & B^2 & = & C^2 \\ \displaystyle \left(\frac{A}{C}\right)^2 & + & \displaystyle \left( \frac{B}{C}\right)^2 &=& 1 \\ \rule{0pt}{15pt}x^2 & + & y^2 & = & 1 \end{array} \end{equation*}$

Each point corresponds to a single point on the -axis, as in the left half of the figure below. The slanted line connects to a point on the -axis.

The key fact is that each pair corresponds to a single number . And is rational if and only if is rational. This can be seen from explicit formulas linking and . To get those formulas consult the right half of the figure where the triangle with sides , is proportional to the triangle with sides . So

$\begin{eqnarray*} \frac{F}{E} & = & \frac{H}{G} \\ \frac{x}{1 - y} & = & z \\ z^2(1-y)^2 & = & x^2 = 1 - y^2 \\ z^2(1-y)(1-y) & = & (1-y)(1+y) \\ z^2(1-y) & = & 1+y \\ z^2 - 1 & = & (z^2 + 1)y \\ y & = & \frac{z^2 - 1}{z^2 + 1} \\ x & = & \frac{2z}{z^2 + 1} \end{eqnarray*}$

The second equation shows that if and are rational then so is . And the last two equations show the converse. But they show more. Writing in reduced form (i.e. and relatively prime) and combining with (2) shows

$\begin{eqnarray*} x = \frac{A}{C}& = & \frac{2z}{z^2+1} \; = \; \frac{2PQ}{P^2 + Q^2}\\ y = \frac{B}{C} & = & \frac{z^2-1}{z^2+1} \;=\; \frac{P^2 - Q^2}{P^2 + Q^2} \end{eqnarray*}$

Equating numerators suggests that and . But there is a subtlety: this is guaranteed only if and are relatively prime. For example , but there are no and with and . The small print below gives two ways to turn the suggestion into a proof.

Both ${\scriptstyle A/C}$ and ${\scriptstyle B/C}$ are in reduced form since ${\scriptstyle A}$ and ${\scriptstyle B}$ are relatively prime. Therefore, the equation above shows only that there is an integer ${\scriptstyle k}$ with
${\scriptstyle \mbox{ } kA = 2PQ \qquad kC = P^2 + Q^2 \qquad kB = P^2 - Q^2}$
So I need to show that ${\scriptstyle k=1}$ . First note that by adding and subtracting the last two equations, ${\scriptstyle k|2P^2}$ and ${\scriptstyle k|2Q^2}$ . Since ${\scriptstyle P/Q}$ is in lowest form, at least one is odd so ${\scriptstyle k}$ cannot be divisible by 4. Also, ${\scriptstyle k}$ cannot be divisible by an odd prime ${\scriptstyle p}$ , since that would then be a common factor of ${\scriptstyle P}$ and ${\scriptstyle Q}$ . So ${\scriptstyle k}$ is either 1 or 2. Suppose ${\scriptstyle k=2}$ . Since ${\scriptstyle A/C}$ , and ${\scriptstyle B/C}$ are reduced, they aren’t all even; and since ${\scriptstyle A^2 + B^2 = C^2}$ one of ${\scriptstyle A}$ and ${\scriptstyle B}$ is odd. The geometric construction works when you switch ${\scriptstyle x}$ and ${\scriptstyle y}$ , so I can assume that ${\scriptstyle B}$ is odd. Then ${\scriptstyle kB = 2B \equiv 2 \pmod 4}$ . If ${\scriptstyle P}$ and ${\scriptstyle Q}$ have the same parity, then ${\scriptstyle P^2 - Q^2 \equiv 0 \pmod 4}$ . So they must have opposite parities. But then ${\scriptstyle P^2 - Q^2}$ is odd and can’t equal ${\scriptstyle kB = 2B}$ , contradiction. Therefore ${\scriptstyle k=1}$ . Forcing ${\scriptstyle B}$ to be odd is crucial. If ${\scriptstyle B}$ is even, ${\scriptstyle k > 1}$ is possible. For example ${\scriptstyle B=4, A=3, C=5}$ has a solution ${\scriptstyle P=3}$ , ${\scriptstyle Q=1}$ , ${\scriptstyle k=2}$ .There’s also a fancy proof that uses unique factorization in the ring ${\scriptstyle \mathbb{Z}[i]}$ . Write ${\scriptstyle A^2 + B^2 = (A+iB)(A-iB) = C^2}$ . The two numbers ${\scriptstyle A \pm iB}$ are relatively prime (see below) so each prime factor of ${\scriptstyle C^2}$ divides only one of them. Therefore, each is a square and ${\scriptstyle A+iB = \epsilon(P+iQ)^2}$ where ${\scriptstyle \epsilon}$ is ${\scriptstyle \pm 1}$ or ${\scriptstyle \pm i}$ . So ${\scriptstyle A+iB = (P^2 - Q^2) + i2PQ}$ , possibly switching ${\scriptstyle A}$ and ${\scriptstyle B}.$

To see that the relative primality of ${\scriptstyle A}$ and ${\scriptstyle B}$ implies the relative primality ${\scriptstyle A \pm iB}$ , suppose that a complex integer ${\scriptstyle Z}$ divides both of ${\scriptstyle A \pm iB}$ . If ${\scriptstyle Z}$ is a real integer, then it divides both ${\scriptstyle A}$ and ${\scriptstyle B}$ , contradicting their relative primality. Similarly if ${\scriptstyle Z}$ is purely imaginary. That means I can assume that ${\scriptstyle Z \neq \overline{Z}}$ . By conjugating, it follows that ${\scriptstyle \overline{Z} | A \pm iB}$ and so both ${\scriptstyle Z}$ and ${\scriptstyle \overline{Z}}$ divide ${\scriptstyle A+iB}$ . Since these are distinct, the real integer ${\scriptstyle |Z|^2}$ divides ${\scriptstyle A+iB}$ which is again a contradiction. The final detail is that although ${\scriptstyle Z \neq \overline{Z}}$ , they could be associates, that is ${\scriptstyle Z = \pm iZ}$ . But that would imply ${\scriptstyle Z = K(1\pm i)}$ so ${\scriptstyle 1 \pm i | A + iB}$ which after taking norms becomes ${\scriptstyle 2 | A^2 + B^2}$ , and that contradicts the statement from the beginning of this post that ${\scriptstyle A}$ and ${\scriptstyle B}$ are of opposite parity.

Formula (1) gives an easy way to show why there isn’t a triangle with integer sides and area 5. If $\frac{1}{2}AB = N$ then that formula shows that there is a pair , with and

$PQ(P - Q)(P+Q) = N$

When this has no integer solution because three of the factors must be 1, the other 5. Since is the largest of the four factors, it would have to be 5 and , which is clearly impossible.

Since the numbers , , , and are used to compute the sides $\alpha = A/D$ , $\beta = B/D$ and $\gamma = C/D$ , you can remove any common factors if necessary since that won’t change the side lengths $\alpha$ , $\beta$ , $\gamma$ . So I will always assume that $\gcd(A,B,C,D) = 1$ , or using a common shorthand .

Proposition: If represents a square-free congruent triangle and , then .

Proof: By contradiction. Suppose . Then some prime divides . First suppose so but $2 \nmid D$ . Then , , and are integers so . It follows that one of or is even. This means that one of , is divisible by 4, the other by 2, so . Since $\frac{1}{2}(A/D)(B/D) = N$

$\frac{1}{2}AB = N D^2$

It follows that , but $2 \nmid D$ and is square free. This is a contradiction, so $2 \nmid (A,B,C)$ . Similarly, if is an odd prime, and divides , , and but not , then , contradiction. So . $\; {\rule{.6ex}{1.8ex}}$

I use this to give a shortcut in the exhaustive search over and . You only need to consider a subset. In the lemma below, the parity of is $N \pmod 2$ , i.e. odd or even.

Lemma: For a square-free congruent triangle, if then and , are of opposite parity. And such pair of generates a triangle with .

Proof:
First assume . If and have the same parity, then from equation (1) all of , and are even, contradicting the proposition. If and have a common factor, so do , and , so that is not possible either. For the other direction, note that since and have different parities, then is odd and is even so $2 \nmid (A,B, C)$ . Thus you only need to consider an odd prime . If then so so and similarly . $\; {\rule{.6ex}{1.8ex}}$

It follows that in exhaustive search, you only need to consider , that are relatively prime and of opposite parities. Note: this is the glitch in the web table I mentioned earlier. For , the web table gives , , which are both odd. If you use them to generate , remove the common factor of 2, and then recompute , you get , with .

Next, I’ll verify the important speedup, which is that and are almost squares.

Proposition: If , are relatively prime and generate a square-free congruent number, then and where (in particular, and ).

Proof: Combine equation (1) and $\frac{1}{2}\alpha \beta = \frac{1}{2}(A/D)(B/D) = N$ to get

$D^2N = \frac{1}{2}AB = \left(P^2 - Q^2\right) PQ \qquad (P,Q) = 1$

If a prime has then or . If the latter, but since , is impossible, and so is impossible so . Therefore every factor of is either a square or a factor of . It follows that where each factor of divides . If any factor of is a square then incorporate it into after which . Similarly . Since , so . $\; {\rule{.6ex}{1.8ex}}$

We observed earlier that in our tables, the denominator of $\alpha$ times the denominator of $\beta$ equals the denominator of $\gamma$ . Here is the proof that it is true in general. Repeating the equations:

$\alpha = \frac{a}{d} \qquad \beta = \frac{b}{d} \qquad \gamma = \frac{c}{d}$

$\begin{eqnarray*} \left(\frac{a}{d}\right) ^2 + \left(\frac{b}{e}\right) ^2 & = & \left(\frac{c}{f}\right) ^2 \\ \left(\frac{A}{D}\right) ^2 + \left(\frac{B}{D}\right) ^2 & = & \left(\frac{C}{D}\right) ^2 \end{eqnarray*}$

Even though , and can have a common factor in which case $a \neq A$ and $b \neq B$ .

Lemma: With the usual assumption that , then .

Proof: First check that so that . If not, then there is a with and . From and

(3) $\begin{equation*} AB = 2nD^2 \end{equation*}$

it follows that (or perhaps ). But and implies , contradiction. Next from (3) every prime factor of must divide either or . Start with and . Then consider the prime factors of one-by-one. For each factor , remove it from either the numerator and denominator of or from . After the removal process becomes and becomes and since and are completely reduced, , and so . Since each factor of was removed, so and thus $de \leq D$ . Finally, write

$\begin{eqnarray*} \frac{A^2}{D^2} + \frac{B^2}{D^2} & = & \frac{C^2}{D^2} \\ \frac{a^2}{d^2} + \frac{b^2}{e^2} & = & \frac{C^2}{D^2} \\ \frac{a^2e^2 + b^2d^2}{d^2e^2} & = & \frac{C^2}{D^2} \end{eqnarray*}$

The last equation shows that $de \geq D$ . If not, then it writes in a more reduced form, contradicting the first part of the proof. I previously showed $de \leq D$ so it follows that . And the first part of the proof showed that . $\; {\rule{.6ex}{1.8ex}}$

Tag: Mathematics