6
$\begingroup$

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,

  • 1
    Well, of course it's wrong. Which book claimed this?2011-03-09
  • 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.2011-03-09
  • 0
    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}$2011-03-09
  • 1
    @Arturo Magidin: Elementary Number Theory and Its application by Kenneth H. Rosen. I've just bought it from the library today :(.2011-03-09
  • 0
    @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.2011-03-09
  • 0
    @Chan: Do you have the book right in front of you? Are you *positive* it says that, and not $-\frac{p+1}{2}$ on the right hand side?2011-03-09
  • 0
    @Arturo Magidin: Yes, I'm 100% positive. It must be a typo, I guess.2011-03-09
  • 0
    @Chan: I have the ebook. Could you tell me the page number of the book?2011-03-09
  • 0
    @Sivaram Ambikasaran: What's your edition? Mine is 6th edition. It's in the back of the book page 673, problem 31.2011-03-09
  • 0
    Mine is the 5th edition. Can you give the chapter number and section number and the exercise number2011-03-09
  • 0
    @Sivaram Ambikasaran: Mine is chapter 6, section 6.1 exercises, exercise number is 31.2011-03-09

2 Answers 2

5

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

1

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

  • 0
    @Sivaram: Thanks; there's a plus there, at any rate...2011-03-09
  • 0
    @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}!$2011-03-09
  • 0
    @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}.$$2011-03-09
  • 0
    @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.2011-03-09
  • 0
    @Chan: I have added the intermediate steps.2011-03-09
  • 0
    @Sivaram Ambikasaran: Thank you. You guys here are so nice, I really appreciate it. Once again, thanks Arturo Magidin.2011-03-09