# explain why $a^{\frac{p-1}{2}}\equiv 1 \pmod{p}$.

If $\gcd({a,p})=1$ where $p\gt2$ is a prime and if $a$ has a square root modulo p, explain why $a^{\frac{p-1}{2}}\equiv 1 \pmod{p}$.

I wish I could provide some work, but all i've been able to find online is various theorems and proofs that don't seem to apply.

Euler's Criterion:

If p is an odd prime and p doesn't divide a, then $x^2 \equiv a \pmod{p}$ has a solution or no solution depending on whether $a^\frac{p-1}{2}\equiv1$ or $-1\pmod{p}$.

Since $a\equiv x^2 \pmod p \text{ for some }x \$ we get $\ a^{\frac{p-1}{2}} \equiv x^{p-1} \pmod p$.
But $(a,p)=1 \Rightarrow (x,p)=1 \Rightarrow$ from Fermat's little theorem $x^{p-1} \equiv 1 \pmod p$.
Therefore $\ a^{\frac{p-1}{2}} \equiv 1 \pmod p$.
• Could you explain a little more on what $x \Rightarrow a^{\frac{p-1}{2}}=x^{p-1}=1 \pmod p$ means. I'm having a hard time following. – maroon.elephants Nov 5 '12 at 15:43
• Since $a$ has a square root $\pmod p \Rightarrow$ $a \equiv x^2 \pmod p$ for some $x$. Now if $a \equiv b \pmod p \Rightarrow a^k \equiv b^k \pmod p, \ \forall k \in \mathbb{N}.$ So $a^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}}\equiv x^{p-1} \pmod p$. – P.. Nov 6 '12 at 22:45