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,

  • 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 Ambikasaran: Thank you. You guys here are so nice, I really appreciate it. Once again, thanks Arturo Magidin.2011-03-09