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.

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|improve this question
2  
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 at 11:49

4 Answers 4

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|improve this answer
3  
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|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|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|improve this answer

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.