1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.