0
$\begingroup$

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.

  • 0
    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.2012-08-30

3 Answers 3

1

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

  • 0
    @Abhishek: Yes, Bill’s answer and mine are basically the same thing, just with more detail on my part.2012-08-30
1

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^*).$

  • 0
    Bill, your answer is also acceptable but I saw Brian's first :)2012-08-30
1

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$

  • 0
    A very well written and concise answer.2012-09-22