Peter wrote: Prove that if $p$ is a prime, then $p^{p}-1$ has a prime factor that is congruent to $1$ modulo $p$. In fact, $p^{p-1}+p^{p-2}+...+p+1>1$. Thus, the number $p^{p-1}+p^{p-2}+...+p+1$ has a prime factor $q$. Then, since $p^p-1=\left(p-1\right)\left(p^{p-1}+p^{p-2}+...+p+1\right)$, we also have $q\mid p^p-1$, so that $p^p\equiv 1\text{ mod }q$. Hence, $p$ is divisible by $\text{ord}_q p$. Since $p$ is a prime, this yields that $\text{ord}_q p=1$ or $\text{ord}_q p=p$. If $\text{ord}_q p=1$, then $p\equiv 1\text{ mod }q$, and thus $p^{p-1}+p^{p-2}+...+p+1\equiv 1^{p-1}+1^{p-2}+...+1+1=p\equiv 1\text{ mod }q$, what contradicts $q\mid p^{p-1}+p^{p-2}+...+p+1$. Hence, $\text{ord}_q p=1$ is not possible, so we must have $\text{ord}_q p=p$. Since $\text{ord}_q p\mid q-1$ (because $q$ is a prime), this yields $p\mid q-1$, so that $q\equiv 1\mod p$. Since $q$ is prime and divides $p^p-1$, it thus follows that $q$ is a prime factor of $p^p-1$ which is congruent to $1$ modulo $p$, and we are done. darij

We can generalize this problem: $ p$ can be composite, too.

Yes, this follows from Zsigmondy's theorem. For those that don't like it in it's general form: just use the same proof