3
$\begingroup$

Prove that all divisors of

$$\frac{p^p-1}{p-1}$$

are of the form $pk+1$ where $p$ is prime and $k\in\mathbb{Z}$.

1 Answers 1

6

Let $q$ be a prime divisor of $\dfrac{p^p-1}{p-1}$. Then in particular $q$ divides $p^p-1$. But $q\ne p$, and therefore by Fermat's Theorem, $p^{q-1}\equiv 1\pmod{q}$.

So the order of $p$ modulo $q$ divides $q-1$. It also divides $p$. There are two cases to consider: (i) $p$ has order $1$ modulo $q$ and (ii) $p$ has order $p$ modulo $q$.

In Case (i), $p\equiv 1\pmod q$. We have $$\frac{p^p-1}{p-1}=p^{p-1}+p^{p-2}+\cdots +1.$$ On the right-hand side, there are $p$ terms, each congruent to $1$ modulo $q$. Thus $\dfrac{p^p-1}{p-1}$ is congruent to $p$ modulo $q$, and in particular cannot be divisible by $q$. This contradicts the fact that $q$ is a prime divisor of $\dfrac{p^p-1}{p-1}$.

In Case (ii), the order of $p$ modulo $q$ is $p$. So $p$ divides $q-1$, meaning that $q$ is of the shape $pk+1$.

But any positive divisor of $\dfrac{p^p-1}{p-1}$ is either $1$ or the product of not necessarily distinct primes that divide $\dfrac{p^p-1}{p-1}$, that is, of primes of the shape $pk+1$. And the product of any number of integers of the form $pk+1$ is also of the form $pk+1$. This completes the proof.

Remark: We proved the result for positive divisors of $\dfrac{p^p-1}{p-1}$. In general, it will not be true for negative divisors.

  • 0
    I was reading this but I don't understand the second paragraph. We have that $p^p\equiv p^{q-1}\equiv 1\pmod q$. Could you please explain me why the order of $p$ modulo $q$ must divide $q-1$ and $p$?2012-11-03
  • 1
    We are working mod $q$. Let $e$ be the order of $p$. So 4e$ is smallest positive integer such that $p^e\equiv 1\pmod{q}$. Now let $K$ be **any** positive integer such that $p^K\equiv 1\pmod{q}$. Then $e$ divides $K$. Why? If not, try to divide, get $K=xe+e'$. Easily $p^{e'}\equiv 1\pmod{q}$, contradicting fact $e$ is the order of $p$. Now (i) By Fermat, $p^{q-1}\equiv 1\pmod{q}$, so putting $K=q-1$ we get $e$ divides $q-1$. Also (ii) we chose $q$ that divides $p^p-1$. So $p^p\equiv 1\pmod{q}$. Taking $K=p$ we get that $e$ divides $p$. Hope is detailed enough.2012-11-03
  • 0
    Yes it is clear now, thanks for the answer.2012-11-03