{"history":[],"article":{"id":"b4587e40-2fb4-4724-bd89-5156371ab4f1","title":"Dirichlet's approximation theorem","slug":"dirichlet-s-approximation-theorem","content":":::summary\n:::\n\n# \nIn [number theory](https://bliptext.com/articles/number-theory), **Dirichlet's theorem on Diophantine approximation**, also called **Dirichlet's approximation theorem**, states that for any [real numbers](https://bliptext.com/articles/real-numbers) \\alpha and N, with 1 \\leq N, there exist integers p and q such that and\nHere represents the [integer part](https://bliptext.com/articles/integer-part) of N. This is a fundamental result in [Diophantine approximation](https://bliptext.com/articles/diophantine-approximation), showing that any real number has a sequence of good rational approximations: in fact an immediate consequence is that for a given irrational α, the inequality\nis satisfied by infinitely many integers p and q.\nThis shows that any irrational number has [irrationality measure](https://bliptext.com/articles/irrationality-measure) at least 2.\nThe [Thue–Siegel–Roth theorem](https://bliptext.com/articles/thue-siegel-roth-theorem) says that, for algebraic irrational numbers, the exponent of 2 in the corollary to Dirichlet’s approximation theorem is the best we can do: such numbers cannot be approximated by any exponent greater than 2.\nThe Thue–Siegel–Roth theorem uses advanced techniques of number theory, but many simpler numbers such as the [golden ratio](https://bliptext.com/articles/golden-ratio) can be much more easily verified to be inapproximable beyond exponent 2.\n\n# Simultaneous version\nThe simultaneous version of the Dirichlet's approximation theorem states that given real numbers and a natural number N then there are integers such that\n\n# Method of proof\n\n## Proof by the pigeonhole principle\nThis theorem is a consequence of the [pigeonhole principle](https://bliptext.com/articles/pigeonhole-principle).\n[Peter Gustav Lejeune Dirichlet](https://bliptext.com/articles/peter-gustav-lejeune-dirichlet) who proved the result used the same principle in other contexts (for example, the [Pell equation](https://bliptext.com/articles/pell-equation)) and by naming the principle (in German) popularized its use, though its status in textbook terms comes later.\nThe method extends to simultaneous approximation.\n**Proof outline**: Let \\alpha be an irrational number and n be an integer.\nFor every we can write such that m_k is an integer and 0\\le x_k <1.\nOne can divide the interval [0, 1) into N smaller intervals of measure \\frac{1}{N}. Now, we have N+1 numbers and N intervals. Therefore, by the pigeonhole principle, at least two of them are in the same interval. We can call those x_i,x_j such that i < j. Now:\nDividing both sides by j-i will result in:\nAnd we proved the theorem.\n\n## Proof by Minkowski's theorem\nAnother simple proof of the Dirichlet's approximation theorem is based on [Minkowski's theorem](https://bliptext.com/articles/minkowski-s-theorem) applied to the set\nSince the volume of S is greater than 4, [Minkowski's theorem](https://bliptext.com/articles/minkowski-s-theorem) establishes the existence of a non-trivial point with integral coordinates.\nThis proof extends naturally to simultaneous approximations by considering the set\n\n# Related theorems\n\n## Legendre's theorem on continued fractions\nIn his Essai sur la théorie des nombres (1798), [Adrien-Marie Legendre](https://bliptext.com/articles/adrien-marie-legendre) derives a necessary and sufficient condition for a rational number to be a convergent of the [simple continued fraction](https://bliptext.com/articles/simple-continued-fraction) of a given real number.\nA consequence of this criterion, often called **Legendre's theorem** within the study of continued fractions, is as follows:\n**Theorem**.\nIf α is a real number and p, q are positive integers such that, then p/q is a convergent of the continued fraction of α.\n**Proof**.\nWe follow the proof given in [An Introduction to the Theory of Numbers](https://bliptext.com/articles/an-introduction-to-the-theory-of-numbers) by [G. H. Hardy](https://bliptext.com/articles/g-h-hardy) and [E. M. Wright](https://bliptext.com/articles/e-m-wright).\nSuppose α, p, q are such that, and assume that α > p/q.\nThen we may write, where 0 < θ < 1/2.\nWe write p/q as a finite continued fraction [a0; a1, ..., an], where due to the fact that each rational number has two distinct representations as finite continued fractions differing in length by one (namely, one where an = 1 and one where an ≠ 1), we may choose n to be even.\n(In the case where α < p/q, we would choose n to be odd.)\nLet p0/q0, ..., pn/qn = p/q be the convergents of this continued fraction expansion.\nSet, so that and thus, where we have used the fact that pn-1 qn - pn qn-1 = (-1)n and that n is even.\nNow, this equation implies that α = [a0; a1, ..., an, ω].\nSince the fact that 0 < θ < 1/2 implies that ω > 1, we conclude that the continued fraction expansion of α must be [a0; a1, ..., an, b0, b1, ...], where [b0; b1, ...] is the continued fraction expansion of ω, and therefore that pn/qn = p/q is a convergent of the continued fraction of α.\nThis theorem forms the basis for [Wiener's attack](https://bliptext.com/articles/wiener-s-attack), a polynomial-time exploit of the [RSA cryptographic protocol](https://bliptext.com/articles/rsa-cryptosystem) that can occur for an injudicious choice of public and private keys (specifically, this attack succeeds if the prime factors of the public key n = pq satisfy p < q < 2p and the private key d is less than (1/3)n1/4).","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T22:26:26.559Z","updated_at":"2025-01-25T22:26:26.559Z","search_vector":"'approxim':3 'dirichlet':1 'theorem':4","search_content":" \n \n\n# \nIn [number theory](https://bliptext.com/articles/number-theory), **Dirichlet's theorem on Diophantine approximation**, also called **Dirichlet's approximation theorem**, states that for any [real numbers](https://bliptext.com/articles/real-numbers) \\alpha and N, with 1 \\leq N, there exist integers p and q such that and\nHere represents the [integer part](https://bliptext.com/articles/integer-part) of N. This is a fundamental result in [Diophantine approximation](https://bliptext.com/articles/diophantine-approximation), showing that any real number has a sequence of good rational approximations: in fact an immediate consequence is that for a given irrational α, the inequality\nis satisfied by infinitely many integers p and q.\nThis shows that any irrational number has [irrationality measure](https://bliptext.com/articles/irrationality-measure) at least 2.\nThe [Thue–Siegel–Roth theorem](https://bliptext.com/articles/thue-siegel-roth-theorem) says that, for algebraic irrational numbers, the exponent of 2 in the corollary to Dirichlet’s approximation theorem is the best we can do: such numbers cannot be approximated by any exponent greater than 2.\nThe Thue–Siegel–Roth theorem uses advanced techniques of number theory, but many simpler numbers such as the [golden ratio](https://bliptext.com/articles/golden-ratio) can be much more easily verified to be inapproximable beyond exponent 2.\n\n# Simultaneous version\nThe simultaneous version of the Dirichlet's approximation theorem states that given real numbers and a natural number N then there are integers such that\n\n# Method of proof\n\n## Proof by the pigeonhole principle\nThis theorem is a consequence of the [pigeonhole principle](https://bliptext.com/articles/pigeonhole-principle).\n[Peter Gustav Lejeune Dirichlet](https://bliptext.com/articles/peter-gustav-lejeune-dirichlet) who proved the result used the same principle in other contexts (for example, the [Pell equation](https://bliptext.com/articles/pell-equation)) and by naming the principle (in German) popularized its use, though its status in textbook terms comes later.\nThe method extends to simultaneous approximation.\n**Proof outline**: Let \\alpha be an irrational number and n be an integer.\nFor every we can write such that m_k is an integer and 0\\le x_k p/q.\nThen we may write, where 0 1, we conclude that the continued fraction expansion of α must be [a0; a1, ..., an, b0, b1, ...], where [b0; b1, ...] is the continued fraction expansion of ω, and therefore that pn/qn = p/q is a convergent of the continued fraction of α.\nThis theorem forms the basis for [Wiener's attack](https://bliptext.com/articles/wiener-s-attack), a polynomial-time exploit of the [RSA cryptographic protocol](https://bliptext.com/articles/rsa-cryptosystem) that can occur for an injudicious choice of public and private keys (specifically, this attack succeeds if the prime factors of the public key n = pq satisfy p < q < 2p and the private key d is less than (1/3)n1/4).","revisionCount":0},"hasMore":false,"nextCursor":null}

History