"Use Derichlet's approximation theorem to show that if a is a real number and n is a positive integer, then there are infinitely many positive integers q for which there exists an integer p such that la-p/q|≤ 1/(q^2)."
"Use Derichlet's approximation theorem to show that if a is a real number and n is a positive integer, then there are infinitely many positive integers q for which there exists an integer p such that la-p/q|≤ 1/(q^2)."
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
100%
Last time I asked for a solution to chapter 1.1, exercise 34 (see the first image)
The question was rejected because the previous user didn’t know how to answer the question.
What is the answer to exercise 34 using Diophantine’s approximation (see second image).
Transcribed Image Text:8:55
←
REJECTED
Thursday, Jan 25, 2024
MATH ADVANCED-MATH
Consider chapter 1.1, exercise 34 of
"Elementary Number & Its Applications" by
Kenneth H. Rosen:
"Use Derichlet's approximation theorem to
show that if a is a real number and n is a
positive integer, then there are infinitely many
positive integers q for which there exists an
integer p such that |a-p/q| ≤ 1/(q^2)."
Derichlet's Approximation theorem is shown in
the first image. Exercise 34 is shown in the
second image.
Oh no! Our expert couldn't answer your
question.
Don't worry! We won't leave you hanging. Plus,
we're giving you back one question for the
√x
♂
@
Do
8
![Proof. If none of the k boxes contains more than one object, then the total number of
objects would be at most k. This contradiction shows that one of the boxes contains at
least two or more of the objects.
We now state and prove the approximation theorem, which guarantees that one of
the first n multiples of a real number must be within 1/n of an integer. The proof we
give illustrates the utility of the pigeonhole principle. (See [Ro07] for more applications
of the pigeonhole principle.) (Note that in the proof we make use of the absolute value
function. Recall that Ix, the absolute value of x, equals x if x ≥ 0 and -x if x < 0. Also
recall that x - y gives the distance between x and y.)
Theorem 1.3. Dirichler's Approximation Theorem. If is a real number and n is a
positive integer, then there exist integers a and b with 1 ≤a ≤n such that laa -b <1/n.
Proof. Consider the n+1 numbers 0, fa 12
na These n+1 numbers
are the fractional parts of the numbers ja, i=0, 1,..., n, so that 0≤ {ja} <1 for
j=0, 1,..., n. Each of these n + 1 numbers lies in one of the n disjoint intervals
0≤x≤1/n, 1/n ≤x<2/n,..., (j-1)/n <x<j/n, ..., (n-1)/n ≤x< 1. Be-
cause there are n + 1 numbers under consideration, but only n intervals, the pigeonhole
principle tells us that at least two of these numbers lie in the same interval. Because each
of these intervals has length 1/n and does not include its right endpoint, we know that
the distance between two numbers that lie in the same interval is less than 1/n. It follows
that there exist integers j and k with 0<j<k<n such that {ka}-{ja}| < 1/n. We
will now show that when a = k - j, the product aa is within 1/n of an integer, namely,
the integer b = [ka] - [ja]. To see this, note that
|aa -b|=|(k-j)a - ([ka] - [ja])]
= |(ka - [ka]) - (ja - [ja]]
= {ka}-{ja}| < 1/n.
Furthermore, note that because 0 ≤j<k≤n, we have 1 ≤a=k-j≤n. Conse-
quently, we have found integers a and b with 1≤a ≤n and lax - b] < 1/n, as desired.
■
Example 1.6. Suppose that a = √2 and n = 6. We find that 1. √2~1.414, 2-√√2
2.828,3√√24.243,4 √2~5.657, 5√27.071, and 6 √28.485. Among these
numbers 5√2 has the smallest fractional part. We see that 15 √2-71~17.071-71 =
0.0711/6. It follows that when a = √2 and n = 6, we can take a = 5 and b = 7 to
make aa-b|<1/n.
Our proof of Theorem 1.3 follows Dirichlet's original 1834 proof. Proving a stronger
version of Theorem 1.3 with 1/(n+1) replacing 1/n in the approximation is not diffi-
cult (see Exercise 32). Furthermore, in Exercise 34 we show how to use the Dirichlet
approximation theorem to show that, given an irrational number a, there are infinitely
many different rational numbers p/q such that la-p/q|<1/q², an important result in
the theory of diophantine approximation. We will return to this topic in Chapter 12.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F9acf228d-ec9e-49d8-a78a-8ceb13ba5105%2F921b7106-00b5-4b65-aefa-3284afd61db8%2Fx8s0bno_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Proof. If none of the k boxes contains more than one object, then the total number of
objects would be at most k. This contradiction shows that one of the boxes contains at
least two or more of the objects.
We now state and prove the approximation theorem, which guarantees that one of
the first n multiples of a real number must be within 1/n of an integer. The proof we
give illustrates the utility of the pigeonhole principle. (See [Ro07] for more applications
of the pigeonhole principle.) (Note that in the proof we make use of the absolute value
function. Recall that Ix, the absolute value of x, equals x if x ≥ 0 and -x if x < 0. Also
recall that x - y gives the distance between x and y.)
Theorem 1.3. Dirichler's Approximation Theorem. If is a real number and n is a
positive integer, then there exist integers a and b with 1 ≤a ≤n such that laa -b <1/n.
Proof. Consider the n+1 numbers 0, fa 12
na These n+1 numbers
are the fractional parts of the numbers ja, i=0, 1,..., n, so that 0≤ {ja} <1 for
j=0, 1,..., n. Each of these n + 1 numbers lies in one of the n disjoint intervals
0≤x≤1/n, 1/n ≤x<2/n,..., (j-1)/n <x<j/n, ..., (n-1)/n ≤x< 1. Be-
cause there are n + 1 numbers under consideration, but only n intervals, the pigeonhole
principle tells us that at least two of these numbers lie in the same interval. Because each
of these intervals has length 1/n and does not include its right endpoint, we know that
the distance between two numbers that lie in the same interval is less than 1/n. It follows
that there exist integers j and k with 0<j<k<n such that {ka}-{ja}| < 1/n. We
will now show that when a = k - j, the product aa is within 1/n of an integer, namely,
the integer b = [ka] - [ja]. To see this, note that
|aa -b|=|(k-j)a - ([ka] - [ja])]
= |(ka - [ka]) - (ja - [ja]]
= {ka}-{ja}| < 1/n.
Furthermore, note that because 0 ≤j<k≤n, we have 1 ≤a=k-j≤n. Conse-
quently, we have found integers a and b with 1≤a ≤n and lax - b] < 1/n, as desired.
■
Example 1.6. Suppose that a = √2 and n = 6. We find that 1. √2~1.414, 2-√√2
2.828,3√√24.243,4 √2~5.657, 5√27.071, and 6 √28.485. Among these
numbers 5√2 has the smallest fractional part. We see that 15 √2-71~17.071-71 =
0.0711/6. It follows that when a = √2 and n = 6, we can take a = 5 and b = 7 to
make aa-b|<1/n.
Our proof of Theorem 1.3 follows Dirichlet's original 1834 proof. Proving a stronger
version of Theorem 1.3 with 1/(n+1) replacing 1/n in the approximation is not diffi-
cult (see Exercise 32). Furthermore, in Exercise 34 we show how to use the Dirichlet
approximation theorem to show that, given an irrational number a, there are infinitely
many different rational numbers p/q such that la-p/q|<1/q², an important result in
the theory of diophantine approximation. We will return to this topic in Chapter 12.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps with 1 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
