NTIC A Lemma About Square Roots Modulo $n$

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 Z,

not

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

x^{2} \equiv a (mod n) .

🔗

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,$ the only way there is a square root of $- 1$ modulo $p$ is if $p \equiv 1 (mod 4) .$

🔗

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 (mod 4) .

Of course, it also only means that there might be one if

p \equiv 1 (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.)

🔗

Lemma 13.3.3.

For an odd prime $p \equiv 1 (mod 4),$ there actually does exist a square root of $- 1$ modulo $p .$ That is, there is an $f$ such that

f^{2} \equiv - 1 (mod p) .

🔗

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

(p - 1)! \equiv - 1 (mod p) for primes .

🔗

Do you remember our proof? We paired up all the numbers from

2

p - 2

in pairs of multiplicative inverses (mod

p

), thus:

(p - 1)! = 1 \cdot 2 \cdot 2^{- 1} \cdot 3 \cdot 3^{- 1} \dots (p - 1) \equiv (p - 1) \equiv - 1 (mod p) .

🔗

Our strategy for this proof will be similar, using all numbers from

1

p - 1,

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:

f = \pm (\frac{p - 1}{2})!,

🔗

where the exclamation point here indicates the factorial. Especially given the proof, an imaginative mind² might call this, “The square root of Wilson's Theorem,” by analogy with Theorem 12.3.2.

Such as that of Abraham Holleran, to whom I am indebted for this point.

🔗

Somehow this is a satisfying answer. We can check that these really are square roots of

- 1

using Sage.

xxxxxxxxxx
 
@interact
def _(p=(13,[q for q in prime_range(200) if q%4==1])):
    f=mod(factorial((p-1)/2),p)
    pretty_print(html(r"The potential square roots of $-1$ are $\pm \left(\frac{%s-1}{2}\right)!=%s,%s\text{ (mod }%s)$"%(p,f,-f,p)))
    pretty_print(html(r"And we can compute that ${0}^2\equiv{1}$ and ${2}^2\equiv {3}$ modulo ${4}$".format(f,f^2,-f,(-f)^2,p)))

🔗

Remark 13.3.4. A class act.

An observant reader may have noticed that when $p \equiv 3$ (mod $4$ ) the Proof of Lemma 13.3.3 can still be used, mutatis mutandis, to show that $\pm (\frac{p - 1}{2})!$ are square roots of $1$ modulo $p .$ (See Exercise 13.7.24.) Of course, we already know everything about those; they are just $\pm 1$ modulo $p,$ as you can test out below.

xxxxxxxxxx
 
@interact
def _(p=(11,[q for q in prime_range(200) if q%4==3])):
    f=mod(factorial((p-1)/2),p)
    pretty_print(html(r"The potential square roots of $1$ are $\pm \left(\frac{%s-1}{2}\right)!=%s,%s\text{ (mod }%s)$"%(p,f,-f,p)))
    pretty_print(html(r"And we can compute that ${0}^2\equiv{1}$ and ${2}^2\equiv {3}$ modulo ${4}$".format(f,f^2,-f,(-f)^2,p)))

Here comes the interesting part. If you play around with the interact, you will notice that sometimes $(\frac{p - 1}{2})! \equiv 1,$ and sometimes $(\frac{p - 1}{2})! \equiv - 1 .$ It's not immediately evident whether there is a pattern here.

But there is a formula. Foreshadowing Definition 14.1.2, if we define the number system ${a + b \frac{1 + \sqrt{- p}}{2} ∣ a, b \in Z}$ (ignoring whether that actually makes sense to do), one can define a special group (recall Definition 8.3.3) called the ideal class group of this number system. The order of this group is denoted by $h .$ Nearly miraculously, if $p > 3$ of this type, then

(\frac{p - 1}{2})! \equiv (- 1)^{(h + 1) / 2} (mod p) .

The default setting of the interact above is for $p = 11,$ and checking this list we see that $h = 1$ and indeed $(\frac{11 - 1}{2})! = 120 \equiv - 1 = (- 1)^{(1 + 1) / 2}$ modulo $11,$ while for $p = 23$ we have $h = 3$ and $(\frac{23 - 1}{2})! = 39916800 \equiv 1 = (- 1)^{(3 + 1) / 2}$ modulo $23 .$

There is a similar, but more complicated, formula when $p \equiv 1$ (mod $4$ ). And by ‘complicated’, I mean that if you've read this far, you've already guessed this is one of the most advanced remarks of the text. The class number being greater than one is closely related to the factorization question raised in Exercise 6.6.30; note that the class number for $p = 5$ in this setting is $2 .$ For more on all this (accessible if you've had a decent introduction to rings and fields), see [E.4.26, Chapters 10 and 26].

Section 13.3 A Lemma About Square Roots Modulo n