Theo Diamandis

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, f(z) = 0,

Newton's method seeks to find a root zz by starting from an initial guess z0z_0 and then updating this guess with the zero of the line tangent to ff at z0z_0, i.e.,

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

Pell's equation

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

x22y2=1. x^2 - 2y^2 = 1.

We wish to find integer solutions for xx and yy. A natural question is given an initial solution, for example (x0,y0)=(3,2)(x_0, y_0)= (3,2), how can generate additional solutions.

Solution generation via Newton's method

A slight rearrangement of Pell's equation gives

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

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

Inspired by this observation, we consider solving the equation z22=0z^2 - 2 = 0 with Newton's method. Starting from some initial iterate z0z_0, Newton's method gives the iteration

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

If ztz_t is a rational number, then it is clear that zt+1z_{t+1} will be rational as well, and we can write zt=xt/ytz_t = x_t / y_t for some integers xtx_t and yty_t. Plugging this in, we get the iteration

xt+1yt+1=xt2yt+ytxt=xt2+2yt22xtyt. \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

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

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

xt+122yt+12=(xt2+2yt2)22(2xtyt)2=xt4+4yt44xt2yt2=(xt22yt2)2=1.\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)(3,2), we can generate additional solutions via Newton's method applied to the root finding problem. The ratio x/yx/y will also provide a better and better approximation to 2\sqrt{2}.

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