196 IV Continued Fractions and Their Uses
where
x=x 1 x 2 +dy 1 y 2 , y=x 1 y 2 +y 1 x 2.(In fact, Brahmagupta’s identity is just a restatement of the norm relationN(αβ)=
N(α)N(β)for elementsα,βof a quadratic field.) In particular, from two solutions of
the equation
x^2 −dy^2 = 1 , (8)a third solution can be obtained bycompositionin this way.
Composition of solutions is evidently commutative and associative. In fact the
solutions of (8) form an abelian group under composition, with the trivial solution 1, 0
as identity element and the solutionx,−yas the inverse of the solutionx,y. Also, by
composing an arbitrary solutionx,yof (8) with the trivial solution− 1 ,0 we obtain
the solution−x,−y.
Suppose first thatd<0. Evidently (7) is insoluble ifm<0andx=y=0is
the only solution ifm=0. Ifm>0, there are at most finitely many solutions and we
may find them all by testing, for each non-negative integery≤(−m/d)^1 /^2 ,whether
m+dy^2 is a perfect square.
Suppose now that d>0. Ifd=e^2 is a perfect square, then (7) is equivalent to the
finite set of simultaneous linear Diophantine equations
x−ey=m′, x+ey=m′′,wherem′,m′′are any integers such thatm′m′′=m. Thuswe now suppose also that d
is not a perfect square.Thenξ=
√
dis irrational.
If 0<m^2 <dthen, by Proposition 5, any positive solutionx,yof (7) has the form
x=pn,y=qn,wherepn/qnis a convergent ofξ. In particular, all positive solutions
ofx^2 −dy^2 =±1 are obtained in this way.
On the other hand, as we now show, ifpn/qnis any convergent ofξthen
|p^2 n−dqn^2 |< 2√
d.Ifn = 0, then|p 02 −dq 02 |=|a 02 −d|,wherea 0 <
√
d < a 0 +1andso0 <d−a^20 <
√
d+a 0 < 2√
d. Now supposen>0. Then|pn−qnξ|<qn−+^11 and hence|p^2 n−dq^2 n|=|pn−qnξ||pn−qnξ+ 2 qnξ|
<qn−+^11 (qn−+^11 + 2 qnξ)< 2 ξ.An easy congruence argument shows that the equationx^2 −dy^2 =−1( 9 )has no solutions in integers unlessd≡1mod4 ord≡2 mod 8. It will now be shown
that the equation (8), on the other hand, always has solutions in positive integers.