求不定方程 $5^m=3^n+2$ 的整数解.
不定方程 $5^m=3^n+2$ 仅有一个解 $(m,n)=(1,1)$.
详见 number theory - $5^m = 2 + 3^n$ help what to do - Mathematics Stack Exchange
Answer
问题及解答
1
首先 $(m,n)=(1,1)$ 是方程的一个解. 当 $m > 1$ 时, 必有 $n > 1$; 反之也是. 因此下设 $m,n$ 均大于 1.
（当然, 可以考虑 $m,n$ 更大的初始值. 若 $m=2$, 则 $3^n+2=5^2$, 无解. 因此 $m\geqslant 3$, 从而 $n\geqslant 3$.）
将原方程改写为
\[
\begin{split}
&5^m=3^n+5-3\\
\Rightarrow\ &5^m-5=3^n-3\\
\Rightarrow\ &5(5^{m-1}-1)=3(3^{n-1}-1),
\end{split}
\]
由于 $m\geqslant 3$, 故 $5^{m-1}-1\geqslant 24$, 类似的 $3^{n-1}-1\geqslant 8$. 因此, $3|(5^{m-1}-1)$, $5|(3^{n-1}-1)$.
另外, $3^2$ 不能整除 $(5^{m-1}-1)$, 否则推出 $3|(3^{n-1}-1)$, 这是不可能的. 同理 $5^2$ 不能整除 $(3^{n-1}-1)$.
若记 $a=m-1$, $b=n-1$, 则上面最后的式子可改写为
\[
\frac{5^a-1}{3}=\frac{3^b-1}{5}.
\]
并且注意左边不再含有因子 $3$, 右边不再含有因子 $5$.
Claim 1. 若 $a=2k+1$, 则 $3$ 不能整除 $(5^a-1)$.
这是因为
\[
\begin{aligned}
5\equiv 2\pmod 3 \\
5^2\equiv 1\pmod 3
\end{aligned}
\]
从而 $5^{2k+1}\equiv 2\pmod 3$.
Claim 2. $3|(5^{3k+1}-1)$ 当且仅当 $k$ 是奇数.
Pf. 若 $k=2s$, 则 $5^{3k+1}=5^{6s}\cdot 5$. 而
\[
5^6\equiv 2^6\equiv 1\pmod 3
\]
故 $5^{6s}\equiv 1\pmod 3$, 从而 $5^{6s+1}\equiv 2\pmod 3$, 这推出 $5^{6s+1}-1\equiv 1\pmod 3$.
若 $k=2s+1$, 则 $5^{3k+1}=5^{6s+4}$, 从而
\[
5^{6s+4}\equiv 5^4\equiv 2^4\equiv 1\pmod 3
\]
这推出 $3|(5^{6s+4}-1)$. 此外, 我们可以证明 $9$ 无法整除 $5^{6s+4}-1$. 因为
\[
5^{6s+4}-1=5^4\cdot 5^{6s}-1=(624+1)\cdot 5^{6s}-1=6\cdot 104\cdot 5^{6s}+(5^{6s}-1),
\]
故 $3||(5^{6s+4}-1)$.
类似地, 可证明
Claim 3. $3|(5^{3k+2}-1)$ 当且仅当 $k$ 是偶数. 并且当 $k$ 是偶数时, $(5^{3k+2}-1)$ 只有一个 $3$ 因子, 即无法被 $9$ 整除.
Claim 4. $3|(5^{3k}-1)$ 当且仅当 $k$ 是偶数. 并且当 $k=2s$ 时, 由于 $5^6-1=3^2\cdot 2^3\cdot 7\cdot 31$, 知 $(5^{6s}-1)$ 中含有的因子 $3$ 的个数等于 $3k$ 中所含因子 $3$ 的个数加 1.
记
\[
[a:p]=\begin{cases}
1, & \text{若}\ p|a,\\
0, & \text{否则}.
\end{cases}
\]
这里的 $[a:p]$ 称为 Iverson方括号(Iverson-bracket).
对于 $a$ 和 $p$, 记 $\{a,p\}$ 为 $p$ 在 $a$ 中的最高阶数. 这意味着, 若 $p^k||a$, 则 $\{a,p\}=k$. （这里 $p^k||a$ 指 $p^k$ 能整除 $a$, 但 $p^{k+1}$ 不能整除 $a$.）
上面这四个 Claim 说明, $3|(5^a-1)$ 当且仅当 $a$ 是偶数. 利用上面的记号, 我们还得到
\[
\{5^a-1,3\}=[a:2](1+\{a,3\}).
\]
类似可得
\[
\{3^b-1,5\}=[b:4](1+\{b,5\}.
\]
由于 $5^a-1$ 只含一个 $3$-因子, 故
\[
a\equiv \pm 2\pmod 6 .
\]
$3^b-1$ 中也只含一个 $5$-因子, 故
\[
b\equiv (4,8,12,16)\pmod {20} .
\]