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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
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
up vote 1 down vote accepted

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)!$?

share|cite|improve this answer
    
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^*).$

share|cite|improve this answer
    
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$$

share|cite|improve this answer
    
A very well written and concise answer. – Jakub Konieczny Sep 22 '12 at 8:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.