Math 115. Slides from the Lecture of December 3

Periodic Continued Fractions (continued)

Lemma. Let ξ ∈ ℝ, k ∈ ℤ, and θ = ξ + k. Then (a). θ − [θ] = ξ − [ξ] , and

(b). If ξ = ⟨a_{0}, a_{1}, a_{2}, … ⟩, then θ = ⟨a_{0} + k, a_{1}, a_{2}, … ⟩.

Proof. Part (a) follows easily from the identity [ξ + k] = [ξ] + k.

Part (b) follows from the above identity and part (a), since ξ_{1} is the same for both ξ and θ:

\frac{1}{ξ − [ξ]} = \frac{1}{θ − [θ]} .

□

Last time: Let d be a positive integer, not a perfect square. Then \sqrt{d} + [\sqrt{d}] is purely periodic.

Also recall that ξ_{i} = \frac{m_{i} + \sqrt{d}}{q_{i}} .

Proposition. Write

\sqrt{d} + [\sqrt{d}] = ⟨\overline{a_{0}, a_{1}, …, a_{r−1}}⟩ ,

with r minimal. Then q_{i} ≠ 1 for all 0 < i < r, and q_{i} = −1 never occurs.

Proof. If q_{i} = 1 then ξ_{i} = m_{i} + \sqrt{d}, so by part (a) of the earlier lemma,

ξ_{i+1} = \frac{1}{ξ_{i} − [ξ_{i}]} = \frac{1}{m_{i} + \sqrt{d} − [m_{i} + \sqrt{d}]} = \frac{1}{[\sqrt{d}] + \sqrt{d} − [[\sqrt{d}] + \sqrt{d}]} = ξ_{1} .

Therefore, going r − 1 steps forward gives

ξ_{i} = ξ_{i+r} = ξ_{i+1+(r−1)} = ξ_{1+(r−1)} = ξ_{r} = \sqrt{d} + [\sqrt{d}] .

But if 0 < i < r, then we would have \sqrt{d} + [\sqrt{d}] = ⟨\overline{a_{0}, a_{1}, …, a_{i−1}}⟩, with i < r, contradicting the choice of r.

As for q_{i} = −1 , all of the ξ_{i} are purely periodic, so q_{i} < 0 would imply ξ_{i} > ξ′_{i}, contradicting Theorem 7.20. □

Since q_{0} = q_{r} = 1 , we have that q_{i} = 1 if and only if i is a multiple of r.

Now note that a_{0} = [\sqrt{d} + [\sqrt{d}]] = [\sqrt{d}] + [\sqrt{d}] = 2[\sqrt{d}] . So, replacing a_{0} with [\sqrt{d}] , we have

\sqrt{d} + [\sqrt{d}] = ⟨\overline{2a_{0}, a_{1}, a_{2}, …, a_{r−1}}⟩ = ⟨2a_{0}, \overline{a_{1}, a_{2}, …, a_{r−1}, 2a_{0}}⟩

and therefore, by the lemma,

\sqrt{d} = ⟨a_{0}, \overline{a_{1}, a_{2}, …, a_{r−1}, 2a_{0}}⟩ .

Again, we have q_{i} = 1 if and only if r | i, and q_{i} = −1 never occurs.

Pell’s Equation (known already in ancient India)

Consider the equation

x^{2} − dy^{2} = N ,

where d, N ∈ ℤ are fixed and we are looking for solutions in integers x, y. If d ≤ 0 , then |x| ≤ \sqrt{N} , which is easy to solve. If d = m^{2} is a perfect square, then x^{2} − dy^{2} = (x + my)(x − my) , again leading

to an equation which is easy to solve.

So from now on we assume that d is a positive integer, not a perfect square. Finding all solutions with x = 0 or y = 0 is easy. All other solutions come in

fours: (±x, ±y) .

Therefore we concentrate on positive solutions, in which x > 0 and y > 0 . Theorem 7.21. With h_{i}, k_{i}, ξ_{i}, q_{i}, m_{i}, and d as usual, we have

h_{n−1}^{2} − dk_{n−1}^{2} = (−1)^{n}q_{n} for all n ≥ 0 .

Proof (sketch). The equation

\sqrt{d} = ξ = \frac{ξ_{n}h_{n−1} + h_{n−2}}{ξ_{n}k_{n−1} + k_{n−2}} = \frac{(m_{n} + \sqrt{d})h_{n−1} + q_{n}h_{n−2}}{(m_{n} + \sqrt{d})k_{n−1} + q_{n}k_{n−2}}

leads to

\sqrt{d}(m_{n}k_{n−1} + q_{n}k_{n−2} − h_{n−1}) + (dk_{n−1} − m_{n}h_{n−1} + q_{n}h_{n−2}) = 0 .

Letting A = m_{n}k_{n−1} + q_{n}k_{n−2} − h_{n−1} and B = dk_{n−1} − m_{n}h_{n−1} + q_{n}h_{n−2} , we see that A = B = 0 (since A, B ∈ ℤ and \sqrt{d} is irrational). Eliminating m_{n} from these two equations gives

q_{n}(h_{n−1}k_{n−2} − k_{n−1}h_{n−2}) = h_{n−1}^{2} − dk_{n−1}^{2} ,

which gives the theorem because h_{n−1}k_{n−2} − k_{n−1}h_{n−2} = (−1)^{n}. □ Theorem. If |N| < \sqrt{d} then every positive solution to x^{2} −dy^{2} = N equals (gh_{n}, gk_{n})

for some g ∈ ℤ_{>0} , n ≥ 0 . Proof (even more sketchy). Reduce to Theorem 7.14, which says that if a, b ∈ ℤ_{>0} and |\frac{a}{b} − ξ| < \frac{1}{2b^{2}} , then a/b is a convergent. □