# If prime $p \equiv 1\pmod 4$ and $b = ((p-1)/2)!$ then show that $b^2 \equiv -1\pmod p$. [duplicate]

This question is from Victor Shoup's book on number theory chapter 2. The problem statement is as mentioned in the title of the question. I haven't been able to crack this one till now. I focused on solving this using the following information:

1. If p is an odd prime then $(p-1)! = -1 \pmod p$, otherwise called Wilson's theorem.

2. When $p \equiv 1 \pmod 4$ then any non square in $Z_p^*$ yields a square root of -1 modulo p.

I think we have to prove here that $b=((p-1)/2)!$ doesn't belong to $(Z_p^*)^2$ but I am unable to use Wilson's theorem or any other result to prove it.
PS: Not a homework for me but might be for someone else one day so tagging it as the same.

-

## marked as duplicate by Grigory M, Claude Leibovici, egreg, naslundx, Najib IdrissiMay 2 '14 at 12:41

Something slightly more general was proved in an answer on MathSE. The answer has been written several times, including at least once by me, but of course I can't find that one. –  André Nicolas Aug 30 '12 at 4:24
Thanks Nicolas, that was a beautiful proof you pointed out. –  Abhishek Anand Aug 30 '12 at 4:44
Ha! I just lectured on this very question today! –  Gerry Myerson Aug 30 '12 at 4:53
I don't get your second point. For $p=13$ the squares are $1$,$3$, $4$, $9$, $10$, $12\equiv -1$, and the square roots of $-1$ are $5$, $8$. How exactly does every non-square (take $2$ for instance) "yield" a square root of $-1$? –  Marc van Leeuwen Aug 30 '12 at 4:58
Marc, any non-square in $Z_p^*$ when raised to power $(p-1)/4$ will give you a square root of -1 modulo p. Here $p=13$ so $(p-1)/4 = 3$ and $2^3 = 8$ which is a square root of -1 as you have pointed out. –  Abhishek Anand Aug 30 '12 at 5:06

HINT: Since $p\equiv 1\pmod4$, we can write $p=4n+1$ for some integer $n$. Then $\frac12(p-1)=2n$. Suppose that $1\le k\le 2n$; then $-k\equiv p-k\pmod p$, and $2n+1\le p-k\le p-1$. Now consider

$$\prod_{k=2n+1}^{p-1}k\equiv\prod_{k=1}^{2n}(-k)\pmod p\;;$$

what is this in terms of $b$? And then what is $b^2$ in terms of $(p-1)!$?

-
Thanks Brian, worked it out. Though Bill's answer is also acceptable and lets us work out some more on our own. –  Abhishek Anand Aug 30 '12 at 4:47
@Abhishek: Yes, Bill’s answer and mine are basically the same thing, just with more detail on my part. –  Brian M. Scott Aug 30 '12 at 4:50

Hint $\$ Compute $\rm\:(p\!-\!1)!\:$ in two ways: in natural order (using Wilson), and by pairing up each factor with its negation (i.e. exploit reflection (involution) symmetry $\rm\:x\to -x\:$ on $\rm\:\Bbb Z_p^*).$

-
Bill, your answer is also acceptable but I saw Brian's first :) –  Abhishek Anand Aug 30 '12 at 4:48

By taking the product $(p-1)!$ and pairing each $x$ with $p-x\equiv -x \pmod p$ we get

$$(p-1)! \equiv \prod_{x=1}^{(p-1)/2} -x^2 = (-1)^{(p-1)/2}b^2=b^2$$

since $p\equiv 1 \pmod 4$ gives that $(p-1)/2$ is even. So by Wilson's theorem $$b^2\equiv (p-1)! \equiv -1 \pmod p$$

-
A very well written and concise answer. –  Feanor Sep 22 '12 at 8:34