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