Section 13.3 A Lemma About Square Roots Modulo \(n\)
We’ll continue our formal investigation of what numbers are sums of two squares by taking a look at a seemingly unrelated lemma about square roots. In
Section 14.1 we’ll see that square roots of negative one (thinking of
\(-1\in\mathbb{Z}\text{,}\) not
\(\mathbb{Z}_n\)) are connected to sums of squares as well, so it is not completely implausible to connect roots and these sums.
Definition 13.3.1.
We say that a number \(a\) has a square root modulo \(n\) if there is some number \(x\) with
\begin{equation*}
x^2\equiv a\text{ (mod }n)\text{.}
\end{equation*}
As an example using this framework, here is an alternate proof of
Exercise 7.7.12.
Fact 13.3.2.
For an odd prime \(p\text{,}\) the only way there is a square root of \(-1\) modulo \(p\) is if \(p\equiv 1\text{ (mod }4)\text{.}\)
Proof.
We will use group theory to prove this.
Assume there is a square root \(f\text{,}\) so that
\begin{equation*}
f^2\equiv -1\text{ (mod }p)\text{.}
\end{equation*}
Then the order of \(f\) in \(U_p\) is four, since
\begin{equation*}
f^4=(f^2)^2\equiv (-1)^2=1\text{.}
\end{equation*}
We know that the order
\begin{equation*}
\mid U_p \mid =p-1
\end{equation*}
but then Lagrange’s (group theory)
Theorem 8.3.12 says that four divides
\(p-1\text{.}\)
Given that, the only possible kind of prime \(p\) solving this is the form \(4k+1\text{.}\)
Remember, this means there can’t be a square root of minus one if
\(p\equiv 3\text{ (mod }4)\text{.}\) Of course, it also only means that there
might be one if
\(p\equiv 1\text{ (mod }4)\text{,}\) so we certainly need the following lemma to confirm there
is one. (See its use in
Subsection 16.1.1, where we combine everything into
Fact 16.1.2.)
Lemma 13.3.3.
For an odd prime \(p\equiv 1\text{ (mod }4)\text{,}\) there actually does exist a square root of \(-1\) modulo \(p\text{.}\) That is, there is an \(f\) such that
\begin{equation*}
f^2\equiv -1\text{ (mod }p)\text{.}
\end{equation*}
\begin{equation*}
(p-1)!\equiv -1\text{ (mod }p)\text{ for primes}\text{.}
\end{equation*}
Do you remember our proof? We paired up all the numbers from \(2\) to \(p-2\) in pairs of multiplicative inverses (mod \(p\)), thus:
\begin{equation*}
(p-1)!=1\cdot 2\cdot 2^{-1}\cdot 3\cdot 3^{-1}\cdots (p-1) \equiv (p-1)\equiv -1\text{ (mod }p)\text{.}
\end{equation*}
Our strategy for this proof will be similar, using all numbers from \(1\) to \(p-1\text{,}\) but paired up in a different way.
Proof of Lemma 13.3.3.
Pair up the numbers from \(1\) to \(p-1\) in a product, in pairs of additive inverses (mod \(p\)):
\begin{equation*}
(p-1)!=1\cdot (p-1)\cdot 2\cdot (p-2)\cdot 3\cdot (p-3)\cdots \frac{p-1}{2}\cdot\frac{p+1}{2}=
\end{equation*}
\begin{equation*}
\left[1\cdot 2\cdot 3\cdots \frac{p-1}{2}\right]\cdot \left[(p-1)\cdot (p-2)\cdots \frac{p+1}{2}\right]\text{.}
\end{equation*}
This makes sense because \((p-1)/2\) is an integer halfway between \(1\) and \(p\text{,}\) as \(p\) is odd.
If we rethink things (mod \(p\)), we can rewrite this in a more suggestive way. Let \(\left(1\cdot 2\cdot 3\cdots \frac{p-1}{2}\right)\) be called \(f\text{.}\) This is also \(\left(\frac{p-1}{2}\right)!\text{,}\) of course. Then, keeping in mind that \(\frac{p+1}{2}=p-\frac{p-1}{2}\text{,}\)
\begin{equation*}
\left[1\cdot 2\cdot 3\cdots \frac{p-1}{2}\right]\cdot \left[(p-1)\cdot (p-2)\cdots \frac{p+1}{2}\right]
\end{equation*}
\begin{equation*}
\equiv f \cdot \left[-1\cdot -2\cdot -3\cdots -\frac{p-1}{2}\right]
\end{equation*}
\begin{equation*}
\equiv f\cdot (-1)^{\frac{p-1}{2}}\left[1\cdot 2\cdot 3\cdots \frac{p-1}{2}\right]\equiv (-1)^{\frac{p-1}{2}}f^2\text{.}
\end{equation*}
Remember that our hypothesis is
\(p\equiv 1\) (mod
\(4\)). Then
\(p=4k+1\) for integer
\(k\text{,}\) so
\(\frac{p-1}{2}=2k\) is even and by
Wilson’s Theorem
\begin{equation*}
-1\equiv f^2\text{ (mod }p)
\end{equation*}
What is neat about this proof is that it shows there are precisely
two square roots of negative one – as Lagrange’s (polynomial)
Theorem 7.4.1 suggests. We even have a formula for them:
\begin{equation*}
f=\pm \left(\frac{p-1}{2}\right)!\text{,}
\end{equation*}
where the exclamation point here indicates the factorial. Especially given the proof, an imaginative mind
6 might call this, “The square root of
Wilson’s Theorem,” by analogy with
Theorem 12.3.2.
Somehow this is a satisfying answer. We can check that these really are square roots of \(-1\) using Sage.
Such as that of Abraham Holleran, to whom I am indebted for this point.
www.numbertheory.org/classnos/