Math 115. A Different Proof of Theorem 7.26

Theorem. Let (x_{1}, y_{1}) be the smallest positive solution of x^{2} − dy^{2} = 1 . Then the set of all positive solutions is equal to the set

{(x_{n}, y_{n}) : n ∈ ℤ^{+}} ,

where x_{n} and y_{n} are determined by x_{n} + y_{n}\sqrt{d} = (x_{1} + y_{1}\sqrt{d})^{n}.

Proof. First note that if x, y ∈ ℤ then (x + y\sqrt{d})(x + y\sqrt{d})′ = x^{2} − dy^{2} , so (x, y) is a solution to x^{2} − dy^{2} = 1 if and only if (x + y\sqrt{d})(x + y\sqrt{d})′ = 1 .

Next, note that if (s_{1}, t_{1}) and (s_{2}, t_{2}) are arbitrary solutions to x^{2} − dy^{2} = 1 , and (s_{3}, t_{3}) is determined by (s_{1} + t_{1}\sqrt{d})(s_{2} + t_{2}\sqrt{d}) = s_{3} + t_{3}\sqrt{d}, then (s_{3}, t_{3}) is also a solution. Indeed, for i = 1, 2, 3 let α_{i} = s_{i} + t_{i}\sqrt{d}, so that α_{3} = α_{1}α_{2} . Then α_{3}α′_{3} = (α_{1}α_{2})(α_{1}α_{2})′ = (α_{1}α′_{1})(α_{2}α′_{2}) = 1 · 1 = 1 , so (s_{3}, t_{3}) is a solution.

Moreover, if (s_{1}, t_{1}) and (s_{2}, t_{2}) are positive solutions, then so is (s_{3}, t_{3}) , since s_{3} = s_{1}s_{2} + dt_{1}t_{2} > 0 and t_{3} = s_{1}t_{2} + s_{2}t_{1} > 0 .

Now the inclusion “ ⊇ ” follows by repeated application of this fact to get

(x_{n} + y_{n}\sqrt{d})(x_{n} + y_{n}\sqrt{d})′ = 1 .

Next, consider the opposite inclusion “ ⊆.”

First, note that on the curve x^{2} − dy^{2} = 1 with x > 0 and y > 0 , we have:

(i). x is an increasing function of y, because x = \sqrt{1 + dy^{2}} ; (ii). x + y\sqrt{d} is an increasing function of y; (iii). x/y is a decreasing function of y, because x/y = \sqrt{d + 1/y^{2}} ; and (iv). x/y > \sqrt{d}, because \frac{x}{y} − \sqrt{d} = ^{\frac{x−y\sqrt{d}}{y}} = \frac{1}{y(x+y\sqrt{d})} > 0 .

Now assume that the inclusion is false, and let (s, t) be the smallest positive solution not of the form (x_{n}, y_{n}) for some n. Then t > y_{1} . Let ξ = x_{1} + y_{1}\sqrt{d} and α = s + t\sqrt{d}. Since ξξ′ = 1 , we have ξ^{−1} = ξ′ = x_{1} − y_{1}\sqrt{d}. Then

αξ^{−1} = (s + t\sqrt{d})(x_{1} − y_{1}\sqrt{d}) = (sx_{1} − dty_{1}) + (tx_{1} − sy_{1})\sqrt{d} .

Accordingly, let s_{2} = sx_{1} − dty_{1} and t_{2} = tx_{1} − sy_{1} . Then (noting that (x_{1}, −y_{1}) is a solution), it follows from the above that (s_{2}, t_{2}) is a solution of x^{2} − dy^{2} = 1 . Moreover, it is a positive solution, because

s_{2} = ty_{1} (\frac{x_{1}}{y_{1}} \frac{s}{t} − d) > 0  and  t_{2} = ty_{1} (\frac{x_{1}}{y_{1}} − \frac{s}{t}) > 0

by (iv) and (iii), respectively. Finally, since ξ > 1 , we have 0 < ξ^{−1} < 1 , therefore α/ξ < α, and this implies that t_{2} < t by (iii). Then (s_{2}, t_{2}) = (x_{n}, y_{n}) for some n by the choice of (s, t) . Therefore (s, t) = (x_{n+1}, y_{n+1}) , contradicting the choice of (s, t) . □