Section13.3A Lemma About Square Roots Modulo \(n\)¶ permalink
We'll continue our formal investigation of what numbers are in sums of two squares by taking a look at a lemma seemingly unrelated to this. Later we'll see that square roots of negative one in \(\mathbb{Z}\) (not \(\mathbb{Z}_n\)) are connected to sums of squares as well, so this is not a completely implausible connection.
Before we do this, let's codify something we already have discussed, e.g. in Fact 7.3.1 or Section 7.6.
Definition13.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)\; .\end{equation*}
As an example, here is an alternate proof of Exercise 7.7.10.
Fact13.3.2
For an odd prime \(p\), the only way there is a square root of \(-1\) modulo \(p\) is if \(p\equiv 1\text{ (mod }4)\).
We will use group theory to prove this.
Assume there is a square root, so that \begin{equation*}u^2\equiv -1\text{ (mod }p)\; .\end{equation*} Then the order of \(u\) in \(U_p\) is four, since \begin{equation*}u^4=(u^2)^2\equiv (-1)^2=1\; .\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.11 says that four divides \(p-1\).
Given that, the only possible kind of prime \(p\) solving this is the form \(4k+1\).
Remember, this means there can't be a square root of minus one if \(p\equiv 3\text{ (mod }4)\). Of course, it also only means that there might be one if \(p\equiv 1\text{ (mod }4)\), 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.)
Lemma13.3.3
If \(p\equiv 1\text{ (mod }4)\), then there actually does exist a square root of \(-1\) modulo \(p\). That is, there is a \(u\) such that \begin{equation*}u^2\equiv -1\text{ (mod }p)\; .\end{equation*}
Before we start the proof, recall Theorem 7.5.1, that \((p-1)!\equiv -1\) (mod \(p\)) for primes. 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)\, .\end{equation*} Our strategy for this proof will be similar.
Assume Wilson's Theorem is true. Now pair up the numbers from \(1\) to \(p-1\) in a different way, 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]\, .\end{equation*} This makes sense because \((p-1)/2\) is an integer halfway between \(1\) and \(p\), 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\) (this is also \(\left(\frac{p-1}{2}\right)!\), of course).
Then \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\cdot -\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\, .\end{equation*}
Remember that our hypothesis is \(p\equiv 1\) (mod \(4\)). Then \(p=4k+1\), so \(\frac{p-1}{2}=2k\) is even, which means \begin{equation*}-1\equiv f^2\text{ or }f^2\equiv -1\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), and we even have a formula for them:\begin{equation*}\pm \left(\frac{p-1}{2}\right)!\end{equation*}
Somehow this is a satisfying answer. We can check that these really are square roots of \(-1\) using Sage.
