Number Theory: An Introduction to Mathematics

198 IV Continued Fractions and Their Uses

The least solution in positive integers, obtained by takingk=1, is called thefunda-
mental solutionof (9).
To illustrate these results, supposed=a^2 +1forsomea∈N.Since

√

d=[a, 2 a],
the equationx^2 −dy^2 =−1 has the fundamental solutionx=a,y=1 and the equa-
tionx^2 −dy^2 =1 has the fundamental solutionx= 2 a^2 +1,y= 2 a. Again, suppose
d=a^2 +afor somea∈N.Since

√

d=[a, 2 , 2 a], the equationx^2 −dy^2 =−1isin-
soluble, but the equationx^2 −dy^2 =1 has the fundamental solutionx= 2 a+1,y=2.
It is not difficult to obtain upper bounds for the fundamental solutions. Since
ξ=

√

dis a root of the polynomialt^2 −dand since its complete quotientsξnare
reduced forn≥1, they have the form

ξn=(−Bn+

√

D)/ 2 An,

whereD = 4 d, 0 <−Bn <

√

DandAn≥1. Thereforea 0 =ξ <

√

dand
an=ξn< 2

√

dforn≥1. If we putα=

√

d, it is easily shown by induction that

pn≤(α+α−^1 )n+^1 / 2 , qn≤(α+α−^1 )n (n≥ 0 ).

These inequalities may now be combined with any upper bound for the periodh
(cf.§3).
Under composition, the fundamental solution of (8) generates an infinite cyclic
groupCof solutions of (8). Furthermore, by composing the fundamental solution
of (9) with any element ofCwe obtain infinitely many solutions of (9). We are go-
ing to show that, by composing also with the trivial solution− 1 ,0 of (8), all integral
solutions of (8) and (9) are obtained in this way. This can be proved by means of con-
tinued fractions, but the following argument due to Nagell (1950) provides additional
information.

Proposition 11Let d be a positive integer which is not a perfect square, let m be a
positive integer, and let x 0 ,y 0 be the fundamental solution of the equation( 8 ).
If the equation
u^2 −dv^2 =m (10)

has an integral solution, then it actually has one for which u^2 ≤ m(x 0 + 1 )/ 2 ,
dv^2 ≤m(x 0 − 1 )/ 2.
Similarly, if the equation

u^2 −dv^2 =−m (11)

has an integral solution, then it actually has one for which u^2 ≤ m(x 0 − 1 )/ 2 ,
dv^2 ≤m(x 0 + 1 )/ 2.

Proof By composing a given solution of (10) with any solution in the subgroupCof
solutions of (8) which is generated by the solutionx 0 ,y 0 we obtain again a solution
of (10). Letu 0 ,v 0 be the solution of (10) obtained in this way for whichv 0 has its least
non-negative value. Thenu^20 =m+dv^20 also has its least value and by changing the
sign ofu 0 we may supposeu 0 >0. By composing the solutionu 0 ,v 0 of (10) with the
inverse of the fundamental solutionx 0 ,y 0 of (8) we obtain the solution

u=x 0 u 0 −dy 0 v 0 ,v=x 0 v 0 −y 0 u 0