大家好，最近在研究一个数论问题，想把我的思路整理出来，同时补上之前没解决的漏洞，问题如下：

给定正整数$a,b,n$，证明存在正整数$x$使得：
$$a^x + x \equiv b \pmod n$$

初始的强归纳思路 #

我最初尝试用强归纳法来证明：
假设对于所有小于$n$的正整数$k$，都存在正整数$x$满足$k \mid a^x + x - b$。

因为欧拉函数$\phi(n) < n$，根据归纳假设，必然存在某个正整数$m$，使得$\phi(n) \mid a^m + m - b$。我们可以把这个式子写成：
$$a^m + m - b = T\phi(n)$$
其中$T$是某个正整数。接下来构造一个新的整数：
$$M = tn\phi(n) - (T\phi(n) - m)$$
这里取$t$足够大，保证$M$是正整数。然后计算$a^M + M$模$n$的结果：
$$
\begin{align*}
a^M + M &\equiv a^{tn\phi(n)-(T\phi(n)-m)} + tn\phi(n)-(T\phi(n)-m) \pmod n \
&\equiv a^m + m - T\phi(n) \pmod n \quad (\text{这里用到了欧拉定理：}a^{\phi(n)} \equiv 1 \pmod n) \
&\equiv b \pmod n
\end{align*}
$$

这个思路看起来没问题，但有个致命漏洞：欧拉定理的应用前提是$a$和$n$互质，当$\gcd(a,n) > 1$时，这个推导就不成立了。我一直没能直接补上这个情况，但找到了当$a$是质数时的解决方案。

当$a$为质数时的补充证明 #

先证明一个关键的辅助结论，再完成整个证明：

辅助引理：解的无限性 #

如果存在某个正整数$x$满足$p^x + x \equiv b \pmod n$（$p$是质数），那么这样的$x$有无穷多个：

• 若$p \nmid n$：取$x_i = x + in\phi(n)$（$i$为正整数），代入验证：
  $$a^{x_i} + x_i = p^{x+in\phi(n)} + x + in\phi(n) \equiv p^x + x \equiv b \pmod n$$
  这是因为$p^{\phi(n)} \equiv 1 \pmod n$，所以$p^{in\phi(n)} \equiv 1^i \equiv 1 \pmod n$，同时$in\phi(n) \equiv 0 \pmod n$，显然成立。

• 若$p \mid n$：把$n$分解为$n = p^r s$，其中$\gcd(p,s)=1$。我们需要验证$p^{x_i} + x_i \equiv b \pmod{p^r s}$：
  首先证明$r \leq x$：假设$r > x$，那么$p^x \mid p^r s = n$，此时由$p^x + x \equiv b \pmod n$可得$p^x \mid x - b$，但$p^x > x$（因为$r > x \geq 1$，$p$是质数），这只有可能$x = b$且$n \mid p^x$，但这与$\gcd(p,s)=1$矛盾，所以$r \leq x$。

  此时$p^{x_i} = p^{x+in\phi(n)} \equiv p^x \pmod{p^r s}$等价于$p^{in\phi(n)} \equiv 1 \pmod{\frac{p^r s}{\gcd(p^r,px)}}$，因为$r \leq x$，$\gcd(p^r,px)=p^{r$，所以等价于$p}{in\phi(n)} \equiv 1 \pmod s$。而$s \mid n$，所以$\phi(s) \mid \phi(n)$，因此$p^{\phi(s)} \equiv 1 \pmod s$，进而$p^{in\phi(n)} = p^{in\phi(s)q} \equiv 1^{inq} \equiv 1 \pmod s$，显然成立。同时$x_i \equiv x \pmod n$，所以$p^{x_i} + x_i \equiv p^x + x \equiv b \pmod n$。

完成质数情形的证明 #

当$a=p$（质数）时：

• 若$p \nmid n$：直接用初始的强归纳思路即可，此时$\gcd(p,n)=1$，欧拉定理适用。
• 若$p \mid n$：还是分解$n=p^r s$，$\gcd(p,s)=1$。根据归纳假设，存在$m$使得$\phi(n) \mid p^m + m - b$，即$p^m + m - b = T\phi(n)$。利用辅助引理，我们可以取足够大的$m$（保证$r \leq m$），然后构造：
  $$M = \phi(n)(tn - T) + m$$
  取$t$足够大让$M$为正整数。计算模$n$的结果：
  $$
  \begin{align*}
  p^M + M &= p^{\phi(n)(tn-T)+m} + \phi(n)(tn-T) + m \
  &\equiv p^m + m \pmod n \quad (\text{因为}p^{\phi(n)(tn-T)} \equiv 1 \pmod s,\text{且}p^m \equiv p^M \pmod{p^r}) \
  &\equiv b + T\phi(n) \pmod n \
  &\equiv b \pmod n
  \end{align*}
  $$
  这样就完成了质数情形的证明。

备注：内容来源于stack exchange，提问作者PNT