Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Theorems > Fundamental Theorem of Arithmetic

Fundamental Theorem of Arithmetic

Every natural number, n, n>1, can be expressed as the product of primes (called prime factors of n) in the form

n = p1 p2 ... pr,   (r ≥ 1).   (eq. 1)

Moreover, there is only one such expression as a product (i.e. decomposition into prime factors), if the order of the factors is not taken into consideration.

Proof:  The assertion is true when n=2, as there is only one prime small enough to be a factor of 2, and that prime is 2 itself.  For this proof by induction, we assume the assertion is true for all numbers smaller than n.

Assume that besides eq. 1, there is another decomposition of n into primes, one which is different from that of eq. 1 in other ways than just the order in which the primes are listed, as follows:

n = q1 q2 ... qs,   (s ≥ 1).   (eq. 2)

so 

p1 p2 ... pr  =  q1 q2 ... qs    (eq. 3)

Now, recall the theorem that if p|ab then p|a or p|b.  Applying it twice, we see that if p|abc then p|a or p|b or p|c.  Applying it "s" times, we see that since p1|q1 q2 ... qs, then p1|qj for some j.  When one prime divides another prime, they must be equal, so p1=qj.  Since the order in which they are listed doesn't matter, we can interchange q1 and qj, so p1=q1.  Dividing by p1, we see that

p2 p3 ... pr  =  q2 q3 ... qs    (eq. 4)

By the same reasoning, we see that p2=q2, p3=q3, etc.  Dividing by each one in turn, we will come at last to

pr = qs   (eq. 5)

and thus r=s, and so we see that the pi are the same as the qj in some order, and in the same number.

Related pages in this website

This theorem uses the fact that if p|ab then p|a or p|b 

 

 


The webmaster and author of this Math Help site is Graeme McRae.