Question

Find two positive nontrivial solutions of x^2-Ny^2=1 when N is 15, 7, or 99

Answer 1

Hello,

if n=15: (4,1),(31,8),(244,63)

if n=7: (8,3),(127,48),(2024,765)

if n=99: (10,1),(199,20),(3970,399)

(Pell 's equation)

Download xls

Answer 2

The solutions to the Pell equation

... x^2 -N·y^2 = ±1

are (x, y) = (p, q) where p/q are alternate convergents‡ of the continued fraction of √N.

The continued fractions for √15 and √99 can be written as

... √15 = 3 + 1/(1 + 1/(6 + 1/(1 + 1/(6 + 1/...))))

or, more compactly, as {3, {1, 6}};

and

... √99 = 9 + 1/(1 + 1/(18 + 1/(1 + 1/(18 + 1/...))))

or, more compactly, as {9, {1, 18}}.

The compact form of the continued fraction for √7 is {2, {1, 1, 1, 4}}.

In all cases, the continued fraction terms of a square root repeat after some finite-length sequence. In the compact form, the repeating sequence is shown in curly brackets. This permits the convergents to be defined recursively.

Successive convergents of the square root are p[k]/q[k], where

... p[k] = a[k]·p[k-1] +p[k-2] . . . . where p[-1]=0, p[0]=1

... q[k] = a[k]·q[k-1] +q[k-2] . . . . where q[-1]=1, q[0]=0

and the a[k] are written in the compact form as {a[1], {a[2], a[3], ...}}

For the given numbers N, the (x, y) values that are solutions to the given equation can be defined recursively quite nicely. The same recursive equation (written here as pq[ ]) is used for both p and q (as above), but with different initial conditions for p than for q.

For N=15, we can write

... pq[k] = 8·pq[k-1] - pq[k-2] . . . . . {p[-1], p[0]} = {4, 1} . . . {q[-1], q[0]} = {-1, 0}

so {x, y} = {4, 1}, {31, 8}, {244, 63}, {1921, 496}, ...

For N=99, we can write

... pq[k] = 20·pq[k-1] - pq[k-2] . . . . . {p[-1], p[0]} = {10, 1} . . . {q[-1], q[0]} = {-1, 0}

so {x, y} = {10, 1}, {199, 20}, {3970, 399}, {79201, 7960}, ...

For N=7, we can write

... pq[k] = 16·pq[k-1] - pq[k-2] . . . . . {p[-1], p[0]} = {8, 1} . . . {q[-1], q[0]} = {-3, 0}

so {x, y} = {8, 3}, {127, 48}, {2024, 765}, {32257, 12192}, ...

_____

‡ Convergents alternate between being larger than the square root and smaller than the square root. However, when there are more than 2 values in the repeating sequence of the continued fraction, the convergents that result in a solution to the Pell equation may be farther apart than every other convergent. For N=7, every 4th convergent gives a solution.