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
- 1992: Hillel Gauchman and Ira Rosenholtz: Problem 1404 (Math. Mag. Vol. 65, no. 4: p. 265) www.jstor.org/stable/2691457
- 1993: Solution to Problem 1404 (Math. Mag. Vol. 66, no. 4: p. 269) www.jstor.org/stable/2690747
- but beware the typo: $31 = 2^4 - 3^0$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $41$