2
$\begingroup$

$p$ is a prime, odd integer. $a$ is an integer. we assume that $p$ does not divide $a$. $\left( \frac{a}{p} \right)$ denotes the Legendre symbol.

In order to prove $a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right)$ mod $p$ my course demonstrates the following statement first (Wilson) :

$\left( p-1 \right)! \equiv -\left(\frac{a}{p}\right) a^{\frac{p-1}{2}}$ mod $p$

However it is not clear to me how this implies the first statement.

$\endgroup$

marked as duplicate by Lord Shark the Unknown, Henrik, Namaste, kingW3, Jack D'Aurizio number-theory Oct 15 '17 at 16:23

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.

1
$\begingroup$

Hint: Use Wilson's theorem $(p - 1)! \equiv -1 \bmod p$ and the property $\left(\frac{a}{p}\right)^2 = 1$.

$\endgroup$
  • $\begingroup$ indeed, I feel very stupid now, thank you. $\endgroup$ – fqzjiooqgtihj Jan 20 '16 at 18:26
  • $\begingroup$ It's my pleasure. Always happy to help $\endgroup$ – Mikhail Goltvanitsa Jan 20 '16 at 18:27
1
$\begingroup$

$\mathbb{F}_p$ is a field so there exists $g$ a cyclic generator of the multiplicative group. so there exists $b$ such that $g^b = -1 $ so $g^{2b} = 1 $ and $g$ being a generator its order is $p-1$ so $b = (p-1)/2$.

$g$ cannot be a square because if $g = h^2$ then $h^{p-1} = 1 = g^{(p-1)/2} = -1$.

finally, if $a$ is a square then there exists $c$ such that $a = g^{2c}$ and $a^{(p-1)/2} = 1$,

and if $a$ is not a square then there exists $c$ such that $a = g^{2c+1}$ and $a^{(p-1)/2} = -1$.

$\endgroup$

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