Number Theory: An Introduction to Mathematics

4 Quadratic Diophantine Equations 197

Proposition 10Let d be a positive integer which is not a perfect square. Suppose
ξ=

√

d has complete quotientsξn, convergents pn/qn, and continued fraction expan-
sion[a 0 ,a 1 ,...,ah]of period h.
Then p^2 n−dq^2 n=± 1 if and only if n=kh− 1 for some integer k> 0 and in this
case

p^2 kh− 1 −dq^2 kh− 1 =(− 1 )kh.

Proof Fromξ=(pnξn+ 1 +pn− 1 )/(qnξn+ 1 +qn− 1 )we obtain

(pn−qnξ)ξn+ 1 =qn− 1 ξ−pn− 1.

Multiplying by(− 1 )n+^1 (pn+qnξ),weget

snξn+ 1 =ξ+rn,

where

sn=(− 1 )n+^1 (p^2 n−dqn^2 ), rn=(− 1 )n(pn− 1 pn−dqn− 1 qn).

Thussnandrnare integers. Moreover, sinceξn+ 1 +kh = ξn+ 1 andξis irrational,
sn+kh=snandrn+kh=rnfor all positive integersk.
Ifp^2 n−dq^2 n=±1, then actuallypn^2 −dqn^2 =(− 1 )n+^1 ,sincepn/qnis less than or
greater thanξaccording asnis even or odd. Hencesn=1andξn+ 1 =ξ+rn.Taking
integral parts, we getan+ 1 =a 0 +rn. Consequently

ξn−+^12 =ξn+ 1 −an+ 1 =ξ−a 0 =ξ 1 −^1.

Thusξn+ 2 =ξ 1 , which implies thatn=kh−1 for some positive integerk.
On the other hand, ifn=kh−1 for some positive integerk,thenξn+ 2 =ξ 1 and
hence

ξn+ 1 −an+ 1 =ξ−a 0.

Thusξn+ 1 =ξ+an+ 1 −a 0 , which implies thatsn=1, sinceξis irrational.

It follows from Proposition 10 that, ifdis a positive integer which is not a perfect
square, then the equation (8) always has a solution in positive integers and all such
solutions are given by

x=pkh− 1 , y=qkh− 1 (k= 1 , 2 ,...)ifhis even,

x=p 2 kh− 1 , y=q 2 kh− 1 (k= 1 , 2 ,...)ifhis odd.

The least solution in positive integers, obtained by takingk=1, is called thefunda-
mental solutionof (8).
On the other hand, the equation (9) has a solution in positive integers if and only if
his odd and all such solutions are then given by

x=pkh− 1 , y=qkh− 1 (k= 1 , 3 , 5 ,...).