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

From ProofWiki
Jump to navigation Jump to search

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$