Homework Help is Here – Start Your Trial Now!
Math
Advanced Math
1. Use the fundamental theorem of arithmetic to show that every integer n > 2 can be written as a product n = s.r², where s, r > 1 are integers and s is square-free. We call this the square-free factorization. 2. For example, the square-free factorization of 8 = 2 · (2)² (s = 2, r = 2) and of 600 = 6 · 102 (s = 6, r = 10.) Find the square-free factorization of 72 and 2366. 3. Define S(N) = The number of squares between 1 and N F(N)= The number of square-free numbers between 1 and N What is S(4), S(25) and S(49)? F(6) and F(50)?

1. Use the fundamental theorem of arithmetic to show that every integer n > 2 can be written as a product n = s.r², where s, r > 1 are integers and s is square-free. We call this the square-free factorization. 2. For example, the square-free factorization of 8 = 2 · (2)² (s = 2, r = 2) and of 600 = 6 · 102 (s = 6, r = 10.) Find the square-free factorization of 72 and 2366. 3. Define S(N) = The number of squares between 1 and N F(N)= The number of square-free numbers between 1 and N What is S(4), S(25) and S(49)? F(6) and F(50)?

Advanced Engineering Mathematics
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
See similar textbooks
icon
Related questions
Question
100%
A lower bound for II(N). In this question we will prove that there are infinitely many primes by examining the prime counting function II(N), where II(N) = The number of primes between 2 and N We say that a natural number n > 2 is square-free if it is not divisible by a square. For example, 6 is square-free, but 8 is not, since it is divisible by 4 = 22. 1. Use the fundamental theorem of arithmetic to show that every integer n > 2 can be written as a product n = s·r², where s, r > 1 are integers and s is square-free. We call this the square-free factorization. 2. For example, the square-free factorization of 8 = 2 · (2)² (s = 2,r = 2) and of 600 = 6 · 102 (s = 6,r = 10.) Find the square-free factorization of 72 and 2366. 3. Define S(N) = The number of squares between 1 and N F(N) = The number of square-free numbers between 1 and N What is S(4), S(25) and S(49)? F(6) and F(50)? 4. In part 1, we showed that every positive integer factors uniquely as a product of a square and square-free number. Use this to conclude that N< S(N) · F(N). In the next parts we'll overestimate both S(N) and F(N). 5. Show that S(N)< /N for every N > 1. 6. Show that F(N) < 2!(N). (Hint: every square free-number smaller than N of the form q1 · q2 · ... · ¶k where the q¡ are distinct primes smaller than N.) 7. Now using 4, 5, and 6, we have N < VN · 2(N). Get II(N) by itself on the right-hand side of this inequality. 8. Take the limit from the solved inequality in 6 to conclude that limN→ II(N) = ∞ and hence that there are infinitely many primes. 9. Using part 6, what's the smallest N guaranteed to have 500 primes smaller than it? 10. What additional information does this proof provide that Euclid's doesn't? This proof is due to Paul Erdos. There is a good documentary about him available to watch by clicking here. Note that square/square-free numbers appear in the Elements.
Transcribed Image Text:A lower bound for II(N). In this question we will prove that there are infinitely many primes by examining the prime counting function II(N), where II(N) = The number of primes between 2 and N We say that a natural number n > 2 is square-free if it is not divisible by a square. For example, 6 is square-free, but 8 is not, since it is divisible by 4 = 22. 1. Use the fundamental theorem of arithmetic to show that every integer n > 2 can be written as a product n = s·r², where s, r > 1 are integers and s is square-free. We call this the square-free factorization. 2. For example, the square-free factorization of 8 = 2 · (2)² (s = 2,r = 2) and of 600 = 6 · 102 (s = 6,r = 10.) Find the square-free factorization of 72 and 2366. 3. Define S(N) = The number of squares between 1 and N F(N) = The number of square-free numbers between 1 and N What is S(4), S(25) and S(49)? F(6) and F(50)? 4. In part 1, we showed that every positive integer factors uniquely as a product of a square and square-free number. Use this to conclude that N< S(N) · F(N). In the next parts we'll overestimate both S(N) and F(N). 5. Show that S(N)< /N for every N > 1. 6. Show that F(N) < 2!(N). (Hint: every square free-number smaller than N of the form q1 · q2 · ... · ¶k where the q¡ are distinct primes smaller than N.) 7. Now using 4, 5, and 6, we have N < VN · 2(N). Get II(N) by itself on the right-hand side of this inequality. 8. Take the limit from the solved inequality in 6 to conclude that limN→ II(N) = ∞ and hence that there are infinitely many primes. 9. Using part 6, what's the smallest N guaranteed to have 500 primes smaller than it? 10. What additional information does this proof provide that Euclid's doesn't? This proof is due to Paul Erdos. There is a good documentary about him available to watch by clicking here. Note that square/square-free numbers appear in the Elements.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 4 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Relations
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, advanced-math and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
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…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,
SEE MORE TEXTBOOKS