A solution to Project Euler problem 9 using only elementary algebra

Date written: 2021.07.28

Near the beginning of the year I started programming in (8-bit) Atmel AVR assembler. I used the problems on Project Euler as goals of things to program.

These problems are mathematics-oriented, and have very concrete goals. For example:

Problem 9: Find (the unique) positive integers $ a, b, c $ such that $a^2 + b^2 = c^2 $ and $ a + b + c = 1000 $.

Such a problem is trivial to solve in the vast majority of programming languages... but not the case in 8-bit assembler! For example, this .asm text file is my Atmel AVR assembler code for solving Problem 2, calculating the sum of even Fibonacci numbers below 8 million. If you browse the file, you will see that programming in Atmel AVR assembler is significantly more involved than programming in python!

Recently I looked at my code for Problem 9 — the second Project Euler question I had solved — and noticed that my code for it was quite long and most likely inefficient (it took 3,041,688 cycles to get the solution)! I tried redoing it using algebra to significantly simplify the calculation... and in the process of simplification the answer popped out!

Below I present how I solved this problem without needing to use a computer at all.

First, use the condition $ a + b + c = 1000 $ to reduce the two equations to the single equation $ a^2 + b^2 = (1000 - a - b)^2 $. Using high-school algebra, this simplifies to $$ \begin{equation} 1000(a + b - 500) = ab. \end{equation} $$

This already offers insight: the left hand side is even, so at least one of $a, b$ must be even too. But we can do much better: the left hand side is divisible by a power of 10, so surely at least one of $a ,b $ is divisible by 10 too?

If this was the case, we would effectively reduce the number of pairs $ a, b $ we need to check by an order of magnitude, which is a significant saving and so probably worth doing. We can try to prove at least one of the numbers is divisible by 10 by assuming the opposite and checking that the equation has no solutions in this case.

In particular, if neither $a $ nor $ b $ were divisible by 10, then one is a multiple of $ 5^3 = 125 $, by virtue of the left hand side being divisible by 125 and the Fundamental theorem of arithmetic. The assumptions of the problem imply $ 1 \lt a, b \lt 500 $. So let $ a $ is a multiple of 125. Then there are only three possible choices for $ a = 125n $, and it is elementary to check if these are solutions by hand:

Substituting $ a = 125 n $ into equation (1) and simplifying gives $$ b = \frac{1000(4-n)}{8-n}. $$ When $ n = 1,2,3 $, we get $ b = 3000/7, 2000/6, 1000/5 $. Surprisingly, the last of these is actually an integer! So $ n = 3 $ gives $ (a,b) = (375, 200)$... and hence $ (a,b,c) = (375, 200, 425) $. By construction this satisfies the conditions so we're done before we had program by hand in assembler!