Although we will spend some significant time working on solving congruences, I haven't forgotten deeper questions. To see how congruences can impact this, 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. Take a look at this table and see if you can find something.
Question7.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.10.)
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 search through Mordell/Bachet curves, and let's look at the particular case \(y^2=x^3+7\).
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.
Proposition7.6.2Showing a Mordell curve has no integer point
There is no integer \(x\) such that \(y^2=x^3+7\), so there are no integer points on this curve.
First let's consider the case where \(x\) is even. Then \(2\mid x\), so \(8\mid x^3\). 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\), so that's not possible.
So it must be the case that \(x\equiv 1\) (mod \(4\)).
Now we do a trick 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\). (Otherwise all its primes look like \(4n+1\equiv 1\), the product of which would also be \(\equiv 1\) (mod \(4\)).)
If \(q\) divides \(x+2\), it (naturally) divides \((x+2)(x^2-2x+4)\) as well. But if it divides \((x+2)(x^2-2x+4)\), it must then divide \(y^2+1\), since they're equal.
However, our exploration said that a prime of the form \(4n+3\) can't divide \(y^2+1\)! So, assuming this is true, \(x\equiv 1\text{ (mod }4)\) doesn't work either.
As a note, we will eventually prove the result of exploration in Fact 13.3.2, but you may want to try to find an “elementary” proof in Exercise 7.7.10.
Enough said; congruences are amazingly powerful.
