# 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}$.

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}$.

-

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.

-
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$? –  barto Nov 3 '12 at 11:09
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. –  André Nicolas Nov 3 '12 at 16:57
Yes it is clear now, thanks for the answer. –  barto Nov 3 '12 at 19:34