Euclidean Algorithms and Congruences
Continued Fraction Expansion of Real Numbers
Continued fractions, convergents as best rational approximations, and the periodic expansion of quadratic irrationals.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0517
Continued fractions are the Euclidean algorithm applied to real numbers. They produce the best rational approximations available for a given denominator, and for quadratic irrationals they become periodic — which is the key to real quadratic field computation.
The expansion
Computing the expansion
- Take integer partThe floor of the current value is the next partial quotient.
- SubtractRemove the integer part, leaving a value in the unit interval.
- InvertTake the reciprocal and repeat.
Convergents
Truncating the expansion gives the convergents, computed by a simple recurrence on numerators and denominators.
Quadratic irrationals
The expansion of a quadratic irrational is eventually periodic, and for the square root of a non-square integer it is purely periodic after the first term with a palindromic structure.
| Property | Consequence |
|---|---|
| Periodicity | The expansion can be computed and stored exactly |
| Palindromic period | Halves the work; the second half mirrors the first |
| Period end detection | Signals a solution to the Pell equation |
| Convergents at period end | Give the fundamental unit of the real quadratic field |
Precision
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.3.5. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.