Problem A. 841. (December 2022)
A. 841. Find all non-negative integer solutions of the equation \(\displaystyle 2^a+p^b=n^{p-1}\), where \(\displaystyle p\) is a prime number.
Proposed by Máté Weisz, Cambridge
(7 pont)
Deadline expired on January 10, 2023.
Case 1: \(\displaystyle p=2\)
If \(\displaystyle p=2\), then for every \(\displaystyle a,b\), \(\displaystyle n=2^a+2^b\) is a solution. From now on, we only consider the case \(\displaystyle p>2\).
Case 2: \(\displaystyle p>2, a=0\).
In this case, \(\displaystyle p^b+1=n^{p-1}\), so \(\displaystyle n^{p-1}-1=p^b\).
Since \(\displaystyle p-1\) is even, \(\displaystyle n^2-1|n^{p-1}-1\), so \(\displaystyle n^2-1=p^k\) and its value is not 1, therefore \(\displaystyle p|n^2-1\). In this case, by the LTE lemma,
\(\displaystyle b=v_p(n^{p-1}-1)=v_p(n^2-1)+v_p(\frac{p-1}{2})=v_p(n-1)=k\)
Thus \(\displaystyle n^2-1=p^k=p^b=n^{p-1}-1\), which means \(\displaystyle p-1=2\), so \(\displaystyle p=3\).
So \(\displaystyle 3^b=n^2-1=(n+1)(n-1)\), which means both \(\displaystyle n-1\) and \(\displaystyle n+1\) are powers of 3, but their difference is 2, which is only possible if \(\displaystyle n-1=1\) and \(\displaystyle n+1=3\), so \(\displaystyle n=2\) and \(\displaystyle b=1\).
Therefore, in this case, there is only one solution: \(\displaystyle a=0, b=1, p=3, n=2\).
Case 3: \(\displaystyle p>2, a>0\), \(\displaystyle b\) odd
Let \(\displaystyle p-1=2^l(2m+1)\) (where \(\displaystyle m \in \mathbb{N}\)). \(\displaystyle p\) is odd, so \(\displaystyle p-1\) is even, or \(\displaystyle l\geq 1\). \(\displaystyle p\) is odd and \(\displaystyle 2^a\) is even, so \(\displaystyle n\) is odd. By the LTE lemma,
\(\displaystyle v_2(n^{2^l(2m+1)}-1)=v_2(n-1)+v_2(n+1)+l-1\geq 3+l-1=l+2,\)
so
\(\displaystyle n^{2^l(2m+1)}\equiv1 \pmod {2^{l+2}}.\)
Therefore \(\displaystyle n^{p-1}\equiv1 \pmod {2^{l+2}}\). Thus it follows that \(\displaystyle n^{p-1}\equiv1\pmod {2^{l}}\) and \(\displaystyle n^{p-1}\equiv1\pmod {2^{l+1}}\) are also true, and \(\displaystyle p\equiv1\pmod {2^{l}}\), so
\(\displaystyle 2^a\equiv n^{p-1}-p^b\equiv 1-1 \equiv 0\pmod {2^{l}}.\)
This means \(\displaystyle 2^l|2^a\), so \(\displaystyle l\leq a\).
Now suppose \(\displaystyle b\) is odd. Then by the LTE lemma, \(\displaystyle v_2(p^b-1)=v_2(p-1)=l\) so \(\displaystyle p^b\equiv 2^l+1\pmod {2^{l+1}}.\) \(\displaystyle 2^a\equiv n^{p-1}-p^b\equiv1-(2^l+1)\equiv -2^l\pmod {2^{l+1}}.\) This means \(\displaystyle 2^a\) is not divisible by \(\displaystyle 2^{l+1}\), but we know \(\displaystyle l\leq a\), so \(\displaystyle l=a\).
Apply the Little Fermat theorem to the number \(\displaystyle n^{p-1}\). Since \(\displaystyle p\) is not a divisor of \(\displaystyle 2^a\), but it is a divisor of \(\displaystyle p^b\) as \(\displaystyle b\) is odd so \(\displaystyle b>0\), \(\displaystyle p\) cannot be a divisor of \(\displaystyle n^{p-1}\). Therefore \(\displaystyle n^{p-1}\equiv1\pmod p\). Thus necessarily \(\displaystyle 2^a\equiv 1\pmod p\). At the same time, \(\displaystyle 2^l<2^l(2m+1)+1=p\), so only \(\displaystyle 2^l=1\) is possible, so \(\displaystyle l=0\), which leads to a contradiction.
Case 4: \(\displaystyle p > 2, a > 0, b = 0\)
\(\displaystyle 2^a = (n^{\frac{p-1}{2}-1})(n^{\frac{p-1}{2}+1})\)
Therefore, both factors are powers of 2, which is only possible if one is 2 and the other is 4, i.e. \(\displaystyle n^{\frac{p-1}{2}} = 3\), so \(\displaystyle n = 3\) and \(\displaystyle p = 3\).
This is indeed a solution: \(\displaystyle 2^a = 3^2 - 3^0 = 8\), so \(\displaystyle a = 3\).
Case 5: \(\displaystyle p > 2, a > 0, b > 0\) and \(\displaystyle b\) is even
Let \(\displaystyle b = 2h\). Thus \(\displaystyle 2^a + p^{2h} = n^{p-1}\), i.e. \(\displaystyle 2^a = n^{p-1} - p^{2h}\). Using that \(\displaystyle p-1\) is even, we rearrange the right hand side to a product:
\(\displaystyle 2^a = \left( n^{\frac{p-1}{2}} + p^h\right)\left( n^{\frac{p-1}{2}} - p^h\right) \)
This is only possible if neither factor has any prime factor other than 2. That is,
\(\displaystyle n^{\frac{p-1}{2}} + p^h = 2^x, n^{\frac{p-1}{2}} - p^h = 2^y\)
for some \(\displaystyle x > y\) natural numbers. Subtracting the second equation from the first gives \(\displaystyle 2p^h = 2^x - 2^y\), which when divided by 2 gives
\(\displaystyle p^h = 2^{x-1} - 2^{y-1}\)
The left hand side is not divisible by 2, so neither is the right hand side, i.e. \(\displaystyle y = 1\).
Therefore
\(\displaystyle n^{\frac{p-1}{2}} - p^h = 2.\)
Since \(\displaystyle h > 0\), \(\displaystyle p | p^h\), so
\(\displaystyle n^{\frac{p-1}{2}} \equiv 2 \pmod p.\)
Squaring the congruence gives
\(\displaystyle n^{p-1} \equiv 4 \pmod p.\)
By Fermat's Little Theorem, \(\displaystyle n^{p-1} \equiv 1 \pmod p\), because \(\displaystyle n\) is not divisible by \(\displaystyle p\). Therefore \(\displaystyle 4 \equiv 1 \pmod p\), i.e. \(\displaystyle p = 3\).
Thus, our task is now to solve the equation \(\displaystyle 2^a+3^{2h}=n^2\). Since in this Case \(\displaystyle 5\), \(\displaystyle h>0\), we have \(\displaystyle 2^{a}\equiv n^2\equiv1 \pmod 3\). The powers of 2 with even exponents give a remainder of 1 when divided by 3, while the powers of 2 with odd exponents give a remainder of 2, so \(\displaystyle a\) must be even. Let \(\displaystyle a=2j\). Then we have \(\displaystyle 3^{2h}=n^2-2^{2j}\), or
\(\displaystyle 3^{2h}=\left( n+2^j\right) \left( n-2^j\right).\)
Both of these factors are powers of 3 with nonnegative integer exponents, but their difference is \(\displaystyle 2\cdot 2^j=2^{j+1}\), which is not divisible by 3. This is only possible if one of the factors is equal to 1, meaning \(\displaystyle n-2^j=1\). In this case, \(\displaystyle n+2^j=2^j+1+2^j=2^{j+1}+1\). Therefore, \(\displaystyle 3^{2h}=2^{j+1}+1\). Rearranging and turning it into a product, we have
\(\displaystyle \left( 3^h+1\right) \left( 3^h-1\right) =2^{j+1}.\)
Therefore, \(\displaystyle 3^h+1\) and \(\displaystyle 3^h-1\) are powers of 2 with nonnegative integer exponents, and their difference is 2, which is only possible if \(\displaystyle h=1\). In this case, \(\displaystyle j=2\), so \(\displaystyle a=2j=4\). Therefore, the original equation can be written as \(\displaystyle 2^4+3^2=n^2\). From here we can see that \(\displaystyle n=5\).
Thus, in this case the only solution is \(\displaystyle (a,b,p,n)=(4,2,3,5)\).
In summary, the solutions to the equation \(\displaystyle (a,b,p,n)\) are
\(\displaystyle (a,b,2,2^a+2^b),(0,1,3,2),(3,0,3,3),(4,2,3,5).\)
Statistics:
22 students sent a solution. 7 points: Bodor Mátyás, Lovas Márton, Móricz Benjámin, Németh Márton, Seres-Szabó Márton, Szakács Ábel, T.Tóth Patrik Tibor, Varga Boldizsár, Zömbik Barnabás. 6 points: Simon László Bence, Sztranyák Gabriella. 5 points: 1 student. 4 points: 4 students. 3 points: 2 students. 2 points: 1 student. 1 point: 2 students. 0 point: 1 student.
Problems in Mathematics of KöMaL, December 2022