NTIC Epilogue: Why Congruences Matter

Section 7.6 Epilogue: Why Congruences Matter

Although we will spend some significant time working on solving congruences, I don't want to lose sight of deeper questions. To see how congruences help address them, recall the search in Section 7.1 for primes

$p$ such that

$\begin{equation*} x^2\equiv -1\text{ (mod }p) \end{equation*}$

🔗

has a solution. The table given by the following interact is organized a little more; if online, try to find a pattern in which

$p$ yield solutions and which do not.

xxxxxxxxxx
 
import itertools
​
@interact
def _(n=20):
    yeslist=[]
    nolist=[]
    for p in prime_range(3,n):
        res = 0
        for res in [0..p]:
            if mod(res,p)^2+1 == 0:
                yeslist.append(p)
                break
        else:
            nolist.append(p)
    t = [['exist', 'do not exist']] + [[a,b] for (a,b) in itertools.zip_longest(yeslist,nolist)]
    for item in t:
        for i in range(len(item)):
            if item[i] is None:
                item[i]=''
    pretty_print(html(r"Solutions to $x^2\equiv -1$ (mod $p$) for $2\le p \le %s$:"%n))
    pretty_print(html(table(t, header_row = True, frame = True)))

🔗

Question 7.6.1.

Do you see a pattern related to some kind of congruence? (This one should be more apparent than in Section 7.3; see also Exercise 7.7.12.)

🔗

The reason I point this kind of thing out is not just because I can, but because it shows simple congruence patterns can have a big result. We will prove a result about integers, assuming something about congruences.

🔗

Recall our brief search through Mordell/Bachet curves in Section 3.5. Let's look at the particular case

$x^3=y^2-7\text{.}$

Solutions of $x^3=y^2-7$ in several viewing windows

🔗

It's amazing how the curve slips between every integer lattice point… So it seems that a perfect square can't ever be exactly seven more than a perfect cube. Is this true? Here's where congruences come into play.

🔗

Proposition 7.6.3. Showing a Mordell curve has no integer point.

There are no integers $x,y$ such that $y^2=x^3+7\text{,}$ so there are no integer points on this curve.

🔗

Proof.

As a prefatory note, this proof will depend upon the results of our exploration at the beginning of this section. We will eventually prove these conjectures in Fact 13.3.2, which will allow us to claim full proof of this statement in Fact 15.3.3. However, you may want to try to find an “elementary” proof of the conjecture in Exercise 7.7.12.

For convenience, we will rewrite $x^3=y^2-7$ as $y^2=x^3+7\text{.}$ To begin the proof, first consider the case where $x$ is even. Then $2\mid x\text{,}$ so $8\mid x^3\text{.}$ That means $y^2\equiv 7$ (mod $8$).

Unfortunately, the only perfect squares mod $(8)$ seem to be 0, 1, and 4. So this is not possible.

What about if $x$ is odd? Then $y$ must be even, since $x^3$ and $7$ are odd. So let's examine whether $x\equiv 1$ (mod $4$) or $x\equiv 3$ (mod $4$), the next two options.

If $x\equiv 3$ (mod $4$), then $x^3\equiv 27\equiv 3$ (mod $4$), so $x^3+7\equiv 10\equiv 2$ (mod $4$). But we already know from earlier that perfect squares are only $0$ or $1$ modulo $4\text{,}$ so that's not possible.
So it must be the case that $x\equiv 1$ (mod $4$).

Now we do a trick⁵Davenport in [C.4.10] and Conrad credit this proof to the same Lebèsgue mentioned in the rediscovery of Qin's generalized Chinese Remainder Theorem in Subsection 5.5.1. like that of completing the square:

\begin{equation*} y^2=x^3+7\Rightarrow y^2+1=x^3+8\Rightarrow y^2+1= (x+2)(x^2-2x+4) \end{equation*}

Let's analyze this carefully in the following argument.

If $x\equiv 1$ (mod $4$), then $x+2\equiv 3$ (mod $4$).
So not only is $x+2$ an odd number, but also it must be divisible by a prime $q$ of the form $4n+3\text{.}$ (Otherwise all its primes look like $4n+1\equiv 1\text{,}$ the product of which would also be $\equiv 1$ (mod $4$).)
If $q$ divides $x+2\text{,}$ it (naturally) divides $(x+2)(x^2-2x+4)$ as well. But if it divides $(x+2)(x^2-2x+4)\text{,}$ it must then divide $y^2+1\text{,}$ since they're equal.
However, our exploration at the start of this section suggested that a prime of the form $4n+3$ can't divide $y^2+1\text{!}$
So, assuming it is true that only primes of the form $4n+1$ can divide perfect squares plus one ($y^2+1$), then $x\equiv 1\text{ (mod }4)$ doesn't work either.

🔗

Enough said; congruences are amazingly powerful.