NTIC The Algebraic Story

Subsection 15.6.1 Computing the hyperbola

Now we can use our geometric intuition to reveal what is happening algebraically here. The algebra is not hard, but a little dense; follow this proof closely.

🔗

Proposition 15.6.1.

Doubling integer points on the hyperbola $x^2-2y^2=1$ yields more integer points.

🔗

Proof.

Algebraically, if $x^2-2y^2=1\text{,}$ then the tangent line at any point $(x_0,y_0)$ other than $(\pm 1,0)$ is given by implicit differentiation to be $y'=\frac{x_0}{2y_0}\text{.}$ So we start there.

What is the line through $(1,0)$ with that same slope? It's

\begin{equation*} y=\frac{x_0}{2y_0}(x-1)\text{,} \end{equation*}

of course. Let's check where else this intersects the hyperbola, if at all.

Start off with plugging the line into the hyperbola:

\begin{equation*} x^2-2y^2-1=x^2-2\left(\frac{x_0}{2y_0}(x-1)\right)^2-1= \end{equation*}

\begin{equation*} \left(1-\frac{x_0^2}{2y_0^2}\right)x^2+\left(\frac{x_0^2}{y_0^2}\right)x+\left(-1-\left(\frac{x_0^2}{2y_0^2}\right)\right)=0\text{.} \end{equation*}

This can be simplified and then solved, unbelievably (via the quadratic formula or factoring out $x-1$):

\begin{equation*} (2y_0^2-x_0^2)x^2+2x_0^2 x+(-2y_0^2-x_0^2)=0 \end{equation*}

\begin{equation*} x=\frac{-2x_0^2-4y_0^2}{-2x_0^2+4y_0^2}=\frac{x_0^2+2y_0^2}{x_0^2-2y_0^2}=x_0^2+2y_0^2 \end{equation*}

Finally, do a slick substitution of the original point:

\begin{equation*} y=\frac{x_0}{2y_0}(x-1)=\frac{x_0}{2y_0}(x_0^2+2y_0^2-(x_0^2-2y_0^2))=2x_0 y_0\text{.} \end{equation*}

To recap, given a point $(x_0,y_0)$ we have achieved a new point $(x_0^2+2y_0^2,2x_0 y_0)\text{.}$

🔗

Now let's try this with actual points in Sage! I have provided both a numerical and a graphical interact.

xxxxxxxxxx
 
@interact
def _(x_0=17,y_0=12):
    x_1=x_0^2+2*y_0^2
    y_1=2*x_0*y_0
    pretty_print(html("Initial point was $(%s,%s)$; new point is $(%s,%s)$."%(x_0,y_0,x_1,y_1)))
    pretty_print(html(r"And indeed $%s^2-2\cdot%s^2$ equals $%s$"%(x_1,y_1,x_1^2-2*y_1^2)))

xxxxxxxxxx
 
d=2
var('x,y')
@interact
def _(x_0=3,y_0=2,lattice=False,auto_update=False):
    g(x,y)=x^2-d*y^2
    x_1,y_1=x_0^2+2*y_0^2,2*x_0*y_0
    plot1 = implicit_plot(g-1, (x_0-4,x_1+4), (x_0-4,x_1+4),plot_points = 200)
    grid_pts = [[i,j] for i in [x_0-4..x_1+4] for j in [x_0-4..x_1+4]]
    plot_grid_pts = points(grid_pts, rgbcolor=(0,0,0), pointsize=2)
    lattice_pts = [coords for coords in grid_pts if (coords[0]^2-d*coords[1]^2==1)]
    plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1), pointsize=20)
    line1 = plot((x_0/(2*y_0))*(x-x_0)+y_0,x_0-4,x_1+4, color='red')
    line2 = plot((x_0/(2*y_0))*(x-1),x_0-4,x_1+4, color='red', linestyle='--')
    if lattice:
        show(plot1 + plot_grid_pts + plot_lattice_pts + line1 + line2, figsize = [5,5], xmin = x_0-4, xmax = x_1+4, ymin = y_0-4, ymax = y_1+4, aspect_ratio=1)
    else:
        show(plot1+plot_lattice_pts+line1+line2, figsize = [5,5], xmin = x_0-4, xmax = x_1+4, ymin = y_0-4, ymax = y_1+4, aspect_ratio=1)
    pretty_print(html("The new points are $x_1=%s$ and $y_1=%s$"%(x_1,y_1)))

