I’ve previously written about Fermat’s Little Theorem, which tells us that if $latex p$ is a prime and $latex a$ is not divisible by $latex p$, then $latex a^{p-1} \equiv 1 \pmod{p}$.  That’s not terribly exciting when $latex p = 2$, so let’s concentrate on odd primes $latex p$ in this post.  Then $latex \frac{p-1}{2}$ is a whole number, so it makes sense (in the modular arithmetic world) to let $latex x = a^{\frac{p-1}{2}}$.  Then Fermat‘s Little Theorem tells us that $latex x^2 \equiv 1 \pmod{p}$.

How many possibilities for $latex x$ are there (modulo $latex p$, of course), if we know that $latex x^2 \equiv 1 \pmod{p}$?

Well, that congruence tells us that $latex (x – 1)(x + 1) \equiv 0 \pmod{p}$.  But, in the jargon, “there are no zero-divisors modulo a prime”.  That is, if $latex mn \equiv 0 \pmod{p}$, then $latex m \equiv 0 \pmod{p}$…

View original post 798 more words