# litlocus 题解导出

导出时间：2026/10/22 02:35:10

---

## super ez problem series 3 T1

- 原题：GZA 提供的初等数论问题 I
- 作者：gza
- 审核时间：2026/10/21 15:02:55

问题: 求所有满足 $n^{p-1}\mid (p-1)^n+1$ 的正整数 $n$ 与素数 $p$ 组成的有序对 $(n,p)$?

记 $\operatorname{minp}(n)$ 为 $n$ 的最小素因子, $v_p$ 为 $p$ 进指数, $\operatorname{ord}_q(\cdot)$ 为模 $q$ 的阶.

当 $p=2$ 时, 条件化为 $n\mid 1^n+1=2$, 故 $n=1,2$.

当 $p$ 为奇素数时, $p-1$ 为偶数; 若 $n$ 为偶数, 则左边 $n^{p-1}$ 为偶数, 而右边 $(p-1)^n+1$ 为奇数, 矛盾, 所以 $n$ 为奇数.

若 $n=1$, 则对任意素数 $p$ 均有 $1^{p-1}\mid (p-1)+1$, 故得到一族解 $(1,p)$, 其中 $p$ 为任意素数.

下面讨论 $n>1$. 取 $q=\operatorname{minp}(n)$, 则 $q\mid (p-1)^n+1$, 即
$$
(p-1)^n\equiv -1\pmod q.
$$
又因 $q\nmid p-1$, 故 $p-1$ 模 $q$ 可逆, 从而
$$
\operatorname{ord}_q(p-1)\mid 2n,\qquad
\operatorname{ord}_q(p-1)\mid q-1.
$$
由于 $n$ 为奇数且 $q$ 是 $n$ 的最小素因子, 有 $\gcd(2n,q-1)=2$, 于是 $\operatorname{ord}_q(p-1)\mid 2$. 但 $(p-1)^n\equiv -1\not\equiv 1\pmod q$, 所以 $\operatorname{ord}_q(p-1)$ 只能为 $2$, 即 $p-1\equiv -1\pmod q$, 故 $q\mid p$. 又 $p,q$ 均为素数, 所以 $p=q$, 从而 $p\mid n$.

设 $t=v_p(n)$. 由 $n^{p-1}\mid (p-1)^n+1$ 得 $p^{t(p-1)}\mid (p-1)^n+1$. 应用 LTE, 有
$$
v_p\bigl((p-1)^n+1\bigr)=v_p(p)+v_p(n)=1+t.
$$
因此 $t(p-1)\le 1+t$, 即 $t(p-2)\le 1$. 易得只有 $t=1,\ p=3$.

于是 $n=3m$, 且 $\gcd(3,m)=1$. 此时原条件变为 $n^2\mid 2^n+1$. 若 $m=1$, 则 $n=3$, 确为解. 若 $m>1$, 取 $Q=\operatorname{minp}(m)$, 则 $2^n\equiv -1\pmod Q$. 设 $d=\operatorname{ord}_Q(2)$, 则 $d\mid 2n$ 且 $d\mid Q-1$. 由 $n$ 中小于 $Q$ 的质因子只有 $3$, 可得 $d=1$ 或 $3$; 简单计算可知 $m>1$ 不成立, 故 $m=1$, 即 $n=3$.

综上, 全部解为
$$
(1,p),\ (2,2),\ (3,3),
$$
其中第一族中的 $p$ 为任意素数.