Skip to main content

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.

Before we do this, let's codify something we already have discussed since Question 7.1.1 at various times, e.g. in Fact 7.3.1 or Section 7.6.

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.

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

Before we start the proof, recall Wilson's Theorem, which states that

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

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.

Somehow this is a satisfying answer. We can check that these really are square roots of \(-1\) using Sage.