## 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

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

Then the order of \(f\) in \(U_p\) is four, since

We know that the order

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

###### Proof.

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

Do you remember our proof? We *paired up* all the numbers from \(2\) to \(p-2\) in pairs of multiplicative inverses (mod \(p\)), thus:

Our strategy for this proof will be similar.

This time, pair up the numbers from \(1\) to \(p-1\) in a *different* way, in pairs of additive inverses (mod \(p\)):

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{,}\)

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

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:

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.