Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a problem with this exercise :

prof that $p-1|\space q \iff (p-1)^2|\space p^q - 1$

I succeed to prof that $(p-1)^2|\space p^q - 1 \implies p-1|\space q$

thanks ^^

share|cite|improve this question
Are $p$ and $q$ primes? – Lazar Ljubenović Feb 16 '13 at 12:39
I donot think they should be primes... – Shane Chern Feb 16 '13 at 12:56
p and q dosen't primes ^^ – Sherloek holmes Feb 16 '13 at 20:43
@Sherloekholmes What does ^^ imply after your post? – pushpen.paul Oct 17 '14 at 11:49
up vote 2 down vote accepted

Since $p^q-1=(p-1)(p^{q-1}+\cdot\cdot\cdot+1)$, we find that $\frac{(p^q-1)}{(p-1)^2}=\frac{p^{q-1}+\cdot\cdot\cdot+1}{p-1}$. Hence, if $p-1$ divides $q$, then $p^q-1$ is a multiple of $p^{p-1}-1=(p^{p-2}+\cdot\cdot\cdot+1)(p-1)$, which is divisible by $(p-1)^2$.
For the other direction, since $p^{q-1}+\cdot\cdot\cdot+1\equiv q \pmod{p-1}$, we find that $(p-1)^2$ divides $p^q-1$ if and only if $p-1$ divides $q$.
So this finishes the proof.

share|cite|improve this answer
If $p>2,$ as $(p-1)\mid q$ how can $q$ be prime? – lab bhattacharjee Feb 16 '13 at 12:47

$\rm{\bf Hint}\:\ (p\!-\!1)^2\! \mid p^q\!-1 \!\iff\! p\!-\!1\ \bigg|\ \dfrac{p^q\!-1}{p\!-\!1} = p^{q-1}\! +\cdots\!+p\! +\! 1\equiv 1+\cdots\!+1$ $\rm\equiv q\ (mod\ p\!-\!1)$

As I explained it has a nice conceptual view as a special case of a derivative test for multiple roots.

share|cite|improve this answer

I just prove the other half.
Notice that: $$p^n=(p-1)(p^{n-1}+\cdots+1)+1\quad(n\in\mathbb{N}^+)$$ hence, $p^n\equiv1\pmod{p-1}$ (Also it's true for $n=0$). $$p^q-1=(p-1)(p^{q-1}+\cdots+1)$$ so $p^{q-1}+\cdots+1\equiv q\equiv0\pmod{p-1}$.
that is $$p-1\mid p^{q-1}+\cdots+1$$ Q.E.D.

share|cite|improve this answer

$p = 1 \mod (p-1)$
Also, let $r = \dfrac{p^q - 1}{p-1} = p^{q-1} + p^{q-2} + \dots + p + 1$
Then $ r = 1 + 1+ \dots + 1 + 1$, $q$ times $\mod (p-1)$
Or $ r = q = 0 \mod (p-1)$, as $(p-1) \mid q$

Thus $(p-1)^2 \mid (p-1)r = p^q - 1$

share|cite|improve this answer

Your Answer


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.