Continued fractions and Diophantine equations · Definition

Continued fraction

elementary number theorycontinued fractions and diophantine equations

Before you start you need to know

Continued fractions represent rational and irrational numbers through a sequence of integers. They are closely tied to the Euclidean algorithm.

Definition

A continued fraction is an expression of the form a₀ + 1/(a₁ + 1/(a₂ + ...)), where a₀ is an integer and the remaining terms aᵢ are positive integers.

\[x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}}\]

Every rational number \( p/q \) has a finite representation as a continued fraction, obtained by applying the Euclidean algorithm to \( p \) and \( q \) and taking the quotients as the terms \( a_i \). The convergents \( p_n/q_n \) satisfy the recurrences \( p_n = a_n p_{n-1} + p_{n-2} \) and \( q_n = a_n q_{n-1} + q_{n-2} \), and they alternate around the exact value. Irrational numbers have infinite expansions, and quadratic irrationals are exactly those with periodic ones.

For \( 415/93 \) the Euclidean algorithm gives quotients 4, 2, 6, 7, so \( 415/93 = [4; 2, 6, 7] \). Computing the convergents with the recurrences yields \( 4/1, 9/2, 58/13, 415/93 \), and the last one matches the original value. The continued fraction thus recovers the starting rational exactly.

A common mistake is forgetting that the last quotient of the Euclidean algorithm can be written either as \( a_n \) or as \( a_n - 1 \) followed by a 1, which gives two different representations of the same number. Another frequent error is reversing the order of the terms when building the expression from the end toward the beginning.

Think about it

Why do the even-indexed convergents lie below the value of \( x \)?

Because they alternate around \( x \): even-indexed ones are smaller and odd-indexed ones are larger.

Exercises 10

  1. What is the term \( a_0 \) of the continued fraction of \( 415/93 \)?
  2. What is the value of the rational \( [2; 3] \)?
  3. How many terms does the continued fraction of \( 415/93 \) have according to the Euclidean algorithm?
  4. Which rational number does the continued fraction \( [1; 1] \) represent?
  5. What is the term \( a_1 \) of the continued fraction of \( 415/93 \)?
  6. Compute the convergent \( p_1/q_1 \) of the continued fraction \( [4; 2, 6, 7] \).
  7. Compute the convergent \( p_2/q_2 \) of the continued fraction \( [4; 2, 6, 7] \).
  8. What is the value of \( [0; 1, 2] \)?
  9. Write the continued fraction of \( 27/11 \) using the Euclidean algorithm.
  10. Let \( x = [1; 2, 2, 2] \). Compute \( x \) as a rational number and check that the convergent \( p_2/q_2 \) approximates it from below.

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