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 N 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 N 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 N=5. 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 N 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 N 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 N=79 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 N = 559 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 N. I got interested in this problem because

  • I wondered how it was done.
  • I wanted to compute sides for N > 1000.
  • 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 N is congruent are not unique. For example, 6 is the area of a triangle with sides (3,4,5) and also (120/7, 7/10, 1201/70).

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 (120/7, 7/10, 1201/70) (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 D of the length of the hypotenuse \gamma against the area N. The plot is below. The vertical axis is \log_{10}D which is the number of base-10 digits in the denominator D. Note that prime values of N (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 N. In other words, the size of D is exponential in N.

congruent

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 N that can easily find the fractions for N=79, 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 N=79 would find the fractions \alpha = 335946000/2950969 and \beta = 233126551/167973000 by trying all \alpha = a/d with integers a, d having up to k=9 digits (and similarly for \beta). That is n^4 possibilities, where n = 10^k. 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 N=5,

    \[ \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 A and B that are Pythagorean, meaning A^2 + B^2 is a square. I’ll always assume that any factor common to all of A, B, C, and D has been removed, in other words that \gcd(A,B,C,D) = 1. Also note that if N is congruent, then multiplying the sides of its triangle by the integer k shows that k^2N is congruent. And conversely, if you have a triangle showing that k^2N is congruent, divide the sides by k to get a triangle for N. So I only need to consider square-free N.

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 (A, B, C) 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 P, Q. Specifically, starting with \alpha, \beta, \gamma you rewrite with a common denominator to get A, B, C and then use (2) to get P, Q. Conversely, given P and Q use (1) to compute A, B, C, and then get D 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 A/D to get \alpha = a/d, similarly for \beta = b/e.

This means that a brute-force search can be done using only two integers P and Q (with P > Q) instead of four integers a, b, d, and e. What is their size? If a, b etc. have k digits, then A, B etc. have 2k digits and P, Q have k 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 P and Q:

Rendered by QuickLaTeX.com

Note that P and Q 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 (A,B,C,D) then P and Q must be of opposite parity. This is the glitch in the web table I mentioned earlier. For N=559, the web table gives P=2608225, Q=4489, which are both odd. If you use them to generate (A,B,C,D) you will find they all have a common factor of 2. If you remove this factor and recompute P, Q you get P' = 1306357, Q'= 1301868 with P' < P.

A major improvement in exhaustive search can be made by noting the special form of P and Q. You can see the pattern in the following table of P and Q, where they are written in partially factored form.
Rendered by QuickLaTeX.com
For entries in the table, P is a square, or a square times a divisor of N, and similarly for Q. As N=30 shows, both P and Q can have divisors. Stated more formally, P = sP_0^2 and Q = tQ_0^2 where st|N. 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 P and Q. In other words, you only need to check n = 10^{k/2} values of P and similarly for Q, so exhaustive search takes n^2 = 10^k \approx 10^9 steps when N=79. 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 N=79 it can’t get the side lengths for more challenging areas such as N=157. In the next post I’ll explain an improved algorithm using elliptic curves and give code for the SageMath system that can solve N=157.

Powered by QuickLaTeX

Leave a Reply

Your email address will not be published. Required fields are marked *