BdMO Online Forum

Let $p$ be an odd prime.Prove $p^{p}-1$ has at least one prime divisor of the form $kp+1$

By Zsigmondy's theorem $p^p-1$ has a prime divisor not dividing $p-1$[Check the exceptions, none works]. Let it be $q$.
Let $d=ord_qp$. So $p^d \equiv 1 \pmod q$. So $d|p \Rightarrow d=1,p$.
If $d=1$, then $q|p-1$, a contradiction!
So $d=p$. Now $d|\phi (q) \Rightarrow p|q-1 \Rightarrow q=kp+1$, done!
Err... anyone have a solution without using sledgehammers?

${p}^{p}-1=(p-1)({p}^{p-1}+{p}^{p-2}..........p+1)$
Here gcd$(p-1,{p}^{p-1}+{p}^{p-2}..........p+1)=1$
Let $q$ be a prime divisor of ${p}^{p-1}+{p}^{p-2}..........p+1$
So $gcd(p-1,q)=1$
${p}^{p}\equiv 1(mod q)$
Again ${p}^{q-1}\equiv 1(mod q)$
or ${p}^{gcd(p,q-1)}\equiv 1(mod q)$
As $p$ is a prime,gcd$(p,q-1)=1$ or $p$
If gcd$(p,q-1)=1$,then $p\equiv 1(mod q)$
So $q$ divides $p-1$,but gcd$(p,q-1)=1$
That means gcd$(p,q-1)=p$
So $p$ divides $q-1$
This implies $q$ is of the for $kp+1$

Actually all of the divisors of $\frac {p^p-1}{p-1}$ will be congruent to $1 \bmod p$ (which comes directly from cyclotomic polynomials [Another sledgehammer ])

Yeah, and it directly kills SL-2006-N5. And this very problem(and a little গুতানি from Masum vai ) motivated me to learn about cyclotomic polynomials.

I think this can be done without using any sledgehammers too. May be BY Exponent GCD Lemma