Section7.1Prime fun and Square Roots

We begin with a couple of fun questions that turn out to be quite interesting. Perhaps it's because we have pretty much exhausted what we want to do with linear congruences and equations. We have to start moving on to get to more interesting questions.

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. Likewise, we keep seeing unusual things about primes numbers, so we will start with something about that.

Subsection7.1.1Prime Fun

Here's a little fun that starts us thinking along the lines of what's to come.

Of course, I'm cheating a little:

In fact, we can prove that quite the opposite of what you might have thought with this example is true.

Fact7.1.1

There is no non-constant polynomial \(f(x)\) with integer coefficients such that \(f(x)\) is prime for all integers \(x\).

(Note that this is not true if you have a multivariable polynomial! Yikes.)

What is the reason? It turns out to be directly related to our previous work on congruences. Namely, if \(f(a)=p\) for some \(a\), then for any \(b\equiv a\) mod (\(p\)) we have \(f(b)\equiv f(a)\) (by well-definedness of addition and subtraction) as well, so \[f(b)\equiv f(a)\equiv p\equiv 0\text{ mod }(p)\text{, or that }p\mid f(b)\; .\] But the problem is that if \(f(b)\) is also prime for all such \(b\), then we have a polynomial which returns to height \(f(x)=p\) periodically, and hence \(\lim_{x\to\infty}f(x)\neq \pm \infty\), which is only possible if \(f\) is a constant polynomial.

What a surprise - limits and calculus can be used in number theory! Even at this early stage, this is true; more will be later. A few more polynomials like this are below: this link has lots and lots more information.

Subsection7.1.2Square Roots

We continue with a basic interesting question. We haven't abandoned integers, by the way! But it turns out that the 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; for now we will look for patterns in two questions.

For what prime \(p\) does \(-1\) have a square root?
For what integers \(n\) does \(1\) have more square roots than just \(\pm 1\)?

Let's look at each of these in turn.

The first question is equivalent to asking whether there is a solution to \[x^2\equiv -1\text{ mod }(p)\text{ or }x^2+1\equiv 0\text{ mod }(p)\; \] This interact might help.

Similarly, the second question is asking what solutions there are to \[x^2\equiv 1\text{ mod }(n)\text{ (equivalently) }x^2-1\equiv 0\text{ mod }(n)\] This is quite tricky, but you will see some patterns.