Pell's equation and Newton's method

While chatting through an exercise from A Friendly Introduction to Number Theory with Guille, he pointed out a connection between Pell's equation and Newton's method. I thought the perspective was cool, so I wanted to catalog it here. (There's also a connection with square-triangular numbers, which is explored in exercise 3.5.)

Review: Newton's method

Given a nonlinear equation,

f(z) = 0,

Newton's method aims to find a root $z$ by starting from an initial guess $z_0$ and then updating this guess with the zero of the line tangent to $f$ at $z_0$ , i.e.,

z_1 = z_0 - \frac{f(z_0)}{f'(z_0)}.

In other words, we linearly approximate $f$ at $z_0$ and then find the zero of that approximation.

Pell's equation

Pell's equation, in the case $n = 2$ is

x^2 - 2y^2 = 1.

We wish to find many integer solutions for $x$ and $y$ . If we have one solution, for example $(x_0, y_0)= (3,2)$ , how can we generate additional solutions?

Solution generation via Newton's method

A slight rearrangement of Pell's equation gives

\frac{x^2}{y^2} - \frac{1}{y^2} = 2.

As $x$ and $y$ become large, the fraction $x/y$ will provide better and better approximations to $\sqrt{2}$ .

Inspired by this observation, we'll consider solving the equation $z^2 - 2 = 0$ with Newton's method. Starting from $z_0$ , Newton's method gives the iteration

z_{t+1} = z_t - \frac{z^2_t - 2}{2z_t} = \frac{z_t}{2} + \frac{1}{z_t}.

If $z_t$ is a rational number, then $z_{t+1}$ will be rational as well. Thus, we can write $z_t = x_t / y_t$ for some integers $x_t$ and $y_t$ . Plugging this in, we get the iteration

\frac{x_{t+1}}{y_{t+1}} = \frac{x_t}{2y_t} + \frac{y_t}{x_t} = \frac{x_t^2 + 2y_t^2}{2x_ty_t}.

Splitting the numerator and denominator, we have the updates

x_{t+1} = x_t^2 + 2y_t^2 \qquad \text{and} \qquad y_{t+1} = 2x_ty_t.

Assume that $(x_t, y_t)$ is a solution to Pell's equation. Plugging in the update shows that $(x_{t+1}, y_{t+1})$ is also a solution:

\begin{aligned} x_{t+1}^2 - 2y_{t+1}^2 &= (x_t^2 + 2y_t^2)^2 - 2(2x_ty_t)^2 \\ &= x_t^4 + 4y_t^4 - 4x_t^2y_t^2 \\ &= (x_t^2 - 2y_t^2)^2 \\ &= 1. \end{aligned}

In other words, given an initial solution to Pell's equation, e.g., $(3,2)$ , we can generate additional solutions via Newton's method applied to the root finding problem. The ratio $x/y$ will also provide a better and better approximation to $\sqrt{2}$ .

Exercise 3.5 in the book derives this procedure using a more geometric approach. This derivation via Newton's method is likely well-known (my number theory knowledge is lacking), but I thought it was an interesting connection.