Congruent Numbers Part I

Usually my posts have a connection to eBay, but this time I’m writing about a recreational math problem that caught my attention.

Introduction

One of the most famous facts of mathematics is that a triangle with sides of length 3, 4, and 5 is a right triangle, which means it can be drawn with a horizontal base and a vertical side, forming a right angle. Since the area of a triangle is one-half base times height, this triangle has area $\frac{1}{2}(3 \times 4) = 6$ .
right_triangle
Is there a right triangle with area 5? Of course there is, since a right triangle with a base of length 1 and height 10 has area 5. But the third side (the hypotenuse) has length $\sqrt{101}$ , which is not an integer.

That the side is ${\scriptstyle \sqrt{101}}$ follows from the famous Pythagorean theorem of high-school geometry, which says that if two sides of a right triangle have lengths ${\scriptstyle \alpha}$ and ${\scriptstyle \beta}$ , then the third side has length ${\scriptstyle \gamma}$ with ${\scriptstyle \gamma^2 = \alpha^2 + \beta^2}$ . So when ${\scriptstyle \alpha = 1}$ and ${\scriptstyle \beta = 10}$ , the third side has length ${\scriptstyle \gamma = \sqrt{101}}$ . The converse of the Pythagorean theorem is also true. It says that if ${\scriptstyle \gamma^2 = \alpha^2 + \beta^2}$ , then the triangle with side lengths = ${\scriptstyle \alpha, \beta, \gamma}$ is a right triangle. In particular, the triangle with sides of length 3, 4, and 5 is a right triangle since ${\scriptstyle 3^2 + 4^2 = 5^2 = 25}$ .

If you require all three sides of a triangle to be integers, then there is no right triangle with area 5. A brute-force enumeration verifies this, and easily shows that 6 is the smallest, and the next few after 6 that are the area of a right triangle are 24, 30, 54, 60. So asking if there is a right triangle with integer area appears to be of little interest. But what if you allow rational sides? It’s possible for the height and width to be non-integer fractions, but have integer area. And in fact there is such a triangle with area . The equation

$\left(\frac{3}{2}\right) ^2 + \left(\frac{20}{3}\right) ^2 = \left(\frac{41}{6}\right) ^2$

shows that a triangle with sides $\alpha = 3/2$ , $\beta = 20/3$ and $\gamma = 41/6$ is a right triangle. The area is $\frac{1}{2} \alpha \beta = 5$ .

An integer that is the area of a right triangle having all sides of rational length is called congruent. What numbers are congruent? Detecting them has something in common with detecting primes. There is a fast test to see if a number is prime or composite, but it’s a lot harder to obtain direct evidence that a number is composite by producing its factors. Similarly, there is a fast test to see if a number is congruent, but it is hard to find the side lengths $\alpha$ , $\beta$ , $\gamma$ that demonstrate directly that is congruent.

The analogy isn’t exact, because the direct test for congruent numbers isn’t guaranteed to work. More precisely, there is a proof that it works, but the proof depends on an unproven hypothesis called the Birch and Swinnerton-Dyer conjecture.

The reason it can be hard to find the sides is that they can be fractions with a lot of digits. For example, the sides of a right triangle with area are

$\left(\frac{335946000}{2950969}\right)^2 + \left(\frac{233126551}{167973000}\right)^2 = \left(\frac{56434050774922081}{495683115837000}\right)^2$

I found tables on several web sites containing the side lengths for all congruent numbers less than 1000, but I believe they are all copies of the same table, because they all have an identical glitch at which I will explain shortly.

The table appears on multiple web sites, but these variants are identical except for a misprint in the entry for ${\scriptstyle N=199}$ . It has the incorrect value ${\scriptstyle 27368486201}$ on all but the site http://bitman.name/math/table/29, which has the correct value ${\scriptstyle 2736848\underline{7}6201}$ . However, that site has a different misprint at ${\scriptstyle N=31}$ which says that ${\scriptstyle D=103020}$ but it should be ${\scriptstyle 103\underline{3}20}$ .

Why

In this posting and the next I will explain my efforts to compute the sides of a triangle with area . I got interested in this problem because

I wondered how it was done.
I wanted to compute sides for .
I wanted to check if the existing table can be improved.

I found the existing table can indeed be improved, as I now explain. The rational sides demonstrating that is congruent are not unique. For example, 6 is the area of a triangle with sides (3,4,5) and also .

Elliptic curve theory explains why there are infinitely many triangles for each area. It gives a formula that takes any set of sides and produces a new set of sides.

I’ll always try to find the example with the smallest denominators. So I prefer (3,4,5) (denominator of 1) to (denominator of 70).

After I wrote my own code to generate a table of side lengths, I discovered that the web table doesn’t always give sides with the smallest denominator. Two examples are below, where the triangle sides are $\alpha$ , $\beta$ , $\gamma$ .

Rendered by QuickLaTeX.com

Plot

How big (how many digits) are the numerator and denominator of the sides? I used the web table to plot the number of digits needed for the denominator of the length of the hypotenuse $\gamma$ against the area . The plot is below. The vertical axis is $\log_{10}D$ which is the number of base-10 digits in the denominator . Note that prime values of (blue) generally require more digits than composite numbers do.

The straight line suggests that the number of digits needed for the denominator increases linearly with . In other words, the size of is exponential in .

Elementary method of computing the triangles

In this section I explain in detail a search method for finding the sides for the triangle of area that can easily find the fractions for , which are

$\left(\frac{335946000}{2950969}\right)^2 + \left(\frac{233126551}{167973000}\right)^2 = \left(\frac{56434050774922081}{495683115837000}\right)^2$

A brute-force exhaustive search for would find the fractions $\alpha = 335946000/2950969$ and $\beta = 233126551/167973000$ by trying all $\alpha = a/d$ with integers , having up to digits (and similarly for $\beta$ ). That is possibilities, where . This search would take a long time, $n^4 = 10^{36}$ . There are some simple tricks that make it much faster to find the fraction by brute force.

Going back to sides for the congruent number ,

$\left(\frac{3}{2}\right) ^2 + \left(\frac{20}{3}\right) ^2 = \left(\frac{41}{6}\right) ^2$

Rewrite the equation to have a common denominator.

$\left(\frac{9}{6}\right) ^2 + \left(\frac{40}{6}\right) ^2 = \left(\frac{41}{6}\right) ^2$

The numerators satisfy

$\begin{eqnarray*} 9^2 + 40^2 & = & 41^2 \\ 81 + 1600 & = & 1681 \end{eqnarray*}$

A triple of such integers is called a pythagorean triple. This link between congruent numbers and Pythagorean triples holds in general, as summarized below:

Rendered by QuickLaTeX.com

So from rational numbers $\alpha$ , $\beta$ , and $\gamma$ you get integers and that are Pythagorean, meaning is a square. I’ll always assume that any factor common to all of , and has been removed, in other words that $\gcd(A,B,C,D) = 1$ . Also note that if is congruent, then multiplying the sides of its triangle by the integer shows that is congruent. And conversely, if you have a triangle showing that is congruent, divide the sides by to get a triangle for . So I only need to consider square-free .

Here are the first few square-free congruent numbers.

Rendered by QuickLaTeX.com

Note that in each case the denominator of $\gamma$ is the product of the denominators of $\alpha$ and $\beta$ . A proof that this is always so is in the final post of this three-part series.

Pythagorean triples can be written in 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*}$

The proof of this can be found on the web and in most number theory textbooks under the name Euclid’s Formula, but I also give a proof in the final post of this series. The formulas can be rewritten as

(2) $\begin{eqnarray*} P &=& \sqrt{\frac{C+B}{2}} \\ Q &=& \sqrt{\frac{C-B}{2}} \nonumber \\ \end{eqnarray*}$

So there is a 1-1 correspondence between $\alpha$ , $\beta$ , $\gamma$ and , . Specifically, starting with $\alpha$ , $\beta$ , $\gamma$ you rewrite with a common denominator to get , , and then use (2) to get , . Conversely, given and use (1) to compute , , , and then get using

(3) $\begin{equation*} % \frac{AB}{2D^2} = N \qquad D = \sqrt{\frac{AB}{2N}} = \sqrt{\frac{PQ(P^2 - Q^2)}{N}} \frac{AB}{2D^2} = N \qquad D = \sqrt{\frac{AB}{2N}} \end{equation*}$

Finally, reduce to get $\alpha = a/d$ , similarly for $\beta = b/e$ .

This means that a brute-force search can be done using only two integers and (with instead of four integers , , , and . What is their size? If etc. have digits, then etc. have digits and , have digits, so brute force is now $n^2 = 10^{2k} \approx 10^{18}$ . Huge but smaller than $10^{36}$ .

Here is a table of the first few square-free congruent numbers represented as and :

Rendered by QuickLaTeX.com

Note that and are always of opposite parity (that is, one is odd and the other even). As I’ll explain in the final post, once you remove any common factors from then and must be of opposite parity. 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 you will find they all have a common factor of 2. If you remove this factor and recompute , you get , with .

A major improvement in exhaustive search can be made by noting the special form of and . You can see the pattern in the following table of and , where they are written in partially factored form.
Rendered by QuickLaTeX.com
For entries in the table, is a square, or a square times a divisor of , and similarly for . As shows, both and can have divisors. Stated more formally, and where . Since this is true for all numbers in the table above, it’s plausible that it’s true in general, and I’ll show that in the final post.

This property means you only need to search up to the square root of and . In other words, you only need to check $n = 10^{k/2}$ values of and similarly for , so exhaustive search takes $n^2 = 10^k \approx 10^9$ steps when . This can be done in less than a minute, at least on my laptop.

I won’t bother to give the code, because although it easily computes the sides for it can’t get the side lengths for more challenging areas such as . In the next post I’ll explain an improved algorithm using elliptic curves and give code for the SageMath system that can solve .

Tag: Mathematics