There is another method that allows one to handle $a^{n}-b^{m}=k$ (here I call the bases $a$ and $b$ because primality is not important to how the method works). Specifically, if one has a solution, it allows a larger solution to be found, or proven to not exist.

As an example of this method, it is easy to outline a proof that $2^{n} - 5^{m} = 3$ has no solutions larger than $(m,n)=(3,7)$:

Suppose $m>3$, $n>7$, and $2^{n}-5^{m}=3$.

Rewrite the equation as $2^{n}=5^{m}+3$.

Now, to use the largest solution we know, subtract $2^{7}=5^{3}+3$ from both sides to obtain $2^{7}(2^{n-7}-1)=5^{3}(5^{m-3}-1)$.

Since $m$ and $n$ give a solution larger than the one we know, both sides are positive integers. Since $n>7$, the highest power of $2$ dividing the right side is $2^{7}$.

Since the order of $5$ in $(\mathbb{Z}/(128))^{\times}$ is $32$, we know that $32$ divides $m-3$, and $5^{32}-1$ divides both sides. Then $29423041$, as a prime factor of $5^{32}-1$, divides both sides. Then $29423041$ divides $2^{n-7}-1$, so since the order of $2$ in $(\mathbb{Z}/(29423041))^{\times}$ is $122596$, $2^{122596}-1$ divides both sides. (This is probably not a profitable direction to take, but it can work as an illustration of the method.)

The contradiction would be obtained by concluding that $5^{4}$ divides the right side, or $2^{8}$ divides the left side.

In the case where a larger solution exists, the ability to bounce back and forth between the two sides of the equation only goes as far as concluding that the larger solution (that is, the common value of both sides when the larger solution is plugged in) minus the common value from the known solution divides both sides.

3: to have a powerkof3as factor of $2^n-1$nmust have the form $x*\varphi(3^k)=x*2*3^{k-1}$ wherexis coprime to2and3. After that, the lhs has additional (prime-)factors due to the $\varphi$-function for nontrivialn>1except ifn=6; here we can use the szigmondy-theorem or a simple comparision of the growthrate of the lhs and rhs, if k>2. – Gottfried Helms Jul 1 '11 at 18:56