On some number-theoretic properties of right triangles (Project Euler 218)

The two hundred and eighteenth problem of Project Euler is quite interesting, but different. It resembles more closely a mathematics olympiad problem than a programming challenge. Its answer is somewhat surprising, too.

Original problem

The problem can be stated as follows:

A right triangle is considered perfect if (1): it is primitive (GCD of the three sides is 1) and (2): its hypotenuse is a perfect square.

A perfect triangle is considered superperfect if its area is divisible by the perfect numbers 6 and 28.

How many perfect triangles are there with hypotenuse below $10^{16}$ that are not also superperfect?

Answer

It turns out that every perfect triangle is also superperfect, meaning that for any limit there are no perfect triangles that are not superperfect.

Looking on the forums, it seems that a large group of solvers counted the triangles for a smaller limit, like $10^{9}$ or $10^{12}$ , and getting 0, assumed the answer applied for $10^{16}$ .

In this article I will attempt to prove, mathematically, that it is indeed impossible for a perfect triangle not to be superperfect.

Proof

Let’s rephrase this problem a bit: Prove that if a primitive right triangle has a hypotenuse that is a perfect square then its area must be a multiple of 6 and 28.

If the area is a multiple of 6 and 28, then it is a multiple of $\mathrm{LCM}(6,28) = 84$ . If we let p, q, and c be the sides of the right triangle (with c as the hypotenuse), then the area is $\frac{pq}{2}$ .

Since $84 | \frac{pq}{2}$ , it follows that $168 | pq$ . As c is a perfect square, we write c as $r^2$ and since $\mathrm{GCD}(p,q,c)=1$ , it also follows that $\mathrm{GCD}(p,q,r)=1$ . This is what we shall now prove.

Lemma 1

For positive integers p, q, r where $p^2 + q^2 = r^4$ and $\mathrm{GCD}(p,q,r)=1$ , then $168|pq$ .

From the Euclid theorem of Pythagorean triples, the sides of a primitive right triangle with sides a, b, and c can be represented as:

$a = u^2 - v^2$

$b = 2uv$

$c = u^2 + v^2$

.. where $u>v$ and u and v are of opposite parity.

Thus by applying the theorem to our triple:

$p = u^2 - v^2$

$q = 2uv$

$r^2 = u^2 + v^2$

Notice here that the third equation here itself represents a pythagorean triple. We then apply the same formula again, this time using m and n for the integers:

$u = m^2 - n^2$

$v = 2mn$

$r = m^2 + n^2$

Substituting for p, q, r:

$\begin{array}{rcl} p &=& u^2 - v^2 \\ &=& (m^2-n^2) - (2mn)^2 \\ &=& m^4 - 2m^2n^2 + n^4 - 4m^2n^2 \\&=& m^4 + n^4 - 6m^2 n^2 \\ \\ q &=& 2uv \\ &=& 2(m^2-n^2)(2mn) \\ &=& 4mn(m^2-n^2) \\ \\ r &=& m^2 + n^2 \end{array}$

Then,

$pq = 4mn(m^2-n^2)(m^4+n^4-6m^2n^2)$

.. which we will prove to be divisible by 168. Since 168=8*3*7, the expression must be proved to be divisible by 8, by 3, and by 7.

Lemma 2

$8 | 4mn(m^2-n^2)(m^4+n^4-6m^2n^2)$

Proof of Lemma 2

The proof is almost trivial. In order for the triple to primitive, m and n must be of opposite parity, meaning mn is even.

Because $2|mn$ and 4 is already a factor of the expression, it follows that $8|pq$ .

Lemma 3

$3 | mn(m^2-n^2)$

Proof of Lemma 3

Rewrite the expression as

$mn(m+n)(m-n)$ .

If $3|m$ or $3|n$ , then $3|mn$ .

If $m \equiv n \mod 3$ , then $m-n \equiv 0 \mod 3$ .

The only other scenario is when $m \not \equiv n \mod 3$ , then either $m \equiv 1 \mod 3$ and $n \equiv 2 \mod 3$ or vice versa. Either way, $m+n \equiv 0 \mod 3$ .

Lemma 4

If $7 \nmid m$ , then $m^2 \equiv 1,2,4 \mod 7$ .

Proof of Lemma 4

We construct a table. The first column of this table is $m \mod 7$ while the second column is $m^2 \mod 7$ :
1 1 2 4 3 2 4 2 5 4 6 1
The only possible values are 1, 2, and 4.

Lemma 5

If $7 \nmid m^2 - n^2$ , then either $m^2 \equiv 2n^2 \mod 7$ or $n^2 \equiv 2m^2 \mod 7$ .

Proof of Lemma 5

Because $7 \nmid m^2 - n^2$ , $m^2 \not\equiv n^2 \mod 7$ . Then, not counting reflective cases, there are three cases we need to consider:

Case 1: $m^2 \equiv 1, n^2 \equiv 2$ . Then $n^2 \equiv 2m^2 \mod 7$ .

Case 2: $m^2 \equiv 1, n^2 \equiv 4$ . Then $m^2 \equiv 2n^2 \mod 7$ .

Case 3: $m^2 \equiv 2, n^2 \equiv 4$ . Then $n^2 \equiv 2m^2 \mod 7$ .

One of these (or their reflection) apply for whatever value of m and n.

Lemma 6

$7 | m^4 + n^4 - 6m^2n^2$

Proof of Lemma 6

Without loss of generality, rewrite the expression as a congruence mod 7, in terms of m. Since $m^2 \equiv 2n^2 \mod 7$ ,

$\begin{array}{rcl} m^4 + n^4 - 6m^2n^2 &=& m^4 + (2m^2)^2 - 6m^2(2m^2) \\ &=& m^4 + 4m^4 - 12m^4 \\ &=& -7m^4 \end{array}$

The result follows.

Q.E.D.

Lucky's Notes

Notes on math, coding, and other stuff

On some number-theoretic properties of right triangles (Project Euler 218)

Original problem

Answer

Proof

Lemma 1

Lemma 2

Proof of Lemma 2

Lemma 3

Proof of Lemma 3

Lemma 4

Proof of Lemma 4

Lemma 5

Proof of Lemma 5

Lemma 6

Proof of Lemma 6

Leave a Reply Cancel reply

Original problem

Answer

Proof

Lemma 1

Lemma 2

Proof of Lemma 2

Lemma 3

Proof of Lemma 3

Lemma 4

Proof of Lemma 4

Lemma 5

Proof of Lemma 5

Lemma 6

Proof of Lemma 6

Share this:

Like this:

Related

Leave a Reply Cancel reply