🔗

Awesome!

🔗

Subsection 15.6.2 Yet more number systems

¶

🔗

Brahmagupta knew how to do this (see for example Wikipedia). Of course, he did it both without our geometric interpretation (which was only made possible by Descartes and Fermat's introduction of coordinate systems, though at least Fermat when he examined these was not thinking geometrically) and also without the benefit of symbolically representing

$\sqrt{2}\text{,}$ which provides this alternate description of what we did.

🔗

Fact 15.6.2.

If $(x_0,y_0)$ is a solution to $x^2-2y^2=1\text{,}$ then so is $(x_1,y_1)$ where

$\begin{equation*} (x_0+\sqrt{2}y_0)^2=x_1+\sqrt{2}y_1\text{.} \end{equation*}$

🔗

If you were to do the algebra out here to get a formula for

$(x_1,y_1)$ in terms of

$(x_0,y_0)\text{,}$ you'd get exactly the same answer as we did above (Exercise 15.7.16).

🔗

Moreover, notice that once again we seem to have created a new number system, though this time we have added to the integers the square root of a positive, not negative number! (And yes, it turns out that finding solutions to this equation is related to

$\mathbb{Z}[\sqrt{2}]\cdots\text{.}$ ³For more details connecting the topics of this section more directly to abstract algebra, see [C.2.7, Sections 5.3-5.4]; for a more geometric viewpoint, see the same author's Numbers and Geometry, Chapters 4 and 8.)

🔗

Furthermore, the “point doubling” procedure precisely corresponds to multiplying a group element by 2. That is to say:

$\begin{equation*} [5]+ [5]\equiv 3\text{ (mod }7)\text{ is the same type of operation as }(3,2)+(3,2)=(17,12)\text{.} \end{equation*}$

🔗

It turns out that there is a more general formula that corresponds to taking the line through two (integer) points and then creating a line with the same slope that goes through the original point

$(1,0)\text{:}$

🔗

Example 15.6.3.

If both $(x_1,y_1)$ and $(x_2,y_2)$ are solutions of $x^2-2y^2=1\text{,}$ then so is

$\begin{equation*} (x_1 x_2+2y_1 y_2, x_1 y_2+y_1 x_2)\text{.} \end{equation*}$

If you apply this to two points opposite each other on the same branch of the hyperbola, such as $(3,2)$ and $(3,-2)\text{,}$ you will get

$\begin{equation*} (3\cdot 3+2\cdot 2\cdot (-2),3\cdot (-2)+3\cdot 2)=(1,0)\text{.} \end{equation*}$

In this sense, if we treat $(1,0)$ as an identity element in the sense of group identity, then $(3,-2)$ may be considered the additive inverse of $(3,2)\text{.}$

xxxxxxxxxx
 
@interact(layout=[['x_0','y_0'],['x_1','y_1'], ['auto_update']])
def _(x_0=3,y_0=2,x_1=17,y_1=12,auto_update=False):
    if x_0 != x_1:
        x_3,y_3=x_1*x_0+2*y_1*y_0,x_1*y_0+y_1*x_0
        pretty_print(html("Initial points were $(%s,%s)$ and $(%s,%s)$; new point is $(%s,%s)$."%(x_0,y_0,x_1,y_1,x_3,y_3)))
        pretty_print(html(r"And indeed $%s^2-2\cdot%s^2$ equals $%s$"%(x_3,y_3,x_3^2-2*y_3^2)))
    elif y_0==y_1:
        x_3,y_3=x_0^2+2*y_0^2,2*x_0*y_0
        pretty_print(html("Initial points were $(%s,%s)$ and $(%s,%s)$; new point is $(%s,%s)$."%(x_0,y_0,x_1,y_1,x_3,y_3)))
        pretty_print(html(r"And indeed $%s^2-2\cdot%s^2$ equals $%s$"%(x_3,y_3,x_3^2-2*y_3^2)))
    else:
        print("Input correct numbers!")

🔗

This procedure ends up working for any

$n\text{.}$ Just change all the

$2$ s above to

$n$ s. Let's see this “by hand” for

$n=3\text{,}$ where we solve

$x^2-3y^2=1$ with

$\begin{equation*} 2^2-3\cdot 1^2=1\text{.} \end{equation*}$

🔗

That is, I use

$\begin{equation*} x'=x^2+3y^2\text{ and }y'=2xy \end{equation*}$

xxxxxxxxxx
 
@interact
def _(x=2,y=1,auto_update=False):
    x,y=x*x+3*y*y,x*y+y*x
    pretty_print(html(r"$%s^2-3\cdot%s^2=%s$"%(x, y, x^2-3*y^2)))
    pretty_print(html("New point is $(%s,%s)$"%(x, y)))

🔗

Subsection 15.6.3 The general solution (any $n$ )

¶

🔗

The general solution, given two points

$(x_1,y_1)$ and

$(x_2,y_2)\text{,}$ would be, for

$n>0$ and not a perfect square,

$\begin{equation*} x'=x_1x_2+ny_1y_2\text{ and }y'=x_1y_2+x_2y_1\text{.} \end{equation*}$

🔗

Even more generally, the same formula works for combining solutions of two different equations like the Pell.

🔗

Fact 15.6.4.

$\begin{equation*} \text{If }x_0^2-ny_0^2=k\text{ and }x_1^2-ny_1^2=\ell \end{equation*}$

$\begin{equation*} \text{then }x=x_0x_1+ny_0y_1,\; y=x_0y_1+y_0x_1\text{ solves }x^2-ny^2=k\ell\text{.} \end{equation*}$

🔗

Proof.

See Exercise 15.7.17.

🔗

This is particularly nice if

$k=\ell=-1\text{,}$ because getting a solution for that would then give a solution to the Pell equation!

🔗

Brahmagupta used analogous techniques for his time (and more sophisticated things) to solve very hard ones, as did the later English mathematicians who answered the following challenges of Fermat.

🔗

Question 15.6.5.

Find nontrivial solutions to these equations:

$x^2-61y^2=1\text{.}$
$x^2-109y^2=1\text{.}$

Solution

Fermat knew that the smallest solution to the second one is

\begin{equation*} x=158070671986249,y=15140424455100\text{,} \end{equation*}

which we can check below. The great mathematician André Weil [C.5.8, II.XIII] finds that Fermat's comment to his counterparts that the numbers $61$ and $109$ were ones selected to not give too much trouble was ‘mischievously’ said; do you agree?

xxxxxxxxxx
 
158070671986249^2-109*15140424455100^2

🔗

Considering that Brahmagupta says that finding the solution

$x=1151,y=120$ to the equation

$x^2-92y^2=1$ within a year proved the person “was a mathematician”, we can be very thankful for computers!

Number Theory: In Context and Interactive

Section 15.6 The Algebraic Story

Subsection 15.6.1 Computing the hyperbola

Proposition 15.6.1.

Proof.

Subsection 15.6.2 Yet more number systems

Fact 15.6.2.

Example 15.6.3.

Subsection 15.6.3 The general solution (any $n$ )

Fact 15.6.4.

Proof.

Question 15.6.5.

Section 15.6 The Algebraic Story

Subsection 15.6.1 Computing the hyperbola

Proposition 15.6.1.

Proof.

Subsection 15.6.2 Yet more number systems

Fact 15.6.2.

Example 15.6.3.

Subsection 15.6.3 The general solution (any nn)

Fact 15.6.4.

Proof.

Question 15.6.5.

Subsection 15.6.3 The general solution (any $n$ )