Selection and Training Session

(Solution of D. Babrou.) If $a\le 3$ or $b\le 2$, then we see that only the pairs $(a;b)=(1;0)$, $(a;b)=(3;2)$ satisfy the equation $3^a-5^b=2$.

Let now $a\ge 4$ and $b\ge 3$. We rewrite the equation in the form $3^3(3^{a-3}-1)=5^2(5^{b-2}-1)$. Setting $x=a-3$, $y=b-2$ ($x,y>0$) we obtain $3^3(3^x-1)=5^2(5^y-1)$.

It is easy to verify that the least possible $n$ with $3^n\equiv 1(\mathrm{mod}25)$ is $n=20$, hence we have $x\equiv 20$.

Similarly we conclude that $y\equiv 18(\mathrm{mod}15)$ because the least $n$ with $5^n\equiv 1(\mathrm{mod}27)$ is $n=18$. So, $5^y-1\equiv 19(\mathrm{mod}19)$.

Further, the smallest positive $x$ such that $3^x\equiv 1(\mathrm{mod}19)$ is 18, so $x\equiv 180(\mathrm{mod}100)$. Since $x\equiv 10(\mathrm{mod}10)$, we have $3^x-1\equiv 11(\mathrm{mod}11)$, then $5^y-1\equiv 11(\mathrm{mod}11)$.

The smallest positive $y$ such that $5^y-1\equiv 11(\mathrm{mod}5)$, hence $y\equiv 90\equiv 5\cdot 18$. Since $x\equiv 12(\mathrm{mod}12)$, we have $3^x-1\equiv 13(\mathrm{mod}13)$. Then $5^y-1\equiv 13(\mathrm{mod}13)$.

The order of 5 modulo 13 is 4, hence $y\equiv 4(\mathrm{mod}13)$, thus $y\equiv 180(\mathrm{mod}12)$. Then $y\equiv 12(\mathrm{mod}12)$.

Since $5^{12}-1=(5^6-1)(5^6+1)$, $5^6+1\equiv 601(\mathrm{mod}601)=5^4-5^2+1$, where 601 is a prime number, we have $5^y-1\equiv 601(\mathrm{mod}601)$ hence also $3^y-1\equiv 601(\mathrm{mod}601)$. Note that $\phi (601)=600=5^2\cdot 24$.

Let $\alpha$ be the order 3 modulo 601. If $\alpha \nmid 25$, then $\alpha$ is a divisor of 120 (since $600\nmid \alpha$). So if $3^{120}-1\nmid 601$, then $\alpha \equiv 25(\mathrm{mod}601)$, and $x\equiv 25(\mathrm{mod}601)$.

We have $3^{120}-1\equiv 729^{20}-1\equiv 128^{20}-1\equiv 2^{140}-1(\mathrm{mod}601)$.

If $2^{20}\not\equiv 1$, then $2^{140}\not\equiv 1(\mathrm{mod}601)$ since 7 is not a divisor of 600. Next $2^{20}=1024^2=423^2\not\equiv 1(\mathrm{mod}601)$, indeed.

Therefore $x\equiv 25(\mathrm{mod}601)$, so $x\equiv 100(\mathrm{mod}601)$.

Further, since $\phi (125)=100$, it follows that $3^x-1\equiv 125(\mathrm{mod}125)$, but if $y>0$, then $5^2(5^y-1)\nmid 125$. Thus $x=y=0$ contrary to $x,y>0$. Therefore the only pairs mentioned above are the solutions of given equation.