Number Theory: Lecture 19

In which we explore infinite continued fractions.

Definition of convergents.
Definition of sequences $p_n$ and $q_n$ .
Lemma 58: For $n \geq 0$ , we have $\frac{p_n}{q_n} = [a_0, a_1, \dotsc, a_n]$ . That is, $\frac{p_n}{q_n}$ is equal to the $n^{\textrm{th}}$ convergent. We proved this by induction, using the fact that $[a_0, a_1, \dotsc, a_n, a_{n+1}] = [a_0, a_1, \dotsc, a_n + \frac{1}{a_{n+1}}]$ .
Lemma 59: For $n \geq 1$ , we have $p_n q_{n-1} - p_{n-1} q_n = (-1)^{n+1}$ . This was an easy induction.
Lemma 60: For $n \geq 0$ , if $a_0$ , $a_1$ , $a_2$ , …, $a_n$ are integers, then the terms $p_n$ and $q_n$ are coprime integers. This follows immediately from the previous lemma.
We reminded ourselves that if we are to find a continued fraction for the irrational number $\theta$ , then we must have $a_0 = \lfloor \theta \rfloor$ , and $\alpha_1 = \frac{1}{\theta - a_0}$ , and $a_i = \lfloor \alpha_i \rfloor$ and $\alpha_{i+1} = \frac{1}{\alpha_i - a_i}$ for $i \geq 1$ .
Proposition 61: The convergents converge. That is, if we define $a_i$ and $p_n$ and $q_n$ as above, then the sequence $[a_0]$ , $[a_0, a_1]$ , $[a_0, a_1, a_2]$ , … converges to $\theta$ . We proved this by using Lemma 58 to show that $\theta = \frac{\alpha_{n+1} p_n + p_{n-1}}{\alpha_{n+1} q_n + q_{n-1}}$ , and then computing $| \theta - \frac{p_n}{q_n} |$ .
Lemma 62: We have $\frac{1}{q_{n+2}} \leq |q_n \theta - p_n | \leq \frac{1}{q_{n+1}}$ for all $n \geq 0$ , and so we also have $| q_n \theta - p_n| \leq | q_{n-1} \theta - p _{n-1}|$ for $n \geq 1$ . We used the expression we obtained for $| \theta - \frac{p_n}{q_n}|$ in the previous result, together with a couple of easy estimates using the recurrence for $q_n$ .

Preparation for Lecture 20

We’ve seen that continued fractions give a sequence of rational numbers that converge to a given real number (namely the convergents). Next time we’ll consider these as rational approximations of that real number. I suggest that you compute some convergents (for some examples that we haven’t seen in lectures), to see whether they give good approximations. How do they compare with the rational approximations arising from truncating decimal expansions?

Next time we’ll see that in some sense the best rational approximations come from continued fractions. You could usefully think about how we might formulate that result in a precise way (and, of course, how we might prove it).

We are then going to turn our attention to the Diophantine equation $x^2 - N y^2 = 1$ (where $N$ is a fixed integer that isn’t a square, and where we are looking for integer solutions $x$ and $y$ ). Can you find some solutions when $N = 2$ or $N = 3$ , for example? It would be good to get a feeling for whether there are no solutions, some but only finitely many solutions, or infinitely many solutions, for different values of $N$ .

(And what happens to the equation $x^2 - N y^2 = 1$ when $N$ is a square? Why have I ruled out that case above?)

Like this:

Be the first to like this post.

This entry was posted on November 18, 2011 at 12:04 pm and is filed under Cambridge Maths Tripos, II Number Theory, Lecture. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Number Theory: Lecture 19”

Number Theory: Lecture 24 « Theorem of the week Says:
November 30, 2011 at 12:11 pm
[...] Lemma 76: Let be a convergent to . Then , and moreover we have . (The angle bracket notation is the same as that introduced in Lecture 7). We proved this using our upper bound on , which in turn we proved in Lecture 19. [...]

Theorem of the week