4
$\begingroup$

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

1 Answers 1

8

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

  • 1
    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$.2012-11-06