Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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
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. –  André Nicolas Nov 3 '12 at 16:57
    
Yes it is clear now, thanks for the answer. –  barto Nov 3 '12 at 19:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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