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 = p₁ p₂ ... p_r,   (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 = q₁ q₂ ... q_s,   (s ≥ 1).   (eq. 2)

so 

p₁ p₂ ... p_r  =  q₁ q₂ ... q_s    (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 p₁|q₁ q₂ ... q_s, then p₁|q_j for some j.  When one prime divides another prime, they must be equal, so p₁=q_j.  Since the order in which they are listed doesn't matter, we can interchange q₁ and q_j, so p₁=q₁.  Dividing by p₁, we see that

p₂ p₃ ... p_r  =  q₂ q₃ ... q_s    (eq. 4)

By the same reasoning, we see that p₂=q₂, p₃=q₃, etc.  Dividing by each one in turn, we will come at last to

p_r = q_s   (eq. 5)

and thus r=s, and so we see that the p_i are the same as the q_j 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.