BMO1 2020 Q6
Given that an integer \(n\) is the sum of two different powers of 2 and also the sum of two different Mersenne primes, prove that \(n\) is the sum of two different square numbers.
(A Mersenne prime is a prime number which is one less than a power of two.)
British Mathematical Olympiad Round 1 2020, Question 6. © UK Mathematics Trust. Original paper on ukmt.org.uk
Proposed by Luke Pebody
We begin by writing\[n = 2^a + 2^b - 2 = 2^c + 2^d\]where \(2^a - 1\) and \(2^b - 1\) are Mersenne primes and (without loss of generality) we have \(a > b\) and \(c > d\).
Since \(2^b - 1\) is prime, we must have \(a > b \ge 2\), so \(n = 2^a + 2^b - 2\) is divisible by 2 but not 4.
Since \(n = 2^c + 2^d\) with \(c > d\), we must have that \(d = 1\) and \(c \ge 2\).
Adding two to both sides of the original equation and dividing by 4 gives\[2^{a-2} + 2^{b-2} = 2^{c-2} + 1.\]The right-hand side is either 2 (if \(c = 2\)) or odd; in either case we must have \(b = 2\).
Returning to the original equation we have \(a = c\) and \(n = 2^a + 2\).
Now \(a\) must be odd, otherwise \(2^a - 1 = (2^{a/2} + 1)(2^{a/2} - 1)\), which is impossible since \(2^a - 1\) is prime and \(a \ge 3\). (Alternatively, if \(a\) were even, then \(2^a - 1\) would be divisible by 3, which is impossible since it is prime and \(a \ge 3\).)
To conclude, we write \(a = 2k + 1\), so that the identity \(n = 2^a + 2\) may be rewritten as\[n = (2^k + 1)^2 + (2^k - 1)^2.\]This exhibits \(n\) as the sum of two distinct squares.
Alternative
We begin by establishing that \(d = 1\) as in the first solution. We then argue directly that \(c\) must be odd. For, if \(c\) were even, then \(n = 2^c + 2\) would be divisible by 3. But all Mersenne primes other than 3 are one more than a multiple of 3, so there is no way to write a multiple of 3 as a sum of two distinct Mersenne primes.
We can then conclude as in the first solution since if \(c = 2k + 1\), then \(n = 2^{2k+1} + 2\) as before.
Alternative
Rewrite the equation as \(2^a + 2^b = 2^c + 2^d + 2\). Since \(2^b - 1\) is prime, \(b \ge 2\) so the left hand side is even, which implies \(d \ge 1\). However, the left hand side is a sum of exactly two distinct powers of 2, so by uniqueness of binary representation we have \(d = 1\). This gives \(2^a + 2^b = 2^c + 4\).
The left hand side is not a power of 2, so again by uniqueness of binary representation, \(b = 2\).
This shows that \(a = c\). Since \(2^a - 1\) is a Mersenne prime greater than three, and it is well known that Mersenne primes must be of the form \(2^p - 1\) where \(p\) is prime, we see that \(a\) is odd and can conclude as before.
Remark
The expression of \(2^{2k+1} + 2\) as a sum of squares can be found using Diophantus’ identity which states that \((a^2 + b^2)(c^2 + d^2) = (ab - cd)^2 + (ad + bc)^2\). Setting \(a = 2^k\) and \(b = c = d = 1\) gives the result needed for the question. Candidates familiar with complex numbers may recognise the original identity, which is equivalent to the fact that the modulus function is multiplicative.
Solution © UK Mathematics Trust, from the BMO1 2020 solutions.