Belarus — 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 \pmod{25}$ is $n = 20$, hence we have $x \equiv 20$.

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

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

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

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

Since $5^{12} - 1 = (5^6 - 1)(5^6 + 1)$, $5^6 + 1 \equiv 601 \pmod{601} = 5^4 - 5^2 + 1$, where 601 is a prime number, we have $5^y - 1 \equiv 601 \pmod{601}$ hence also $3^y - 1 \equiv 601 \pmod{601}$. Note that $\varphi(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 \pmod{601}$, and $x \equiv 25 \pmod{601}$.

We have $3^{120} - 1 \equiv 729^{20} - 1 \equiv 128^{20} - 1 \equiv 2^{140} - 1 \pmod{601}$.

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

Therefore $x \equiv 25 \pmod{601}$, so $x \equiv 100 \pmod{601}$.

Further, since $\varphi(125) = 100$, it follows that $3^x - 1 \equiv 125 \pmod{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.