Homework Help is Here – Start Your Trial Now!
Math
Advanced Math
Theorem 4.6 (Fundamental Theorem of Arithmetic) Every positive integer n can be written as the product of prime numbers n = P1 P2 Pr. unique up to (The pi's can repeat.) Furthermore, this product representation changing the order of the factors.

Theorem 4.6 (Fundamental Theorem of Arithmetic) Every positive integer n can be written as the product of prime numbers n = P1 P2 Pr. unique up to (The pi's can repeat.) Furthermore, this product representation changing the order of the factors.

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%

it's hard to understand this theory , would you explain in in simple way 

CTheorem 4.6 (Fundamental Theorem of Arithmetic) Every positive integer n can be written as the product of prime numbers n = Pip2· · Pr. (The pi's can repeat.) Furthermore, this product representation is unique up to changing the order of the factors. Proof There are two things we need to show: the existence and the uniqueness of a prime factorization. Let us start with existence: given a positive integer n, we must show that it has at least one representation as a product of prime numbers. We do this by induction on n, with the base case n =1 being the empty product: the product of no primes is equal to 1. Let us now suppose that all positive integers less than n can be written as a product of primes, and we will show that n can be so written as well. If n is itself prime, then it is a product of just n alone, and there is nothing left to prove. Otherwise, if n is composite, then it has some factor m with 1 < m < n, and we let r = n/m, so that n = mr. Because 1 < m, r < n, the induction hypothesis guarantees that both m and r can be written as products of primes, say as m = P1· Pk» r = q1· · · qe• Then, we have n = Pi ·…· Pkqi• • • ¶e, so we have just written n as a product of primes. This completes the proof of existence.
Transcribed Image Text:CTheorem 4.6 (Fundamental Theorem of Arithmetic) Every positive integer n can be written as the product of prime numbers n = Pip2· · Pr. (The pi's can repeat.) Furthermore, this product representation is unique up to changing the order of the factors. Proof There are two things we need to show: the existence and the uniqueness of a prime factorization. Let us start with existence: given a positive integer n, we must show that it has at least one representation as a product of prime numbers. We do this by induction on n, with the base case n =1 being the empty product: the product of no primes is equal to 1. Let us now suppose that all positive integers less than n can be written as a product of primes, and we will show that n can be so written as well. If n is itself prime, then it is a product of just n alone, and there is nothing left to prove. Otherwise, if n is composite, then it has some factor m with 1 < m < n, and we let r = n/m, so that n = mr. Because 1 < m, r < n, the induction hypothesis guarantees that both m and r can be written as products of primes, say as m = P1· Pk» r = q1· · · qe• Then, we have n = Pi ·…· Pkqi• • • ¶e, so we have just written n as a product of primes. This completes the proof of existence.
m = 9192 · · · 9s – P192 · · · s =n – pi(q2 · · · 4s) = P1P2•·· Pr – P192 ·· · 92 = pi(P2 ·.· Pr – 92 ·· · ¶s). The second term w = P2 · · · P, – 92 ··· ¶s is positive, because it is n/p1–n/qq and Pi < q1. Thus the prime factorization of m is på times the prime factorization of w, and thus pi occurs in the (unique) prime factorization of m. Now, let us look at the factor q1 – Pı of m. If q1 – Pi = 1, then the prime factorization of m would contain only q2, ..., qs. But we just showed that it contains P1, and we already know that p¡ is not one of the q ;'s. Thus q1 – Pj cannot be 1. Since q1 – Pi <n as well, q1 – p1 has unique prime factorization, and the factorization must contain a p1, so let us suppose that q1 u. Then q1 – Pi = pju, so q̟ = pi (u + 1), i.e., q¡ is divisible by p1. But this is impossible, since qi is prime, and primes cannot have other prime factors. This is our final contradiction, which completes the proof of uniqueness in the Fundamental Theorem of Arithmetic. Pi = Piu for some positive integer We now show that the prime factorization is unique. Let us suppose not, and that some number n has at least two prime factorizations, and furthermore that n is the smallest positive integer with this property. We write these two factorizations as n = Pi · ·· Pr =q1•·¶s» ... where some of the primes might be repeated. Now, if some p; is equal to some q;, then we have n/ p; = n/qj, and this number also has at least two prime factorizations obtained by omitting p; from the first factorization and q; from the second. However, n/p; is smaller than n, contradicting our assumption that n is the smallest positive integer with at least two prime factorizations. Thus we may assume that the list of pi's and the list of q;'s share no common primes. Let us assume, without loss of generality, that p1 < q1. (If not, then switch the Pi's and the q;'s.) Consider the number m = (qı – pi)q2·… ¶s• %3D Since q1 – Pi < qı, it follows that m < n, so m has unique prime factorization, and this factorization is (whatever the factorization of q1 – pi is) times the product of the rest of the q;'s. If we expand the product for m, we find that
Transcribed Image Text:m = 9192 · · · 9s – P192 · · · s =n – pi(q2 · · · 4s) = P1P2•·· Pr – P192 ·· · 92 = pi(P2 ·.· Pr – 92 ·· · ¶s). The second term w = P2 · · · P, – 92 ··· ¶s is positive, because it is n/p1–n/qq and Pi < q1. Thus the prime factorization of m is på times the prime factorization of w, and thus pi occurs in the (unique) prime factorization of m. Now, let us look at the factor q1 – Pı of m. If q1 – Pi = 1, then the prime factorization of m would contain only q2, ..., qs. But we just showed that it contains P1, and we already know that p¡ is not one of the q ;'s. Thus q1 – Pj cannot be 1. Since q1 – Pi <n as well, q1 – p1 has unique prime factorization, and the factorization must contain a p1, so let us suppose that q1 u. Then q1 – Pi = pju, so q̟ = pi (u + 1), i.e., q¡ is divisible by p1. But this is impossible, since qi is prime, and primes cannot have other prime factors. This is our final contradiction, which completes the proof of uniqueness in the Fundamental Theorem of Arithmetic. Pi = Piu for some positive integer We now show that the prime factorization is unique. Let us suppose not, and that some number n has at least two prime factorizations, and furthermore that n is the smallest positive integer with this property. We write these two factorizations as n = Pi · ·· Pr =q1•·¶s» ... where some of the primes might be repeated. Now, if some p; is equal to some q;, then we have n/ p; = n/qj, and this number also has at least two prime factorizations obtained by omitting p; from the first factorization and q; from the second. However, n/p; is smaller than n, contradicting our assumption that n is the smallest positive integer with at least two prime factorizations. Thus we may assume that the list of pi's and the list of q;'s share no common primes. Let us assume, without loss of generality, that p1 < q1. (If not, then switch the Pi's and the q;'s.) Consider the number m = (qı – pi)q2·… ¶s• %3D Since q1 – Pi < qı, it follows that m < n, so m has unique prime factorization, and this factorization is (whatever the factorization of q1 – pi is) times the product of the rest of the q;'s. If we expand the product for m, we find that
Expert Solution
steps

Step by step

Solved in 5 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
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