# 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.
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