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.14, and saw that the solution depended at least partly on the modulus in Exercises 6.6.18 and 6.6.19. So we will examine these slightly simpler-sounding questions keeping in mind the structure of the modulus, not so much the actual answers.

These questions are exactly 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*}

• Is there a solution 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. The interacts are merely an aid; it is quite possible use pencil and paper to explore these as well.

• An interact for which primes \(-1\) has a square root:

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

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