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\ $.
Best Answer
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.