Solve Euler Project #9 only mathematically - Pythagorean triplet

Question

The "Euler Project" problem 9 (https://projecteuler.net/problem=9) asks to solve:

$a^2$ + $b^2$ = $c^2$
a + b + c = 1000

I find answers solving it with brute-force and programmatically, but is there a way to solve the problem ONLY mathematically? Can someone help, please?

Problem as explained in Project Euler website:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Answer 1

Hint Euclid's parameterization of the Pythagorean triples (Elements, Book X, Proposition XXIX) is: $$a = k (m^2 - n^2), \qquad b = 2 k m n, \qquad c = k (m^2 + n^2),$$ where $m > n > 0$ and $m, n$ coprime and not both odd.

Substituting in our condition gives $$1000 = a + b + c = 2 k m (m + n),$$ and clearing the constant leaves $$\phantom{(\ast)} \qquad 500 = k m (m + n) . \qquad (\ast)$$ Now, notice that (1) $500 = 2^2 5^3$ has only two distinct prime factors, and (2) since $m$ and $n$ are coprime, so are $m$ and $m + n$.

So, one of $m, m + n$ must be one of $1, 2, 4$ (in fact one of $2, 4$, since $m > n > 0$ implies $m + n > m > 1$) and the other must be one of $1, 5, 25, 125$. Because $m + n > m$, we must have $m \in \{2, 4\}$, and so $m + n < 2 m \leq 8$. Thus, $m + n = 5$, and $2 m > m + n = 5$ implies $m \geq 3$, leaving $m = 4$ as the only possibility. So, $n = 1, k = 25$, and $$\color{#df0000}{\boxed{(a, b, c) = (375, 200, 425)}} .$$

Answer 2

It is known that all primitive Pythagorean triples (i.e with no common factors) is of the form $(m^2-n^2,2mn,m^2+n^2)$ for relatively prime $m$ and $n$ where one is even and the other is odd.

Based on that, you are looking for $m$ and $n$ such that $$(m^2-n^2)+2mn+(m^2+n^2)=2m^2+2mn=2m(m+n)$$ is a factor of $1000$.

Answer 3

The triplets are all of the form $a=u(n^2-m^2), b=2umn, c=u(n^2+m^2) $ with $n > m$ so $a+b+c =u(2n^2+2mn) =2un(n+m) $.

We must have $n > m$.

Therefore $500 =un(n+m) $.

If $500 = rst $ with $s < t$ then $u = r, n = s, n+m = t $ so $m = t-n =t-s $.

We must have $n > m$ so $s > t-s$ or $s < t < 2s$.

Playing around a bit,

$500 = 1*20*25$, so, swapping $m$ and $n$, $u = 1, m = 5, n=20 $ and the sides are $20^2-5^2 = 375 = 25\ 15, 2\ 20\ 5 = 200 = 25\ 8, 20^2+5^2 = 425 = 25\ 17 $.

Answer 4

Given perimeter: $\qquad P=(m^2-n^2 )+2mn+(m^2+n^2 )=2m^2+2mn\qquad $ If we solve for $n$, we can find if there exists one or more $m,n$ combinations for a Pythagorean triple with that perimeter. Any value of $m$ that yields an integer $n$ gives us such an $m,n$ combination. We let:

$$n=\frac{P-2m^2}{2m}\quad where \quad \biggl\lceil\frac{\sqrt{P}}{2}\biggr\rceil\le m \le \biggl\lfloor\sqrt{\frac{P}{2}}\biggr\rfloor$$ Here, the lower limit ensures that $m>n$ and the upper limit insures that $n>0$. For example:

$$P=1000\implies \biggl\lceil\frac{\sqrt{1000}}{2}\biggr\rceil =16\le m \le \biggl\lfloor\sqrt{\frac{1000}{2}}\biggr\rfloor=22$$

In this range, we find that only $20$ is a factor of $1000$ and the only value of $m$ that yields and integer $n$. We find that $m=20\implies n=5$, and, using Euclid's formula $F(m,n)$, we have $F(20,5)=(375,200,425)$. Then, the product, as I understand it, is $$A\times B\times C=375\times200\times425=31875000.$$

Answer 5

If the Pythagorean parameterization is a little advanced, be rest assured that it is unnecessary. One can simply rewrite the condition as: $$c = 1000 - a - b$$ And simply substitute into the Pythagorean Theorem as: $$a^2+b^2=(1000-a-b)^2 = 1,000,000 + a^2+b^2 - 2000a-2000b+2ab$$ We can easily rewrite this as: $$ab - 1000a-1000b + 500,000 = 0$$ Now we employ Simon's Favorite Factoring Trick to "factor" this as: $$(a-1000)(b-1000) = 500,000$$ Now both $a$ and $b$ are less than $1000$, so perhaps it would be better to have this written in the form: $$(1000-a)(1000-b) = 500,000$$ In other words, we are seeking two factors, both less than a thousand, that multiply to $500,000$.

There are many ways to finish, including some simple guess-and-checking. Fortunately, there is a relatively clean finish. One could potentially now observe that $500,000 \approx 490,000 = 700^2$, so perhaps our factors are around $700$. This is a decent ballpark to start with. Now, one could observe that our factors perhaps could have been $500$ and $1000$, but unfortunately one of these is not less than $1000$. We could instead say that our factors must be between $500$ and $1000$. If our factors were to be $F_1,F_2$, we can write: $$500 < F_1,F_2 < 1000$$ We now try to tighten this bound, keeping in mind that both factors must satisfy it. Firstly, we note that $500,000 = 2^5 \cdot 5^6$. It would be quite ridiculous if, say, $F_1$ were to have no factors of $5$, for then the maximum value it could have be would be $32$, which is for sure outside of these bounds. So for each of our factors, we can say that they contain a factor of 5. Donating our two factors of 5, we're left with $2^5 \cdot 5^4$, and they satisfy some new bounds: $$100 < \frac{F_1}{5},\frac{F_2}{5} < 200$$ Continuing, it would be equally ridiculous if $\frac{F_1}{5}$ had no factors of 5 either, since $32$ is still outside of these bounds. Donating an additional two factors of 5, we're left with $2^5 \cdot 5^2$ to work with, and the following bounds: $$20 < \frac{F_1}{5^2},\frac{F_2}{5^2} < 40$$ At this point, we can stop with the reduction, and see that by inspection, we have both $32$ and $25$ satisfying this inequality, and so $32*25 = 800$ and $25*25 = 625$ would be our factors. Some simple thought can tell us that really, this is the only solution that can satisfy these bounds. Namely, if within the last obtained inequality, we somehow found another two numbers that satisfied it that multiplied to $2^5 \cdot 5^2$, then surely one of these numbers would be a $10$. But $10$ does not satisfy the bounds, and multiplying it by either some 2s or 5s will jump over the whole interval $(20,40)$, so no such alternate solution can exist. Now, the rest of the problem is routine. We write: $$1000 - a = 800$$ $$1000 - b = 625$$ And so $a = 200$ and $b = 375$.