NTIC Exploring Patterns in Square Roots

Section 7.1 Exploring Patterns in Square Roots

Just as in high school algebra one moved from linear functions to quadratics (and found there was a lot to say about them!), this is the next natural step in number theory. We will focus on congruences. We haven't abandoned integers! But it turns out that questions about quadratic polynomials with integers are much, much harder, and are better pursued after studying the relatively simple (and computable) cases of quadratic congruences. Much later, we will return to a full investigation of this.

🔗

You may recall that we looked at one particular quadratic congruence in Question 4.6.7 and Exercise 4.7.19, and saw that the solution depended at least partly on the modulus in Exercises 6.6.25 and 6.6.26. So we will examine these slightly simpler-sounding questions keeping in mind the structure of the modulus, not so much the actual answers.

🔗

Question 7.1.1.

Consider the following questions, even if the term ‘square root’ seems a bit odd right now.

For what prime $p$ does $-1$ have a square root?
For what integers $n$ does $1$ have more square roots than just $\pm 1\text{?}$

🔗

As we will precisely define in Definition 13.3.1, these questions are equivalent to the following quadratic congruence questions.

Is there a solution to

$\begin{equation*} x^2\equiv -1\text{ (mod }p)\text{ or }x^2+1\equiv 0\text{ (mod }p)\; ? \end{equation*}$
Are there more than the two obvious solutions to

$\begin{equation*} x^2\equiv 1\text{ (mod }n)\text{ (or equivalently }x^2-1\equiv 0\text{ (mod }n)\text{)?} \end{equation*}$

🔗

Let's look at each of these in turn. If you are online, you may use the following interacts, but they are merely an aid. It is quite possible to use pencil and paper to explore these as well.

An interact for which primes $-1$ has a square root:

xxxxxxxxxx
 
@interact
def _(p=(13,prime_range(10,100))):
    pretty_print(html("Values of $x^2+1$ mod %s"%(p,)))
    pretty_print(html("<ul>"))
    for m in [0..p-1]:
        pretty_print(html(r"<li>$%s^2+1\equiv %s\text{ (mod }%s)$</li>"%(m,mod(m,p)^2+1,p)))
    pretty_print(html("</ul>"))

An interact for when $1$ has more square roots than just $\pm 1$ – a rather tricky question:

xxxxxxxxxx
 
@interact
def _(n=(12,[10..100])):
    pretty_print(html("Values of $x^2-1$ mod %s"%(n,)))
    pretty_print(html("<ul>"))
    for m in [0..n]:
        pretty_print(html(r"<li>$%s^2-1\equiv %s\text{ (mod }%s)$</li>"%(m,mod(m,n)^2-1,n)))
    pretty_print(html("</ul>"))

🔗

What do you get? See Exercise 7.7.1. To keep track of results, writing ideas in the margin of a physical book or in a small text document on a computer are both awesome.