super ez problem series 3 T1

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

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

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

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

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

下面讨论 $n>1$. 取 $q=\operatorname{minp}(n)$, 则 $q\mid (p-1)^n+1$, 即

又因 $q\nmid p-1$, 故 $p-1$ 模 $q$ 可逆, 从而

由于 $n$ 为奇数且 $q$ 是 $n$ 的最小素因子, 有 $\gcd(2n,q-1)=2$, 于是 . 但 , 所以 只能为 , 即 , 故 . 又 均为素数, 所以 , 从而 .

设 $t=v_p(n)$. 由 $n^{p-1}\mid (p-1)^n+1$ 得 . 应用 LTE, 有

因此 $t(p-1)\le 1+t$, 即 $t(p-2)\le 1$. 易得只有 $$.

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

综上, 全部解为

其中第一族中的 $p$ 为任意素数.