Legendre's theorem on continued fractions
ProvedFamousTheorems.legendre_continued_fraction_theoremLegendre's theorem on continued fractions. Let be a real number and a rational number in lowest terms with
Then is a convergent of the continued fraction expansion of .
So very good rational approximations are automatically convergents. The theorem is central in Diophantine approximation, and it is used in the analysis of Pell's equation, in Wiener's attack on RSA with a small private exponent, and in the classical part of Shor's factoring algorithm.
Formalization note. Mathlib's Real.exists_rat_eq_convergent. q.den is the reduced denominator of q : ℚ, and ξ.convergent n is the -th convergent of the continued fraction of .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem legendre_continued_fraction_theorem {ξ : ℝ} {q : ℚ} (h : |ξ - q| < 1 / (2 * (q.den : ℝ) ^ 2)) : ∃ n : ℕ, q = ξ.convergent n := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Real.exists_rat_eq_convergent`. Proof here reduces to that Mathlib result.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.