# document.write (document.title)

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