Maths Olympiad Prep

Library / /55 of 105

Number theory Difficulty 4.9 AIME Prove it United States

Problem:

Do there exist three different prime numbers such that the sum of any two of them is a square?

Solution

Solution:

The answer is no. We work modulo 44 (i.e., we look at remainders on division by 44). Note that any square is 0\equiv 0 or 1mod41 \bmod 4. Indeed, if n=2kn=2k is even, n2=4k20n^{2}=4k^{2} \equiv 0, while if n=2k+1n=2k+1 is odd, n2=4k2+4k+11n^{2}=4k^{2}+4k+1 \equiv 1.

Now suppose some three such primes exist. If they are all odd, then each of them is 1\equiv 1 or 3(mod4)3 \pmod{4}; some two must then have the same value modulo 44 (both 11 or both 33), and then their sum is 2(mod4)\equiv 2 \pmod{4}, so it cannot be a square.

Thus, the primes are not all odd, so one of them is 22. Since they are all different, the other two are odd. If these two are both 3\equiv 3, then again their sum is 2\equiv 2 and cannot be a square. So one of them is 1\equiv 1, but then this prime plus 22 is congruent to 33, so that sum cannot be a square. So, once again, we can find two of the three primes whose sum is not a square.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.