Does every odd prime power divide a number of the form $\ n^{n-1}+n-1\ $?

Question

A conjecture motivated by a factoring project :

For every odd prime power $\ P\ $ , there is an integer $\ n>1\ $ such that $\ P\mid n^{n-1}+n-1\ $. In other words , every odd prime power divides some number of the form $n^{n-1}+n-1$.

Can we prove this conjecture ?

Every prime power $\ p^k\le 10^7 $ with an odd prime $p$ and an integer $\ k>1\ $ satisfies the conjecture which I found out with a brute force search. For the primes however, I only arrived at about $\ P=500\ 000\ $.

I noticed no nice pattern to find a suitable $\ n\ $quickly, so I need (in the case it is too hard to prove the conjecture) a more efficient method to find a suitable $\ n\ $ so that I can at least extend the search limit significantly.

The conjecture is false for arbitary odd numbers $\ P\ $. A counterexample is $\ 171\ $.

Answer 1

For $p$ an odd prime this is always true. Take $n$ such that $n\equiv 2\pmod{p-1}$ and $n\equiv\frac{p+1}{2}\pmod p$; this is always possible by the Chinese remainder theorem. Now we have $n-1\equiv 1\pmod{p-1}$, and so $n^{n-1}\equiv n\pmod p$ by Fermat's little theorem. So $n^{n-1}+n-1\equiv 2n-1\equiv p$.

For $P$ a nontrivial prime power this approach (via Euler-Fermat) doesn't work because $P$ and $\phi(P)$ are not coprime.

Answer 2

For the case of prime powers, I think we can use induction to find solutions $n$ that are congruent to $2$ mod $p-1$. Let $p$ be an odd prime number, $k \geq 1$, and let $n$ be a positive integer such that $p^k|n^{n-1}+n-1$ (so $n$ and $p$ are coprime) and such that $n=2$ mod $p-1$.

Now, write $m=n+sp^k$ for a positive integer $s$ divisible by $p-1$: then $C=m^{m-1}+m-1$ is congruent mod $p^{k+1}$ to $m^{n-1}+n+sp^k-1$, so $C$ is congruent to $n^{n-1}+(n-1)sp^kn^{n-2}+n+sp^k-1$ mod $p^{k+1}$.

Thus, if we write $n^{n-1}+n-1=tp^k$ for some integer $t$, $p^{k+1}|C$ iff $p^{k+1}|tp^k+(n-1)n^{n-2}sp^k+sp^k$ iff $p|t+(1+(n-1)n^{n-2})s$. If $1+(n-1)n^{n-2}$ is coprime to $p$, then we’re done. But $n-2$ can be chosen divisible by $p-1$ (by the accepted answer) so $1+(n-1)n^{n-2}$ is congruent to $n$ mod $p$ so is coprime to $p$.