That's a big number

My solution to this question was using a case bash.

Case 1: $n > 1$ is odd

We will show this has no solutions for the general case $x^n - y^n = 2^k$ , where $k$ is a non-negative integer. Assume such a solution exists, such that $k$ is minimal.

By parity, $x$ and $y$ are either both odd or both even. If they are both odd, we have

$(x-y)(x^{n-1} + x^{n-2} y + \ldots + y^{n-1}) = 2^k$

There are an odd number of odd terms in the second bracket so this is impossible. Therefore, $x$ and $y$ are both even. Let $x=2a$ and $y=2b$ . We have

$\begin{aligned} 2^n a^n - 2^n b^n &= 2^k\\ a^n - b^n &= 2^{k-n} \end{aligned}$

If $k-n>0$ , then this contradicts the minimality argument. If $k-n=0$ , we have $a^n - b^n = 1$ , which is impossible for odd $n>1$ . Therefore, there are no solutions.

Case 2: $n=2$

$\begin{aligned} x^2 - y^2 &= 2^{2016}\\ \implies (x+y)(x-y) &= 2^{2016}\\ \implies x+y &= 2^a\\ x-y &= 2^b\\ \implies x &= 2^{a-1} + 2^{b-1}\\ y &= 2^{a-1} - 2^{b-1}\\ \implies (a, b) &= (2015, 1), (2014, 2), \ldots, (1009, 1007) \end{aligned}$

Therefore, there are 1007 solutions in this case.

Case 3: $n=4$

$\begin{aligned} x^4 - y^4 &= 2^{2016}\\ y^4 + (2^{504})^4 &= x^4\\ \end{aligned}$

This has no solutions by Fermat's Last Theorem .

Case 4: $n>4$ , $n$ is even

We will show this has no solutions for the general case $x^n - y^n = 2^k$ , where $k$ is a non-negative integer. Assume such a solution exists, such that $n$ is minimal. Let $n=2m$ . We then have

$\begin{aligned} x^{2m} - y^{2m} &= 2^k\\ (x^m - y^m)(x^m + y^m) &= 2^k\\ \end{aligned}$

From this, we must have $x^m - y^m = 2^a$ , for a non-negative integer $a\leq k$ . Either $m$ is even and strictly greater than 4, $m=4$ (case 3) or $m$ is odd (case 1). Since there are no solutions in case 1 or 3, hence $m$ is even and strictly greater than 4. This creates a contradiction since we assumed $k$ to be minimal. Therefore, no solutions exist for $n$ even and $n>4$ .

---

Overall these cases, there is a total of 1007 solutions.