# Smallest Prime Number not Difference between Power of 2 and Power of 3

## Theorem

$41$ is the smallest prime number which is not the difference between a power of $2$ and a power of $3$.

## Proof

First we have:

 $\ds 2$ $=$ $\ds 3^1 - 2^0$ $\ds 3$ $=$ $\ds 2^2 - 3^0$ $\ds 5$ $=$ $\ds 3^2 - 2^2$ $\ds 7$ $=$ $\ds 3^2 - 2^1$ $\ds 11$ $=$ $\ds 3^3 - 2^4$ $\ds 13$ $=$ $\ds 2^4 - 3^1$ $\ds 17$ $=$ $\ds 3^4 - 2^6$ $\ds 19$ $=$ $\ds 3^3 - 2^3$ $\ds 23$ $=$ $\ds 3^3 - 2^2$ $\ds 29$ $=$ $\ds 2^5 - 3^1$ $\ds 31$ $=$ $\ds 2^5 - 3^0$ $\ds 37$ $=$ $\ds 2^6 - 3^3$

Aiming for a contradiction, suppose $41 = 2^n - 3^m$.

We have that $n > 3$.

Thus:

$2^n \equiv 0 \pmod 8$

and as:

$41 \equiv 1 \pmod 8$

we have:

$1 \equiv -3^m \pmod 8$

which is not possible:

For any integer $k$,

 $\ds -3^{2 k}$ $=$ $\ds -9^k$ $\ds$ $\equiv$ $\ds -1^k$ $\ds \pmod 8$ Congruence of Powers $\ds$ $\equiv$ $\ds -1$ $\ds \pmod 8$ $\ds -3^{2 k + 1}$ $=$ $\ds 3 \paren {-3^{2 k} }$ $\ds$ $\equiv$ $\ds 3 \paren {-1}$ $\ds \pmod 8$ Modulo Multiplication is Well-Defined $\ds$ $\equiv$ $\ds -3$ $\ds \pmod 8$

So for any integer $m$, $1 \not \equiv -3^m \pmod 8$.

Now suppose $41 = 3^m - 2^n$.

We have that $m > 1$ and $n > 2$.

Taking $\mod 3$ on both sides:

 $\ds 41$ $=$ $\ds 3^m - 2^n$ $\ds \leadsto \ \$ $\ds -1$ $\equiv$ $\ds - 2^n$ $\ds \pmod 3$ $\ds \leadsto \ \$ $\ds 1$ $\equiv$ $\ds 2^n$ $\ds \pmod 3$ $\ds$ $\equiv$ $\ds \paren {-1}^n$ $\ds \pmod 3$ Congruence of Powers

which shows that $n$ is even.

Taking $\mod 4$ on both sides:

 $\ds 41$ $=$ $\ds 3^m - 2^n$ $\ds \leadsto \ \$ $\ds 1$ $\equiv$ $\ds 3^m$ $\ds \pmod 4$ $\ds$ $\equiv$ $\ds \paren {-1}^m$ $\ds \pmod 4$ Congruence of Powers

which shows that $m$ is even as well.

Now we take $\mod 5$ on both sides:

 $\ds 41$ $=$ $\ds 3^m - 2^n$ $\ds \leadsto \ \$ $\ds 1$ $\equiv$ $\ds 3^m - 2^n$ $\ds \pmod 5$ $\ds$ $\equiv$ $\ds 9^{m / 2} - 4^{n / 2}$ $\ds \pmod 5$ $\ds$ $\equiv$ $\ds \paren {-1}^{m / 2} - \paren {-1}^{n / 2}$ $\ds \pmod 5$ Congruence of Powers

But $\paren {-1}^{m / 2} - \paren {-1}^{n / 2}$ can only be $0$ or $\pm 2$, not $1$, which is a contradiction.

Therefore $41$ is not the difference between a power of $2$ and a power of $3$.

$\blacksquare$

## Sources

but beware the typo: $31 = 2^4 - 3^0$