# $p^p - 1$ has a prime factor of the form $lp+1$

Prove that if $$p$$ is a prime $$p^p - 1$$ has a prime factor $$\equiv1(\mod p)$$. My approach was to write the congruence $$p^p\equiv 1\pmod q(1)$$ for some prime factor of $$p^p-1$$ $$q$$ and I noticed that $$gcd(p,q) = 1$$. Let $$o =$$ order $$p$$ of a modulo $$m$$. From $$(1)$$ $$o\in\{1,p\}$$. And here I don't know how to proceed. I see that it sufficies to prove that there exist a prime $$q$$ for which $$o = p$$ and we know that $$o = p$$ divides $$\phi(q) = q-1$$ so $$q\equiv 1\pmod p$$. Any help appreciated.

## 2 Answers

First work modulo $$p-1$$ so $$N:=\sum_{j=0}^{p-1}p^j=p=1$$, and fix a prime factor $$q$$ of $$N\ge3$$ (and hence of $$p^p-1$$), which won't be $$p$$ or a prime factor of $$p-1$$. Now work modulo $$q$$: since $$p\ne1$$ but by Fermat's little theorem $$p^{\gcd\{p,\,q-1\}}=1$$, the GCD is $$p$$ as required.

• How do you know that there exisst a prime factor which won't be $p$ or a prime factor of $p-1$? – Calvin Lin Dec 28 '20 at 1:06
• @CalvinLin Because neither $p$ nor $p-1$ divides $N$. – J.G. Dec 28 '20 at 8:17

As $$p^p\equiv1\pmod q$$

and $$p^{q-1}\equiv1\pmod q$$

$$p^{(q-1,p)}\equiv1\pmod q$$

Now if $$p|(q-1),(p,q-1)=p$$

Else $$(p,q-1)=1,p^1\equiv1\pmod q$$

• How do you know that there exist a prime factor $q > p$? – Calvin Lin Dec 28 '20 at 1:05