Section13.3A Lemma about Square Roots Modulo \(n\)
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.
Subsection13.3.1Reminder about square roots
We begin by codifying something we already have discussed.
Definition13.3.1
We say that a number \(a\) has a square root modulo \(n\) if there is some number \(x\) with \[x^2\equiv a\text{ mod }(n)\; .\]You may have found square roots of \(\pm 1\) earlier. Here is a fact we mentioned before.
Fact13.3.2
For an odd prime \(p\), then the only way there is a square root of \(-1\) modulo \(p\) is if \(p\equiv 1\text{ mod }(4)\).Proof
We will use group theory to prove this.
- Assume there is a square root, so that \[u^2\equiv -1\text{ mod }(p)\; .\]
- Then the order of \(u\) in \(U_p\) is four, since \[u^4=(u^2)^2\equiv (-1)^2=1\; .\]
- We know that the order \[\mid U_p \mid =p-1\] but then the group theory theorem of Lagrange says that four divides \(p-1\).
- So the only possible such prime \(p\) is one that is of the form \(4k+1\).
- (We used the fact that \(p\) is odd because then \(-1\not\equiv +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)\).
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. However, for now we have the following lemma.
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 \[u^2\equiv -1\text{ mod }(p)\; .\]Proof
- Recall Wilson's Theorem, 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: \[(p-1)!=1\cdot 2\cdot 2^{-1}\cdot 3\cdot 3^{-1}\cdots (p-1) \equiv (p-1)\equiv -1\text{ mod (}p)\, .\]
- Now, assuming that Wilson's Theorem is true, we will pair up the numbers from \(1\) to \(p-1\) in a different way, in pairs of additive inverses mod (\(p\)): \[(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}=\]\[\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]\, .\] This makes sense because \((p-1)/2\) is an integer halfway between \(1\) and \(p\), as \(p\) is odd.
- But 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 \[\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]\]\[\equiv f \cdot \left[-1\cdot -2\cdot -3\cdot -\frac{p-1}{2}\right]\] \[\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\, .\]
- Now, when \(p\equiv 1\) mod (4), then \(p=4k+1\) so \(\frac{p-1}{2}=2k\) is even.
- That means: \[-1\equiv f^2\text{ or }f^2\equiv -1\text{ mod }(p)\] so in fact there precisely two square roots of negative one (as Lagrange's (polynomial) Theorem suggests), and we even have a formula for them:\[\pm \left(\frac{p-1}{2}\right)!\]Somehow this is a satisfying answer.
We can check that these really are square roots of \(-1\).
