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 2²·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 = p₁ … p_s = q₁ … q_t, where the p_i and q_j are all primes. (We allow repetitions among the p_i and q_j. That way, we don't have to use exponents.) Then p₁ | a = q₁ … q_t. Since p₁ is prime, by the Lemma above, p₁ | q_j for some j. Since q_j is prime and p₁ > 1, this means that p₁ = q_j. For convenience, we may renumber the q_j so that p₁ = q₁. We can now cancel p₁ from both sides of the equation above to get p₂ … p_s = q₂ … q_t. But p₂ … p_s < a and by assumption a is the smallest positive integer with a non-unique prime factorization. It follows that s = t and that p₂ … p_s are the same as q₂ … q_t, except possibly in a different order. But since p₁ = q₁ 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.)