3
$\begingroup$

Let $p$ be an odd prime with a primitive root $g$. Prove that $$\prod_{x=1}^{\frac{p-1}{2}}x^2 \equiv (-1)^{\frac{p+1}{2}}\pmod{p}.$$

Remark: I intend to use the relationship $g^{\frac{p-1}{2}} \equiv -1 \pmod{p}.$

$\endgroup$
2
$\begingroup$

$\prod_1^{p-1}x=\prod_1^{(p-1)/2}x\prod_{(p+1)/2}^{p-1}x\equiv\prod_1^{(p-1)/2}x\prod_1^{(p-1)/2}(-x)=(-1)^{(p-1)/2}\prod_1^{(p-1)/2}x^2$ but also by Wilson's Theorem $\prod_1^{p-1}x\equiv-1\pmod p$ and there you are.

$\endgroup$
3
$\begingroup$

If you really want to use a primitive root, note that your product is equal to the product of all the non-zero squares (the quadratic residues) modulo $p$. But these are congruent to the even powers of our primitive root $g$. So your product is congruent to $$g^2 g^4 g^6\cdots g^{2\frac{p-1}{2}}.$$ This is equal to $$g^{2\left(1+2+3+\cdots +\frac{p-1}{2}\right)}.$$ The arithmetic progression which is the exponent of $g$ has sum $$\frac{p-1}{2}\frac{p+1}{2}.$$ Finally, $$g^{\frac{p-1}{2}\frac{p+1}{2}}=\left(g^{\frac{p-1}{2}}\right)^{\frac{p+1}{2}}\equiv (-1)^{\frac{p+1}{2}}\pmod{p}.$$

$\endgroup$
  • $\begingroup$ Your first line seems to suggest that $g,\cdots,g^{p-1/2}$ enumerates $1,\cdots, p-1/2$, why is that? $\endgroup$ – user27126 Oct 31 '12 at 17:10
  • $\begingroup$ I certainly would not want to suggest that, since it is false! But the squares of the numbers between $1$ and $\frac{p-1}{2}$ are an enumeration (modulo $p$) of all the non-zero squares. (The squares of the numbers between $\frac{p+1}{2}$ and $p-1$ are another enumeration of the non-zero squares.) And the even powers of $g$ are another enumeration of all the squares. $\endgroup$ – André Nicolas Oct 31 '12 at 17:19
0
$\begingroup$

$\prod_{1\le x\le p-1}x\equiv\prod_{1\le y\le p-1}g^y$ $=g^{1+2+\cdots +p-1}=g^{\frac{p(p-1)}2}=(g^\frac{p-1}2)^p\equiv (-1)^p=-1$

$\prod_{1\le x\le p-1}x=\prod_{1\le x\le \frac{p-1}2}x(p-x)$ as to avoid omission and repetition of terms $x\le p-x\implies x\le \frac p 2$ i.e., $x\le\frac{p-1}2$ as $p$ is odd

So, $\prod_{1\le x\le p-1}x\equiv(-1)^\frac{p-1}2\prod_{1\le x\le \frac{p-1}2}x^2$

So, $(-1)^\frac{p-1}2\prod_{1\le x\le \frac{p-1}2}x^2\equiv-1$

Multiplying either sides by $(-1)^{p-1},$ (which is legal as $(-1)^{p-1}=1$ as $p$ is odd)

$\prod_{1\le x\le \frac{p-1}2}x^2\equiv (-1)(-1)^\frac{p-1}2=(-1)^\frac{p+1}2$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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