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.

If $p - a \equiv -a \pmod{p}$ then what is $\frac{p-1}{2} \equiv ? \pmod{p}$? Where $p$ is an odd prime.

I read in the book, they claimed: $$p - 1 \equiv -1 \pmod{p}$$ $$p - 2 \equiv -2 \pmod{p}$$ $$p - 3 \equiv -3 \pmod{p}$$ $$ ... $$ $$\frac{p - 1}{2} \equiv -(\frac{p - 1}{2}) \pmod{p}$$

However, I realized that the last statement was wrong because if it's true then: $$\frac{p - 1}{2} + \frac{p - 1}{2}\equiv 0 \pmod{p}$$ $$p - 1 \equiv 0 \pmod{p}$$

This is my scan version from the book 6th edition Any idea?

Thanks,

share|improve this question
1  
Well, of course it's wrong. Which book claimed this? –  Arturo Magidin Mar 9 '11 at 5:25
1  
Well, it's the inverse of $-2$ modulo $p$. In other words $(-2)\cdot\frac{p-1}{2} \equiv 1 \mod p$. The last step of your sequence of equalities mod $p$ should be $\frac{p-1}{2} \equiv -\frac{p+1}{2}$ by the way. –  Myself Mar 9 '11 at 5:25
    
I dont understand your question $\frac{p-1}{2} \equiv \frac{p-1}{2} \pmod{p}$ or $\frac{p-1}{2} \equiv -\frac{p+1}{2} \pmod{p}$ –  user17762 Mar 9 '11 at 5:25
1  
@Arturo Magidin: Elementary Number Theory and Its application by Kenneth H. Rosen. I've just bought it from the library today :(. –  Chan Mar 9 '11 at 5:28
    
@Sivaram Ambikasaran: $\frac{p-1}{2} \equiv -\frac{p-1}{2} \pmod{p}$ was from the book. I don't know what does the rhs equal to. –  Chan Mar 9 '11 at 5:30
show 6 more comments

2 Answers 2

up vote 4 down vote accepted

The sequence as written doesn't make sense, since the last term does not follow the pattern of the previous ones. However, you can argue that $$p - \left(\frac{p-1}{2}\right) \equiv -\frac{p-1}{2}\pmod{p}.$$ This does follow the same pattern as the rest of the terms.

And since $$p - \frac{p-1}{2} = \frac{2p-p+1}{2} = \frac{p+1}{2}$$ then you have that $$\frac{p+1}{2}\equiv -\frac{p-1}{2}\pmod{p},$$ hence $\frac{p-1}{2}\equiv -\frac{p+1}{2}\pmod{p}$.

Or peharps, it went like this: \begin{align*} p-1 &\equiv -1\pmod{p}\\ p-2 &\equiv -2 \pmod{p}\\ &\vdots\\ \frac{p-1}{2} = p-\left(\frac{p+1}{2}\right) &\equiv -\frac{p+1}{2}\pmod{p} \end{align*} and you have the wrong sign in the numerator on the right hand side?

Added. So, the rest of the proof. According to the scans Sivaram has posted, this was part of the computation of $\left(\frac{p-1}{2}\right)!^2$. The idea then is that we can get $\left(\frac{p-1}{2}\right)!$ by multiplying the terms on the right hand side, and then get it again by multiplying the terms on the left hand side. That is, we look at \begin{align*} p-1 &\equiv -1 \pmod{p}\\ p-2 &\equiv -2 \pmod{p}\\ &\vdots\\ p-\left(\frac{p-1}{2}\right) &\equiv -\frac{p-1}{2}\pmod{p} \end{align*} and note that if $p\equiv 3\pmod{2}$, then we have an odd number of negative signs on the right hand side. So we have that: $$(-1)\left(\frac{p-1}{2}\right)! = (-1)\Bigl(1\times 2\times\cdots\times \frac{p-1}{2}\Bigr) \equiv (p-1)(p-2)\cdots\left(p - \frac{p-1}{2}\right)\pmod{p}.$$ Now, $p - \frac{p-1}{2} = \frac{p+1}{2} = \frac{p-1}{2}+1$. So therefore we have that: \begin{align*} \left(\frac{p-1}{2}\right)!^2 &= \left(\frac{p-1}{2}\right)!\left(\frac{p-1}{2}\right)!\\ &\equiv \left(\frac{p-1}{2}\right)!\Biggl( -(p-1)(p-2)\cdots\left(\frac{p-1}{2}+1\right)\Biggr)\pmod{p}\\ &\equiv -\left(1\times 2\times 3\times\cdots\times\left(\frac{p-1}{2}\right)\times\left(\frac{p-1}{2}+1\right)\times\cdots\times (p-1)\right)\pmod{p}\\ &\equiv -(p-1)!\pmod{p}. \end{align*} But we know that $(p-1)!\equiv -1\pmod{p}$ by Wilson's Theorem, so $$\left(\frac{p-1}{2}\right)!^2 \equiv -(p-1)!\equiv -(-1) = 1\pmod{p},$$ so if we let $x = \left(\frac{p-1}{2}\right)!$, then $x^2 \equiv 1 \pmod{p}$. This means that $p|x^2-1 = (x-1)(x+1)$, so either $p|x-1$ or $p|x+1$. that is, eithe $x\equiv 1 \pmod{p}$ or $x\equiv-1\pmod{p}$; giving: $$\text{either }\left(\frac{p-1}{2}\right)!\equiv -1\pmod{p}\quad\text{or}\quad \left(\frac{p-1}{2}\right)!\equiv 1\pmod{p}.$$

