1H (Number Theory)

Solution

θ = [a_{0}; a_{1}, a_{2}, \dots]

p_{- 1} = 1, p_{0} = a_{0}, p_{n} = a_{n} p_{n - 1} + p_{n - 2},

q_{- 1} = 0, q_{0} = 1, q_{n} = a_{n} q_{n - 1} + q_{n - 2} .

Induction using these recurrences gives

p_{n} q_{n - 1} - p_{n - 1} q_{n} = - (p_{n - 1} q_{n - 2} - p_{n - 2} q_{n - 1}) = (- 1)^{n - 1} .

In particular, consecutive convergents have coprime numerator and denominator. The standard best-approximation consequence of the same determinant identity is that, for

0 < q \leq q_{n}

and

p / q \neq = p_{n} / q_{n}

∣ qθ - p ∣ > ∣ q_{n} θ - p_{n} ∣.

Dividing by

q \leq q_{n}

gives

θ - \frac{p}{q} = \frac{∣ qθ - p ∣}{q} > \frac{∣ q _{n} θ - p _{n} ∣}{q _{n}} = θ - \frac{p _{n}}{q _{n}} .

The contrapositive proves that any strictly better approximation has

q > q_{n}

For

12

12 = 3 + (12 - 3), \frac{1}{12 - 3} = 2 + \frac{1}{12 + 3},

and the remainder then repeats. Hence

12 = [3; \overline{2, 6}] .

The convergent

[3; 2] = 7/2

supplies a solution of the Pell equation:

x = 7, y = 2, 7^{2} - 12 \cdot 2^{2} = 1.

There are no discussions about this article yet.

There are currently no matching articles.