# Arithmetics ; $p-1 \mid q$ equivalent to $(p-1)^2 \mid p^q - 1$

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 ^^

-
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

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.

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

-

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.

-

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

-