Math 620  Problem Set #9  Due Wed., Nov. 14, 2001

1. For d = 2, 3, 5, 11, 13:

a) Find all solutions to x^{2} − dy^{2} = ±1.

b) Find all units in O_{K}, where K = ℚ(\sqrt{d}).

c) Do all the units in O_{K} “come from” the continued fraction expansion for \sqrt{d}? (Here, if α = \frac{p}{2} + \frac{q}{2} \sqrt{d} is a unit in O_{K} with p, q odd integers, we count α as coming from the continued fraction convergent p/q.)

d) More generally, for which positive square-free integers d do all units in O_{ℚ(\sqrt{d})} come from the continued fraction expansion for \sqrt{d}?

2. a) Let a/b and c/d be consecutive Farey fractions in some Farey sequence F_{n}, and suppose that a/b < x < c/d.

(i) Show that either |\frac{a}{b}−x| < \frac{1}{2b^{2}} or |\frac{c}{d}−x| < \frac{1}{2d^{2}} . [Hint: If not, consider |\frac{c}{d}−x|+|x−\frac{a}{b}| and use Problem Set 4 #2c.]

(ii) Let e/f be a rational number between a/b and c/d. Show that if b < d, if e/f < x, and if e/f and c/d are consecutive Farey fractions in some Farey sequence F_{m} (for some m > n), then |a − bx| > |c − dx|. Show an analogous assertion in the case that b > d. [Hint: In the first case, show that |a − bx| > \frac{1}{f} > |c − dx| using Problem Set 4 #2c.]

b) Consider two consecutive continued fraction convergents to a real number x. Deduce that at least one of them is a rational number p/q such that |\frac{p}{q} − x| < \frac{1}{2q^{2}} , and also that |p_{n+1} − q_{n+1}x| < |p_{n} − q_{n}x|. [Hint: Use part (a) and Problem Set 5 #2d.]

3. Let d be a positive square-free integer, let [a_{1}, a_{2}, …] be the continued fraction expansion of \sqrt{d}, and for every n ≥ 1 let p_{n}/q_{n} be the continued fraction convergents to \sqrt{d} and let α_{n} = [a_{n}, a_{n+1}, …].

a) Show that \sqrt{d} = (p_{n−1}α_{n} + p_{n−2})/(q_{n−1}α_{n} + q_{n−2}) for all n. [Hint: Problem Set 5 # 2a.]

b) Explicitly find rational numbers r_{n}, s_{n} such that α_{n} = (\sqrt{d} + r_{n})/s_{n}, for each n. [Hint: Rationalize the denominators in (a), and use Problem Set 5 # 2b to simplify the expression.] Show that these are the unique values of r_{n}, s_{n} ∈ ℚ that satisfy this relation. Show also that r_{n}, s_{n} ∈ ℤ.

c) Show that the sequences {r_{n}}, {s_{n}} are each periodic. What are the periods? [Hint: Is {a_{n}} periodic? Is {α_{n}}?]

d) Deduce that the sequence {p_{n}^{2} − dq_{n}^{2}} is periodic, and find the period.

4. Let S_{m,n} be the square in ℝ^{2} having vertices (2m, 2n), (2m + 2, 2n), (2m, 2n + 2), (2m + 2, 2n + 2). Thus S_{m,n} may be carried onto S_{0,0} by translation. Suppose that K is a symmetric convex closed set with area > 4 (cf. Problem Set 8 #5).

a) Show that after translation, there are two points of K which must overlap.

b) Deduce that there are distinct points v, w ∈ K with v − w = (2m, 2n) for some m, n ∈ ℤ.

c) Deduce that there are distinct points v, w ∈ K with v + w = (2m, 2n) for some m, n ∈ ℤ.

d) Conclude that K must contain a lattice point.