share|improve this answer
4  
Very clear and step by step answer. I love the way you explain things. Great thanks. –  Chan Mar 9 '11 at 5:32
    
@Chan: I've also added an argument covering what is written. –  Arturo Magidin Mar 9 '11 at 6:32
    
Great thanks. –  Chan Mar 9 '11 at 6:36
add comment

In the 5th edition, they have got the signs right, at least thats what the scanned version of the ebook says.

enter image description here

EDIT

We have $p-k \equiv -k \pmod{p}$ and hence $$ \prod_{k=1}^{\frac{p-1}{2}} (p-k) \equiv \prod_{k=1}^{\frac{p-1}{2}} (-k) \pmod{p}$$

Note that $$(p-1)! = \left(\prod_{k=1}^{\frac{p-1}{2}} k \right) \left(\prod_{k=1}^{\frac{p-1}{2}} (p-k) \right)$$

Hence, $$(p-1)! \equiv \left(\prod_{k=1}^{\frac{p-1}{2}} k \right) \left(\prod_{k=1}^{\frac{p-1}{2}} (p-k) \right) \pmod{p} \equiv \left(\prod_{k=1}^{\frac{p-1}{2}} k \right) \left(\prod_{k=1}^{\frac{p-1}{2}} (-k) \right) \pmod{p}$$

Hence, $$(p-1)! \equiv (-1)^{\frac{p-1}{2}} \left(\prod_{k=1}^{\frac{p-1}{2}} k \right)^2 \pmod{p}$$

$$\left(\prod_{k=1}^{\frac{p-1}{2}} k \right) = \left(\frac{p-1}{2}\right)!$$

From Wilson's theorem, $$(p-1)! \equiv -1 \pmod{p}$$

Hence, $$-1 \equiv (-1)^{\frac{p-1}{2}} \left[ \left(\frac{p-1}{2}\right)! \right]^2 \pmod{p}$$

Hence, $$\left[ \left(\frac{p-1}{2}\right)! \right]^2 \equiv (-1)^{\frac{p+1}{2}} \pmod{p}$$

Hence, if $p = 4k+3$, then $$(-1)^{\frac{p+1}{2}} = 1$$

Hence, if $p = 4k+3$, $$\left[ \left(\frac{p-1}{2}\right)! \right]^2 \equiv 1 \pmod{p}$$

share|improve this answer
    
@Sivaram: Thanks; there's a plus there, at any rate... –  Arturo Magidin Mar 9 '11 at 6:04
    
@Sivaram Ambikasaran: I'm trying to understand the proof. So as you brought it up, could you help me understand this proof? I can ask another question if you don't mind because the lhs in your 5th edition doesn't make sense to me. How could it add up $\frac{p-1}{2}!$ –  Chan Mar 9 '11 at 6:06
    
@Chan: Look at my derivation again: $$\frac{p+1}{2} = p-\frac{p-1}{2}.$$ So you get$$\frac{p+1}{2} = p-\frac{p-1}{2} \equiv -\frac{p-1}{2}\pmod{p}.$$ –  Arturo Magidin Mar 9 '11 at 6:17
    
@Arturo Magidin: Many thanks, I did not realize they're related. Another question is that how the rhs equals to $!(p - 1)$? I could not see it. –  Chan Mar 9 '11 at 6:19
    
@Chan: I have added the intermediate steps. –  user17762 Mar 9 '11 at 6:28
show 1 more 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.