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.

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|improve this question

marked as duplicate by Grigory M, Claude Leibovici, egreg, naslundx, Najib Idrissi May 2 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

3 Answers 3

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|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|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|improve this answer
    
A very well written and concise answer. –  Feanor Sep 22 '12 at 8:34

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