BMO1 B 2020 6

let a,b,c,d \in \mathbb{N}, so that we have

n=2^a+2^b=(2^c-1)+(2^d-1)=2^c+2^d-2 \\ \iff 2^{a-1}+2^{b-1}=2^{c-1}+2^{d-1}-1

where a\not=b,c\not=d as the powers/mersenne primes must be distinct.

claim 1: it is always the case that exactly one of a,b,c,d=1.
proof: split into cases, in terms of numbers of variables that equal 1.

  • if none equal to 1, ie. a,b,c,d>1:
    2^{a-1}+2^{b-1}\equiv 0\pmod 2
    2^{c-1}+2^{d-1}-1 \equiv 0+0-1 \equiv 1 \pmod 2.
    which is a contradiction.
  • if exactly 2 equal to 1, then we have WLOG a=c=1,b\geqslant d >1 (a=b,c=d cannot happen):
    2^{a-1}+2^{b-1}=1+2^{b-1}\equiv 1\pmod 2
    2^{c-1}+2^{d-1}-1 =1+2^{d-1}-1=2^{d-1}\equiv 0 \pmod 2.
    which is a contradiction.
  • if 3 or more are all equal to 1, then this would lead to at least one of a=b,c=d being true, which contradicts a\not=b,c\not=d.
  • the only remaining case is when exactly one of a,b,c,d=1. this reduces, WLOG, to 2 sub-cases.
    either a=1 and b,c,d>1, in which case
    2^{a-1}+2^{b-1}=1+2^{b-1}\equiv 1\pmod 2
    2^{c-1}+2^{d-1}-1\equiv0+0-1=-1\equiv 1 \pmod 2.
    or c=1 and a,b,d>1, in which case
    2^{a-1}+2^{b-1}\equiv 0\pmod 2
    2^{c-1}+2^{d-1}-1 =1+2^{d-1}-1=2^{d-1}\equiv 0 \pmod 2.

therefore claim 1 is proven.

notice that 2^1-1=1 which is not a prime, so we have that c,d\not=1 (c,d are the exponents of the power of 2 in the mersenne primes). from this we can say, WLOG, that b=1.

\therefore n=2^a+2=2^c+2^d-2

claim 2: all mersenne primes, apart from 2^{2(1)}-1=3 are of the form 2^{2k+1}-1, \ k\in \mathbb{N}.
proof: assume to the contrary; then \exists mersenne primes of the form 2^{2m}-1, \ m\in\mathbb{N}.
2^{2m}-1=(2^m+1)(2^m-1), and for m>1 we have 2^m+1 \geqslant 5, 2^m-1 \geqslant 3. this means that their product must always be composite, and so it isn’t prime. this contradicts the assumption, and so any mersenne primes must be as stated in the claim.

from this we get that c=2x+1,d=2y+1 or (WLOG) 2, where x,y \in \mathbb{N}, x\not=y. we now have:
EITHER

\begin{align} \therefore n=2^a+2&=2^{2x+1}+2^{2y+1}-2 \\\iff 2^a+2^2&=2^{2x+1}+2^{2y+1} \\\iff 2^{a-2}+1&= 2^{2x-1}+2^{2y-1} \end{align}

which clearly leads to a contradiction taking both sides modulo 2, unless a=2, which is not possible either as (WLOG) x> y \geqslant 1\iff 2^{2x-1}+2^{2y-1}\geqslant 10.
OR

\begin{align} n=2^a+2&=2^{2x+1}+2^{2}-2 \\\iff 2^a+2^2&=2^{2x+1}+2^{2} \\\iff a&= 2x+1 \end{align}

which must be the case. we now have

n=2^{2x+1}+2^1=(2^{2x+1}-1)+(2^2-1)

as the only possibility. as x varies, it only remains now to prove that this can always be written as the sum of 2 distinct squares.
first notice that 2^{2x+1}+2^1\equiv 2 \pmod4 as x \geqslant 1, so for it to equal a sum of squares, the squares must each be 1\pmod 4 (squares are only ever 0,1 \pmod 4, so this is the only possibility). this means that the integers being squared must each be odd, trivially. so we can now consider the equation, where p,q\in\mathbb{N_0} and p\not=q:

\begin{align} n=2^{2x+1}+2&=(2p+1)^2+(2q+1)^2 \\ &= 4p^2+4p+1+4q^2+4q+1 \\ &= 4(p^2+p+q^2+q)+2 \\\iff 2^{2x-1}&=p(p+1)+q(q+1) \end{align}

we must prove that, for each x \ \exists \ p, q such that the equation above is satisfied. consider p=2^{x-1}-1,q=2^{x-1}.

\begin{align} \implies p(p+1)+q(q+1)&=2^{x-1}(2^{x-1}-1)+2^{x-1}(2^{x-1}+1) \\ &= 2^{2(x-1)}-2^{x-1}+2^{2(x-1)}+2^{x-1} \\ &= 2^{2(x-1)-1} \\ &= 2^{2x-1} \ \blacksquare \end{align}

so we have proven that n can always be written as the sum of 2 distinct squares.

2 Likes

Have you ruled out whether any of the exponents are zero?

1 Like

it should be trivially impossible right? mersenne primes are 2^2-1=3 or greater, so c,d can’t be 0. that means 2^a+2^b\geqslant 10 so a=0,b=1 cannot be a solution. then just contradiction modulo 2 for the other a,b

1 Like

It is trivial but should be stated somewhere near the beginning for a full proof. This was a common oversight in solutions I read and meant at most 9 marks could be awarded for an otherwise perfect solution!

oh right ty, i should try and make my solutions more detailed in that case haha. often have trouble judging what is trivial enough to exclude, and vice versa, what do you think i could exclude from my original solution?