This result has a very uninformative name, I’m afraid, and it doesn’t identify the result uniquely, but it is the standard name so I’d better stick with it.

I’m going to write this post on the assumption that you know about Fermat’s little theorem and Euler’s criterion.  Fortunately, those links take you to places on this blog where you can read everything you need to know, and then you can come back here.

Ready?  Are you sitting comfortably?  Then we’ll begin.

Let’s fix an odd prime $latex p$, and some number $latex a$ that is coprime to $latex p$.  We’d like to know whether $latex a$ is a quadratic residue modulo $latex p$.  Putting that another way, we’d like to find the value of the Legendre symbol $latex \genfrac{(}{)}{}{}{a}{p}$.  Helpfully, Euler‘s criterion tells us that $latex \genfrac{(}{)}{}{}{a}{p} \equiv a^{\frac{p-1}{2}} \pmod{p}$.  I say “helpfully”, but it rather…

View original post 905 more words