Problem A. 876. (March 2024)
A. 876. Find all non-negative integers \(\displaystyle a\) and \(\displaystyle b\) satisfying \(\displaystyle 5^a+6=31^b\).
Proposed by Erik Füredi, Budapest
(7 pont)
Deadline expired on April 10, 2024.
With \(\displaystyle a=2, b=1\) we obtain a solution, we will prove that this is the only solution. First, we observe that \(\displaystyle a\) is even and \(\displaystyle b\equiv1\) (mod \(\displaystyle 5\)). Examining the equation modulo \(\displaystyle 3\), we have \(\displaystyle 5^a\equiv1\) (mod \(\displaystyle 3\)). The powers of \(\displaystyle 5\) alternate between leaving remainders \(\displaystyle 2\) and \(\displaystyle 1\) modulo \(\displaystyle 3\), which implies \(\displaystyle a\) is even.
There are no solutions for \(\displaystyle a<2\), so examining the equation modulo \(\displaystyle 25\), we get \(\displaystyle 31^b\equiv6\) (mod \(\displaystyle 25\)). The powers of \(\displaystyle 6\) alternate between \(\displaystyle 1\), \(\displaystyle 6\), \(\displaystyle 11\), \(\displaystyle 16\), \(\displaystyle 21\), and then \(\displaystyle 1\), ... modulo \(\displaystyle 25\). Therefore, \(\displaystyle b\equiv1\) (mod \(\displaystyle 5\)).
Examining the equation modulo \(\displaystyle 8\), as \(\displaystyle a\) is even, \(\displaystyle 5^a\) yields remainder \(\displaystyle 1\) when divided by \(\displaystyle 8\), since it is a power of \(\displaystyle 25\). Hence, \(\displaystyle 31^b\equiv6+5^a\equiv7\) (mod \(\displaystyle 8\)). Since \(\displaystyle 31^1\equiv7\) (mod \(\displaystyle 8\)) and \(\displaystyle 31^{2}\equiv1\) (mod \(\displaystyle 8\)), the odd powers of \(\displaystyle 31\) yield remainder \(\displaystyle 7\) when divided by \(\displaystyle 8\), implying \(\displaystyle b\) is odd.
For the case \(\displaystyle 2\geq{a}\), there is only the described solution to the equation \(\displaystyle 6+5^a=31^b\), hence we can assume \(\displaystyle a>2\). In this case, \(\displaystyle 5^a\) is divisible by \(\displaystyle 125\), so \(\displaystyle 31^b\equiv6\) (mod \(\displaystyle 125\)). The order of \(\displaystyle 31\) modulo \(\displaystyle 125\) is \(\displaystyle 25\) since \(\displaystyle 31^5\equiv26\) (mod \(\displaystyle 125\)) is not congruent to \(\displaystyle 1\), but \(\displaystyle 31^{25}\equiv26^5\equiv 1\) (mod \(\displaystyle 125\)). The powers of \(\displaystyle 31\) from \(\displaystyle 1\) to \(\displaystyle 25\) modulo \(\displaystyle 125\) are pairwise incongruent, and \(\displaystyle 31^{21}\equiv(31^5)^4\cdot31\equiv26^4\cdot31\equiv 6\). Therefore, the powers of \(\displaystyle 31\) giving \(\displaystyle 6\) modulo \(\displaystyle 125\) are exactly those which have exponent congruent to \(\displaystyle 21\) modulo 25.
Examining the equation modulo \(\displaystyle 101\), we know that \(\displaystyle b\equiv21\) (mod \(\displaystyle 25\)) and \(\displaystyle b\equiv1\) (mod \(\displaystyle 2\)), so \(\displaystyle b\equiv21\) (mod \(\displaystyle 50\)). Notice that \(\displaystyle 31^{50}\equiv1\) (mod \(\displaystyle 101\)), since \(\displaystyle 31\equiv1849\equiv43^2\) (mod \(\displaystyle 101\)), raising to the \(\displaystyle 50\)th power gives \(\displaystyle 31^{50}\equiv43^{100}\) (mod \(\displaystyle 101\)), hence, by Fermat's Little Theorem, it is congruent to \(\displaystyle 1\) modulo \(\displaystyle 101\). Thus, \(\displaystyle 31^b\equiv31^{21}\) (mod \(\displaystyle 101\)). The values of \(\displaystyle 31^2, 31^4, 31^8,\) and \(\displaystyle 31^{16}\) modulo \(\displaystyle 101\) can be calculated successively by squaring, and thus, we find \(\displaystyle 31^{21}\equiv 31^{16}\cdot 31^4\cdot31\equiv 79\). Therefore, \(\displaystyle 31^b\equiv79\) (mod \(\displaystyle 101\)).
From this, \(\displaystyle 5^a\equiv31^b-6\equiv73\) (mod \(\displaystyle 101\)). However, this is impossible, since none of the powers of \(\displaystyle 5\) are congruent to \(\displaystyle 73\) modulo \(\displaystyle 101\) as the powers of \(\displaystyle 5\) modulo \(\displaystyle 101\) are periodic, and a period is
\(\displaystyle 5,25,24,19,95,71,52,58,88,36,79,92,56,78,87,31,54,68,37,84,16,80,97,81,1.\)
This leads to a contradiction, concluding that the equation \(\displaystyle 6+5^a=31^b\) has only the solution \(\displaystyle a=2, b=1\) among non-negative integers.
Statistics:
13 students sent a solution. 7 points: Varga Boldizsár, Wiener Anna. 6 points: Bodor Mátyás. 3 points: 1 student. 2 points: 1 student. 1 point: 4 students. 0 point: 3 students. Not shown because of missing birth date or parental permission: 1 solutions.
Problems in Mathematics of KöMaL, March 2024