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

$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – maroon.elephants
    Nov 5, 2012 at 15:43
  • 1
    $\begingroup$ 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$. $\endgroup$
    – P..
    Nov 6, 2012 at 22:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .