Fundamental Theorem of Arithmetic

    The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime or a product of a finite number of primes and this factorization is unique except for the rearrangement of the factors. This result is one of the most fundamental results in all of mathematics. Its importance was not always know; indeed before its importance was known there were a few famous mathematicians who assumed unique factorization for others sets of numbers to yield untrue results.
    In this topic we start out with Euclid’s Lemma which states that if a prime divides a product then it must divide one of the factors. This lemma is very useful and will be used to show there are infinitely many primes and that every integer greater than 1 is a product of primes. Euclid’s Lemma can be found in Euclid's book The Element, and is instrumental in proving the Fundamental Theorem of Arithmetic.

    Before we prove the Fundamental Theorem of Arithmetic, it is important to realize that not all sets of numbers have this property, (it fact many do not have this property). Let's consider the set of even integers, namely

fundamental theorem of arithmetic _gr_1.gif]

We can add, subtract, even multiply elements of fundamental theorem of arithmetic _gr_2.gif] and obtain elements in fundamental theorem of arithmetic _gr_3.gif] so we say the set fundamental theorem of arithmetic _gr_4.gif] is closed under addition, subtraction, and multiplication. However, this is not he set of integers so we should define what we mean by divisibility; namely for any two elements of E we say fundamental theorem of arithmetic _gr_5.gif] means there fundamental theorem of arithmetic _gr_6.gif] such that fundamental theorem of arithmetic _gr_7.gif] The importance of fundamental theorem of arithmetic _gr_8.gif] should not be overlooked. For example, fundamental theorem of arithmetic _gr_9.gif] because fundamental theorem of arithmetic _gr_10.gif] where fundamental theorem of arithmetic _gr_11.gif] But fundamental theorem of arithmetic _gr_12.gif] because there is no fundamental theorem of arithmetic _gr_13.gif] such that fundamental theorem of arithmetic _gr_14.gif] So what are some primes in fundamental theorem of arithmetic _gr_15.gif] For example, 2 is prime in fundamental theorem of arithmetic _gr_16.gif] because there does not exist fundamental theorem of arithmetic _gr_17.gif] in fundamental theorem of arithmetic _gr_18.gif] such that fundamental theorem of arithmetic _gr_19.gif] Similarly, 6 is prime in fundamental theorem of arithmetic _gr_20.gif] because there does not exist fundamental theorem of arithmetic _gr_21.gif] in fundamental theorem of arithmetic _gr_22.gif] such that fundamental theorem of arithmetic _gr_23.gif] Also, 10 and 30 are primes, and so fundamental theorem of arithmetic _gr_24.gif] is not. But since fundamental theorem of arithmetic _gr_25.gif] we conclude that factorization into primes in fundamental theorem of arithmetic _gr_26.gif] is not unique.
    The first step in showing the Fundamental Theorem of Arithmetic is usually proving Euclid's Lemma.

Proposition (Euclid's Lemma)

    (i) An integer fundamental theorem of arithmetic _gr_27.gif] is a prime number if and only if fundamental theorem of arithmetic _gr_28.gif] for any integers fundamental theorem of arithmetic _gr_29.gif] and fundamental theorem of arithmetic _gr_30.gif]
    
    (ii) If fundamental theorem of arithmetic _gr_31.gif] is a prime number, fundamental theorem of arithmetic _gr_32.gif] fundamental theorem of arithmetic _gr_33.gif] fundamental theorem of arithmetic _gr_34.gif] are integers, and fundamental theorem of arithmetic _gr_35.gif] then fundamental theorem of arithmetic _gr_36.gif] for some fundamental theorem of arithmetic _gr_37.gif]
    
    (iii) Every integer (except fundamental theorem of arithmetic _gr_38.gif]) is a product of primes.
    
    (iv) There are infinitely many prime numbers.
    
    Proof. (i) If fundamental theorem of arithmetic _gr_39.gif] is prime and fundamental theorem of arithmetic _gr_40.gif] then fundamental theorem of arithmetic _gr_41.gif] or fundamental theorem of arithmetic _gr_42.gif] If fundamental theorem of arithmetic _gr_43.gif] then fundamental theorem of arithmetic _gr_44.gif] or if fundamental theorem of arithmetic _gr_45.gif] then fundamental theorem of arithmetic _gr_46.gif] In either case, fundamental theorem of arithmetic _gr_47.gif] or fundamental theorem of arithmetic _gr_48.gif] Similarly, when fundamental theorem of arithmetic _gr_49.gif] Conversely, suppose fundamental theorem of arithmetic _gr_50.gif] for any integers fundamental theorem of arithmetic _gr_51.gif] and fundamental theorem of arithmetic _gr_52.gif] To show that fundamental theorem of arithmetic _gr_53.gif] is prime let fundamental theorem of arithmetic _gr_54.gif] be a divisor of fundamental theorem of arithmetic _gr_55.gif] Then fundamental theorem of arithmetic _gr_56.gif] for some fundamental theorem of arithmetic _gr_57.gif] and so fundamental theorem of arithmetic _gr_58.gif] or fundamental theorem of arithmetic _gr_59.gif] Thus, if fundamental theorem of arithmetic _gr_60.gif] for some fundamental theorem of arithmetic _gr_61.gif] then fundamental theorem of arithmetic _gr_62.gif] and so fundamental theorem of arithmetic _gr_63.gif] If fundamental theorem of arithmetic _gr_64.gif] for some fundamental theorem of arithmetic _gr_65.gif] then fundamental theorem of arithmetic _gr_66.gif] and so fundamental theorem of arithmetic _gr_67.gif] as desired. fundamental theorem of arithmetic _gr_68.gif]
    (ii) fundamental theorem of arithmetic _gr_69.gif] The statement is clearly true when fundamental theorem of arithmetic _gr_70.gif] and fundamental theorem of arithmetic _gr_71.gif] is (i). Assume the statement is true for fundamental theorem of arithmetic _gr_72.gif] and suppose

fundamental theorem of arithmetic _gr_73.gif]

Then by (i), fundamental theorem of arithmetic _gr_74.gif] or fundamental theorem of arithmetic _gr_75.gif] So by the induction hypothesis there is some fundamental theorem of arithmetic _gr_76.gif] such that fundamental theorem of arithmetic _gr_77.gif] or it may be the case that fundamental theorem of arithmetic _gr_78.gif] Therefore, there is some fundamental theorem of arithmetic _gr_79.gif] such that fundamental theorem of arithmetic _gr_80.gif] as desired.
    (iii) Consider the set fundamental theorem of arithmetic _gr_81.gif] consisting of all positive integers greater than 1 that are not a product of primes. Assume for a contradiction that fundamental theorem of arithmetic _gr_82.gif] is not empty, then by the Well-Ordering Axiom there is a least element say fundamental theorem of arithmetic _gr_83.gif] Then fundamental theorem of arithmetic _gr_84.gif] is itself not a prime number and so, fundamental theorem of arithmetic _gr_85.gif] where fundamental theorem of arithmetic _gr_86.gif] and fundamental theorem of arithmetic _gr_87.gif] Since fundamental theorem of arithmetic _gr_88.gif] is the least element in fundamental theorem of arithmetic _gr_89.gif] fundamental theorem of arithmetic _gr_90.gif] and fundamental theorem of arithmetic _gr_91.gif] are products of primes; and thus so is fundamental theorem of arithmetic _gr_92.gif] This contradiction shows that fundamental theorem of arithmetic _gr_93.gif] is empty and so every integer greater than fundamental theorem of arithmetic _gr_94.gif] is a product of primes. Therefore, every integer (except fundamental theorem of arithmetic _gr_95.gif]) is a product of primes because if fundamental theorem of arithmetic _gr_96.gif] and fundamental theorem of arithmetic _gr_97.gif] then fundamental theorem of arithmetic _gr_98.gif] is a product of primes as desired.
    (iv) Assume, as Euclid did, that there are only finitely many prime numbers say,   fundamental theorem of arithmetic _gr_99.gif] Consider

fundamental theorem of arithmetic _gr_100.gif]

which by (iii) must be a product of primes. Let's say fundamental theorem of arithmetic _gr_101.gif] and since fundamental theorem of arithmetic _gr_102.gif] we have fundamental theorem of arithmetic _gr_103.gif] Therefore, fundamental theorem of arithmetic _gr_104.gif] which can not be true. Therefore, there can not be a finite number of prime numbers, as desired. fundamental theorem of arithmetic _gr_105.gif]

Proposition (Fundamental Theorem of Arithmetic) Every integer fundamental theorem of arithmetic _gr_106.gif] can be written uniquely in the form fundamental theorem of arithmetic _gr_107.gif] where fundamental theorem of arithmetic _gr_108.gif] are prime numbers and fundamental theorem of arithmetic _gr_109.gif] are positive integers.

    Proof. Every integer has a prime factorization by Euclid's Lemma. If there is an integer greater than 1 for which the factorization is not unique, then by the Well-Ordering Axiom there exists a smallest such integer, say fundamental theorem of arithmetic _gr_110.gif] Assume that fundamental theorem of arithmetic _gr_111.gif] has two factorizations say

fundamental theorem of arithmetic _gr_112.gif] and fundamental theorem of arithmetic _gr_113.gif]

where fundamental theorem of arithmetic _gr_114.gif]   fundamental theorem of arithmetic _gr_115.gif] and the fundamental theorem of arithmetic _gr_116.gif] and fundamental theorem of arithmetic _gr_117.gif] are all positive for fundamental theorem of arithmetic _gr_118.gif] and fundamental theorem of arithmetic _gr_119.gif] By Euclid's Lemma, fundamental theorem of arithmetic _gr_120.gif] for some fundamental theorem of arithmetic _gr_121.gif] and fundamental theorem of arithmetic _gr_122.gif] for some fundamental theorem of arithmetic _gr_123.gif] Since all the numbers fundamental theorem of arithmetic _gr_124.gif] and fundamental theorem of arithmetic _gr_125.gif] are prime, we must have fundamental theorem of arithmetic _gr_126.gif] and fundamental theorem of arithmetic _gr_127.gif] Then fundamental theorem of arithmetic _gr_128.gif] since fundamental theorem of arithmetic _gr_129.gif] Let fundamental theorem of arithmetic _gr_130.gif] be the integer defined as

fundamental theorem of arithmetic _gr_131.gif]

If fundamental theorem of arithmetic _gr_132.gif] then fundamental theorem of arithmetic _gr_133.gif] has a unique factorization. If fundamental theorem of arithmetic _gr_134.gif] then fundamental theorem of arithmetic _gr_135.gif] and fundamental theorem of arithmetic _gr_136.gif] has two factorizations. Both cases reveal that fundamental theorem of arithmetic _gr_137.gif] can not exist as desired. fundamental theorem of arithmetic _gr_138.gif]

Example (Unique Factorization) Find the unique prime factorization of fundamental theorem of arithmetic _gr_139.gif]

    Solution. We have,
    
fundamental theorem of arithmetic _gr_140.gif]  
   fundamental theorem of arithmetic _gr_141.gif]

Example (Unique Factorization)  Find the unique prime factorization of fundamental theorem of arithmetic _gr_142.gif]

    Solution. We have,
    
fundamental theorem of arithmetic _gr_143.gif]  
fundamental theorem of arithmetic _gr_144.gif]

Example (Unique Factorization) Factor fundamental theorem of arithmetic _gr_145.gif] and fundamental theorem of arithmetic _gr_146.gif] into a product of primes with the same set of primes with (possibly zero) nonnegative exponents.

    Solution. We have, the set of primes in both integers is fundamental theorem of arithmetic _gr_147.gif] and so we have
    
fundamental theorem of arithmetic _gr_148.gif]

and

fundamental theorem of arithmetic _gr_149.gif]
fundamental theorem of arithmetic _gr_150.gif]

Example (Unique Factorization) There are infinitely many primes of the form fundamental theorem of arithmetic _gr_151.gif]

    Solution. We assume there are only a finite number of primes of the form fundamental theorem of arithmetic _gr_152.gif] say fundamental theorem of arithmetic _gr_153.gif] is all of them; and we consider the integer

fundamental theorem of arithmetic _gr_154.gif]
    
Notice that the prime factorization of fundamental theorem of arithmetic _gr_155.gif] must contain at least one prime of the form fundamental theorem of arithmetic _gr_156.gif] because otherwise fundamental theorem of arithmetic _gr_157.gif] would be of the form fundamental theorem of arithmetic _gr_158.gif] In general, integers of the form fundamental theorem of arithmetic _gr_159.gif] have products of the form fundamental theorem of arithmetic _gr_160.gif] which can be seen by letting fundamental theorem of arithmetic _gr_161.gif] and fundamental theorem of arithmetic _gr_162.gif] then

fundamental theorem of arithmetic _gr_163.gif]

Thus, there is one prime in the prime factorization of fundamental theorem of arithmetic _gr_164.gif] that is of the form fundamental theorem of arithmetic _gr_165.gif] say fundamental theorem of arithmetic _gr_166.gif] Either fundamental theorem of arithmetic _gr_167.gif] or fundamental theorem of arithmetic _gr_168.gif] If fundamental theorem of arithmetic _gr_169.gif] then fundamental theorem of arithmetic _gr_170.gif] which means fundamental theorem of arithmetic _gr_171.gif] and so fundamental theorem of arithmetic _gr_172.gif] which is absurd. If fundamental theorem of arithmetic _gr_173.gif] then fundamental theorem of arithmetic _gr_174.gif] implies fundamental theorem of arithmetic _gr_175.gif] which is also absurd. Therefore, there are infinitely many primes of the form fundamental theorem of arithmetic _gr_176.gif] fundamental theorem of arithmetic _gr_177.gif]

Cite this as:
Fundamental Theorem Of Arithmetic
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/fundamental-theorem-of-arithmetic.html
 
    
Library of Math
Library of Math
Online Math Organized by Subject Into Topics
math search
Library of Math AddThis Feed Button
Online Math
Math Books
Custom math gifts on sale now.
Share your enthusiasm for mathematics!
Famous Mathematicians
Math Gifts
The Library of Math - Online Math Organized by Subject Into Topics.
© 2005 - 2008 www.LibraryOfMath.com All rights reserved.
about us | feedback | privacy policy | terms of use | mision statement | help

Page copy protected against web site content infringement by Copyscape Valid CSS! Valid HTML 4.01 Transitional Subscribe to the Library of Math Feed
Art & Photography Shop | Being Healthy Shop | Best Sports Mall | Cafe Food Lover | Cafe Gift Shop | Cafe Internet Shop | Career Archives | City Annals
Countries Shop | Crazy Kids World | Dallas Cowboys Football Shop | Headline News Shop | Heart Boutique | Lover of Pets | Military Support Store
Musical Boutique | Online Math Store | Political Ramblings | Shop by Auction | Shop of Learning | Shop of Technology | Shop of Travels | Special Occasion Shop
Store of Hobbies | Theology Store | Triathlon Junkie | USA States Shop | Your Animal Store | Your Fitness World | Your Funny Store | Your Science Store