Number Theory: An Introduction to Mathematics

200 IV Continued Fractions and Their Uses

and then from Proposition 7 thatξm+ 1 =− 1 /ξm′+ 1. But, by the proof of Proposi-
tion 10,

smξm+ 1 =ξ+rm,

wheresmandrmare integers. Hence

− 1 =ξm+ 1 ξm′+ 1 =(ξ+rm)(−ξ+rm)/sm^2 =(rm^2 −d)/sm^2 ,

and thusd=rm^2 +sm^2. The formulas forsmandrmshow that, ifpn/qnare the conver-
gents of

√

d,thend=x^2 +y^2 with

x=pm− 1 pm−dqm− 1 qm, y=pm^2 −dq^2 m.

Unfortunately, the equation (9) may be insoluble, even thoughdis a sum of two
squares. As an example, taked= 34 = 52 + 32. It is easily verified that the funda-
mental solution of the equationx^2 − 34 y^2 =1isx 0 =35,y 0 =6. If the equation
u^2 − 34 v^2 =−1 were soluble in integers, then, by Proposition 11, it would have a
solutionu,vsuch that 34v^2 ≤18, which is clearly impossible.
As already observed, the equation (9) has no integral solutions ifd ≡3 mod 4.
It will now be shown that (9) does have integral solutions ifd = pis prime and
p≡1 mod 4. For letx,ybe the fundamental solution of the equation (8). Since any
square is congruent to 0 or 1 mod 4, we must havey^2 ≡0andx^2 ≡1. Thusy= 2 z
for some positive integerzand

(x− 1 )(x+ 1 )= 4 pz^2.

Sincexis odd,x−1andx+1 have greatest common divisor 2. It follows that there
exist positive integersu,vsuch that

either x− 1 = 2 pu^2 ,x+ 1 = 2 v^2 or x− 1 = 2 u^2 ,x+ 1 = 2 pv^2.

In the first casev^2 −pu^2 =1, which contradicts the choice ofx,yas the funda-
mental solution of (8), sincev<x. Thus only the second case is possible and then
u^2 −pv^2 =−1. (In fact,u,vis the fundamental solution of (9).)
This proves again thatany prime p≡1mod4may be represented as a sum of
two squares,and moreover shows that an explicit construction for this representation
is provided by the continued fraction expansion of

√

p.
The representation of a primep≡1 mod 4 in the formx^2 +y^2 is actually unique,
apart from interchangingxandyand changing their signs. For suppose

x^2 +y^2 =p=u^2 +v^2 ,

wherex,y,u,vare all positive integers. Then

y^2 u^2 −x^2 v^2 =(p−x^2 )u^2 −x^2 (p−u^2 )=p(u^2 −x^2 ).

Henceyu≡εxvmodp,whereε=±1. On the other hand,

p^2 =(x^2 +y^2 )(u^2 +v^2 )=(xu+εyv)^2 +(xv−εyu)^2.