Naturals representable as differences of powers

Question

With paper-and-pencil method I found only a first $5$ cases:

$$1=3^2-2^3$$

$$2=3^3-5^2$$

$$3=2^7-5^3$$

$$4=5^3-11^2$$

$$5=2^5-3^3$$

This looks interesting and if a natural $n$ can be represented as difference of two powers (we do not take here $a^1$ into consideration but only exponents $\geq 2$ and we do not take into consideration powers $1^m$) we can call $n$ a power-representable natural number.

It is very reasonable to expect that some numbers can be represented in more than one way but I would like to know here is it known to be true and is it true a following statement:

Every natural number is power-representable.

Answer 1

Differences of squares are well understood.

If $$ n = a^2 - b^2 = (a-b)(a+b) $$ then $a-b$ and $a+b$ are either both even or both odd, so $n$ is either odd or a multiple of $4$.

Suppose $n$ is odd. Then each way to write $n = rs$ as a product of two (necessarily odd) factors with $r > s$ tells you $$ n = \left( \frac{r+ s}{2} \right)^2 - \left( \frac{r- s}{2} \right)^2 . $$

You can always take $r=n= 2k+1$ and $s=1$, to get the well known $$ 2k+1 = (k+1)^2 - k^2 . $$

If $n$ is prime that's the only way to write it as a difference of squares.

I leave it to you to find all the ways to write $105 = 3 \times 5 \times 7$.

Then you can work out the argument for the multiples of $4$.

Answer 2

A partial answer since as @Ethan points out, the problem is well-known and solved in general.

I'm going to write an integer of the form $4n$ as a difference of squares. A slightly more subtle argument works for $4n + 1$ and $4n + 3$.

Suppose that you look at an integer $k = 4n$, where $n$ is a positive integer. $k$ is not prime, for $k = 2(2n)$. If we write $$ a + b = 2n a - b = 2 $$ we have two equations in two unknowns; adding, we get $$ 2a = 2n + 2 $$ so $$ a = n + 1 $$ Similarly, $b = n-1$.

That gives us two integers, $a$ and $b$, with the property that $(a+b)(a-b) = 4n$. But $(a+b)(a-b) = a^2 - b^2$, so our number $k = 4n$ is a difference of squares.

As an example, look at $k = 4\cdot 5 = 20$, so $n = 5$. The formula above says to pick $a = 6$ and $b = 4$. We compute $$(a+b)(a-b) = 10 \cdot 2 = 20.$$ But this is the same as $$ a^2 - b^2 = 36 - 16 = 20 $$ so we've written $20$ as a difference of squares.