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 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 or
, and getting 0, assumed the answer applied for
.
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 . If we let p, q, and c be the sides of the right triangle (with c as the hypotenuse), then the area is
.
Since , it follows that
. As c is a perfect square, we write c as
and since
, it also follows that
. This is what we shall now prove.
Lemma 1
For positive integers p, q, r where and
, then
.
From the Euclid theorem of Pythagorean triples, the sides of a primitive right triangle with sides a, b, and c can be represented as:
.. where and u and v are of opposite parity.
Thus by applying the theorem to our triple:
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:
Substituting for p, q, r:
Then,
.. 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
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 and 4 is already a factor of the expression, it follows that
.
Lemma 3
Proof of Lemma 3
Rewrite the expression as
.
If or
, then
.
If , then
.
The only other scenario is when , then either
and
or vice versa. Either way,
.
Lemma 4
If , then
.
Proof of Lemma 4
We construct a table. The first column of this table is while the second column is
:
1 1
2 4
3 2
4 2
5 4
6 1
The only possible values are 1, 2, and 4.
Lemma 5
If , then either
or
.
Proof of Lemma 5
Because ,
. Then, not counting reflective cases, there are three cases we need to consider:
Case 1: . Then
.
Case 2: . Then
.
Case 3: . Then
.
One of these (or their reflection) apply for whatever value of m and n.
Lemma 6
Proof of Lemma 6
Without loss of generality, rewrite the expression as a congruence mod 7, in terms of m. Since ,
The result follows.
Q.E.D.
wow nice
LikeLike