Advanced book on Mathematics Olympiad

5.3 Diophantine Equations 277

x^2 −Dy^2 = 1

has infinitely many solutions in positive integers and the general solution(xn,yn)n≥ 1 is
computed from the relation

(xn,yn)=(x 1 +y 1

√

D)n,

where(x 1 ,y 1 )is the fundamental solution(the minimal solution different from the trivial
solution( 1 , 0 )).

The fundamental solution can be obtained by trial and error. But there is an algorithm
to find it. The continued fraction expansion or

√

Dis periodic:

√

D=a 0 +

1

a 1 +

1

a 2 +···+

1

an+

1

a 1 +

1

a 2 +···

.

Whennis even, the fundamental solution is given by the numerator and the denominator
of the fraction

a 0 +

1

a 1 +

1

a 2 +···+

1

an− 1

,

while whennis odd, the fundamental solution is given by the numerator and the denom-
inator of the fraction

a 0 +

1

a 1 +

1

a 2 +···+

1

an+

1

a 1 +

1

a 2 +···+

1

an− 1

.

This algorithm is not as simple as it seems. The smallest solution(x 1 ,y 1 )can depend
exponentially onD. From the computational point of view, the challenge is to determine