Primes Written as a Difference of Powers

As Finn already showed, all primes up to 37 work. It is left to prove that 41 doesn't work.

One very important number theory rule is: "If you can't do anything, take mod everything!" -Nathan Ramesh 2014

Applying that rule to this problem there are two cases:

• Case 1: $3^a-2^b=41$ .

It is clear that $a\ge 1$ , so we can safely say that $3^a\equiv 0\pmod{3}$ . From here we can take $\pmod{3}$ to get that $-2^b\equiv 41\equiv 2\pmod{3}\implies 2^b\equiv 1\pmod{3}$ . Checking values of $2^b\pmod{3}$ we see that $2^b\equiv 1\pmod{3}\iff b\equiv 0\pmod{2}$ . Thus we can set $b=2k\implies 2^b=2^{2k}=(2^k)^2$ . Let's leave this aside for now and go back to our original equation. It is clear that $b\ge 2$ , so we can safely say that $2^b\equiv 0\pmod{4}$ . From here we can take $\pmod{4}$ to get that $3^a\equiv 41\equiv 1\pmod{4}$ . Checking values of $3^a\pmod{4}$ we see that $3^a\equiv 1\pmod{4}\iff a\equiv 0\pmod{2}$ . Thus we can set $a=2j\implies 3^a=3^{2j}=(3^j)^2$ . Now we can see where we're getting. We have $(3^j)^2-(2^k)^2=41\implies (3^j-2^k)(3^j+2^k)=41$ . Clearly, since $41$ is prime and $3^j+2^k\not=1$ , we must have $3^j-2^k=1$ and $3^j+2^k=41$ . Adding these equations and dividing by $2$ gives $3^j=21$ which clearly isn't possible. Thus this case has no solutions. $\square$

• Case 2: $2^b-3^a=41$ .

It is clear that $a\ge 1$ , so we can safely say that $3^a\equiv 0\pmod{3}$ . From here we can take $\pmod{3}$ to get that $2^b\equiv 41\equiv 2\pmod{3}$ . Checking values of $2^b \pmod{3}$ we see that $2^b\equiv 2\pmod{3}\iff b\equiv 1\pmod{2}$ . This will be important later, so keep it in mind. It is clear that $b\ge 2$ , so we can safely say that $2^b\equiv 0\pmod{4}$ . From here we can take $\pmod{4}$ to get that $-3^a\equiv 41\equiv 1\pmod{4}\implies 3^a\equiv 3\pmod{4}$ . Checking values of $3^a\pmod{4}$ we see that $3^a\equiv 3\pmod{4}\iff a\equiv 1\pmod{2}$ . Since we still aren't done, let's try another mod. Let's try $8$ . We have $2^b-3^a\equiv 1\pmod{8}$ . Values of $2^b\pmod{8}$ are $1,2,4,0,0,0,\cdots$ . Values of $3^a\pmod{8}$ are $1,3,1,3,1,3,\cdots$ . However, since we know that $a\equiv 1\pmod{2}$ we must have $3^a\equiv 3\pmod{8}$ . Thus we now have $2^a-3\equiv 1\pmod{8}\implies 2^a\equiv 4\pmod{8}\implies a=2$ . However, $a=2$ won't work because we have $a\equiv 1\pmod{2}$ . Thus this case also has no solutions. $\square$

Since we have exhausted both cases, we are done (whew!) $\mathbb{Q}.\mathbb{E}.\mathbb{D}.$