# Proving Euler’s congruence and Legendre

So the question is "Prove Euler's congruence $a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \bmod p$ for odd primes $p$ and $a$ in $\mathbb{Z}$."

So I know that $$\left(\frac{a}{p}\right) = \begin{cases} 1, & \text{if } a \equiv \square \bmod p \text{ and } a \not\equiv 0 \bmod p \\ -1, & \text{if } a \not\equiv \square \bmod p \\ 0, & \text{if } a \equiv 0 \bmod p \end{cases}$$ And I also know that $$a^{\frac{p-1}{2}} \equiv \begin{cases} 1 \bmod p \text{ if } a \equiv \square \mod p \\ -1 \bmod p \text{ if } a \not\equiv \square \bmod p \end{cases}$$ So I'm just not sure how to go about proving this. I'm probably just over thinking it.

• If you already know these things then you are finished. – André Nicolas Dec 6 '14 at 18:26
• So the proof just falls out of the definition? I just wasn't sure if that was enough or if I was missing something. – mconn7 Dec 6 '14 at 18:27
• Well, the result that $a^{(p-1)/2}\equiv 1\pmod{p}$ when $a$ is a QR of $p$, and is $\equiv -1\pmod{p}$ if $a$ is an NR of $p$ takes some work to prove. But once that has been done, the result $\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod{p}$ is an immediate consequence. Because of your definition of the Legendre symbol as $0$ when $p$ divides $a$ (I prefer to leave it undefined), one more trivial observation has to be made, that if $p$ divides $a$ then $a^{(p-1)/2}\equiv 0\pmod{p}$. – André Nicolas Dec 6 '14 at 18:34
• @AndréNicolas: I think it is important for the Legendre symbol $(\frac{a}{p})$ to be defined without any exceptions, meaning even when $a \equiv 0 \bmod p$. I'll give you two reasons. The first is that it leads to the Jacobi symbol $(\frac{m}{n})$ being defined without any constraint on the gcd of $m$ and $n$, so you can compute Jacobi symbols by Jacobi reciprocity without having to check ahead of time if $m$ and $n$ are relatively prime. If they weren't relatively prime then eventually your symbol would become $(\frac{0}{b}) = 0$ and you'd then know $m$ and $n$ have a common factor after all. – KCd Jan 3 '15 at 20:33
• The second reason is that you can then say that the number of solutions to $x^2 \equiv a \bmod p$ is $1 + (\frac{a}{p})$ for all possible $a$ (no exceptions). This might seem trivial, but it is important when you want to count solutions to equations over finite fields that you can write out such counting formulas all the time. Ireland & Rosen's number theory book uses this idea very often with squares replaced by higher powers, which is possible if you define power residue characters like the Legendre symbol to be defined as $0$ at $a = 0$. – KCd Jan 3 '15 at 20:35