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.
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 .
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 , which is not an integer.
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
shows that a triangle with sides , and is a right triangle. The area is .
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 , , that demonstrate directly that is congruent.
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
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.
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 .
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 , , .
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 against the area . The plot is below. The vertical axis is 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
A brute-force exhaustive search for would find the fractions and by trying all with integers , having up to digits (and similarly for ). That is possibilities, where . This search would take a long time, . 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 ,
Rewrite the equation to have a common denominator.
The numerators satisfy
A triple of such integers is called a pythagorean triple. This link between congruent numbers and Pythagorean triples holds in general, as summarized below:
So from rational numbers , , and 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 . 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.
Note that in each case the denominator of is the product of the denominators of and . A proof that this is always so is in the final post of this three-part series.
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
So there is a 1-1 correspondence between , , and , . Specifically, starting with , , 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
Finally, reduce to get , similarly for .
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 . Huge but smaller than .
Here is a table of the first few square-free congruent numbers represented as and :
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.
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 values of and similarly for , so exhaustive search takes 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 .
Powered by QuickLaTeX