Continued fractions and Diophantine equations · Definition

Convergent of a continued fraction

elementary number theorycontinued fractions and diophantine equations

Before you start you need to know

Convergents are the best way to approximate an irrational number by fractions with small denominators. They are computed recursively from the partial quotients.

Definition

A convergent of a continued fraction \( [a_0; a_1, a_2, \ldots] \) is the rational number \( p_n/q_n \) obtained by truncating the expansion at the term \( a_n \).

\[\frac{p_n}{q_n}=[a_0;a_1,\ldots,a_n],\quad p_n=a_np_{n-1}+p_{n-2},\\q_n=a_nq_{n-1}+q_{n-2}\]

The numerators and denominators satisfy the recurrences \( p_n=a_np_{n-1}+p_{n-2} \) and \( q_n=a_nq_{n-1}+q_{n-2} \), with initial values \( p_{-1}=1, p_{-2}=0, q_{-1}=0, q_{-2}=1 \). Moreover, \( p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1} \), so each convergent is in lowest terms. Convergents of even index are less than the value of the fraction, and those of odd index are greater.

For \( \sqrt{2}=[1;2,2,2,\ldots] \), the first convergents are computed with \( p_0=1, q_0=1 \), \( p_1=3, q_1=2 \), and \( p_2=7, q_2=5 \). Thus \( 7/5 \) approximates \( \sqrt{2} \) with an error less than \( 0.02 \).

A typical mistake is forgetting the initial values of the recurrences and starting with \( p_0=a_0 \) without defining \( p_{-1} \) and \( q_{-1} \), which produces incorrect denominators. Another common error is assuming that every convergent is greater than the true value of the continued fraction.

Think about it

Why are the convergents of even index less than the value of the continued fraction?

Because \( x-p_n/q_n \) has the sign of \( (-1)^n \), so even-index convergents lie below \( x \).

Exercises 10

  1. What is the convergent \( p_0/q_0 \) of the continued fraction \( [3;7,16] \)?
  2. What is the value of \( q_1 \) for the continued fraction \( [2;5,4] \)?
  3. What is the convergent \( p_1/q_1 \) of \( [0;1,2,3] \)?
  4. What is the convergent \( p_2/q_2 \) of \( [1;2,2] \)?
  5. What is the value of \( p_1 \) for the continued fraction \( [4;3,2] \)?
  6. Compute the convergent \( p_2/q_2 \) of the continued fraction \( [1;3,2,4] \).
  7. If \( [0;2,3,4] \) has convergents \( p_n/q_n \), what is \( q_3 \)?
  8. What is the value of \( p_3/q_3 \) for \( [2;1,1,2] \)?
  9. For \( [0;1,4,2] \), what is the convergent \( p_3/q_3 \)?
  10. Let \( x=[0;1,2,3,4] \). Compute \( p_4/q_4 \) and determine which option is that convergent.

What comes next

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 15
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 7