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.
