# Proof of $a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right)$ mod $p$ [duplicate]

$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.

## marked as duplicate by Lord Shark the Unknown, Henrik, Namaste, kingW3, Jack D'Aurizio number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Oct 15 '17 at 16:23

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

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

$\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$.