Fundamental Theorem of Arithmetic

Pronunciation: /ˌfʌn.dəˈmɛn.tl ˈθɪər.əm ʌv əˈrɪθ.mə.tɪk/ Explain

The fundamental theorem of arithmetic states that for all positive integers except 1, there exists a unique prime factorization. For example, take the number 12. The prime factorization of 12 is 22·3. There is no other combination of prime factors that multiplies out to 12.

Proof of the Fundamental Theorem of Arithmetic

There are two things to be proved. Both parts of the proof will use the Well-ordering Principle for the set of natural numbers.

  1. We first prove that every integer a > 1 can be written as a product of prime factors. (This includes the possibility of there being only one factor in case a is prime.) Suppose that there exists an integer a > 1 such that a cannot be written as a product of primes. By the Well-ordering Principle, there is a smallest such a. Then by assumption a is not prime so a = bc where 1 < b; c < a. So b and c can be written as products of prime factors (since a is the smallest positive integer than cannot be.) But since a = bc, this makes a product of prime factors, a CONTRADICTION.
  2. Now suppose that there exists an integer a > 1 that has two different prime factorizations, say a = p1ps = q1qt, where the pi and qj are all primes. (We allow repetitions among the pi and qj. That way, we don't have to use exponents.) Then p1 | a = q1qt. Since p1 is prime, by the Lemma above, p1 | qj for some j. Since qj is prime and p1 > 1, this means that p1 = qj. For convenience, we may renumber the qj so that p1 = q1. We can now cancel p1 from both sides of the equation above to get p2ps = q2qt. But p2ps < a and by assumption a is the smallest positive integer with a non-unique prime factorization. It follows that s = t and that p2ps are the same as q2qt, except possibly in a different order. But since p1 = q1 as well, this is a CONTRADICTION to the assumption that these were two different factorizations. Thus there cannot exist such an integer a with two different factorizations.[2]

References

  1. McAdams, David E.. All Math Words Dictionary, fundamental theorem of arithmetic. 2nd Classroom edition 20150108-4799968. pg 83. Life is a Story Problem LLC. January 8, 2015. Buy the book
  2. E. Lee Lady. Fundamental Theorem of Arithmetic. Last Accessed 7/11/2018. http://www.math.hawaii.edu/~lee/courses/fundamental.pdf.
  3. Bell, Eric Temple. An Arithmetical Theory of Certain Numerical Functions. vol 1. no 1. www.archive.org. University of Washington Publications in Mathematical and Physical Sciences. University of Washington. Aug 1915. Last Accessed 7/11/2018. http://www.archive.org/stream/ariththeorycernu00bellrich#page/n25/mode/1up/search/fundamental. Buy the book
  4. Bettinger, Alvin K. and Englund, John A.. Algebra and Trigonometry. pg 25. www.archive.org. International Textbook Company. January 1963. Last Accessed 7/11/2018. http://www.archive.org/stream/algebraandtrigon033520mbp#page/n18/mode/1up. Buy the book

Cite this article as:

McAdams, David E. Fundamental Theorem of Arithmetic. 4/21/2019. All Math Words Encyclopedia. Life is a Story Problem LLC. http://www.allmathwords.org/en/f/fundtheoremarithmetic.html.

Revision History

4/21/2019: Modified equations and expression to match the new format. (McAdams, David E.)
12/21/2018: Reviewed and corrected IPA pronunication. (McAdams, David E.)
7/9/2018: Removed broken links, updated license, implemented new markup, implemented new Geogebra protocol. (McAdams, David E.)
2/5/2010: Added "References". (McAdams, David E.)
2/12/2009: Initial version. (McAdams, David E.)

All Math Words Encyclopedia is a service of Life is a Story Problem LLC.
Copyright © 2018 Life is a Story Problem LLC. All rights reserved.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License