
Every natural number, n, n>1, can be expressed as the product of primes (called prime factors of n) in the form
n = p_{1} p_{2} ... 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_{1} q_{2} ... q_{s}, (s ≥ 1). (eq. 2)
so
p_{1} p_{2} ... p_{r} = q_{1} q_{2} ... q_{s} (eq. 3)
Now, recall the theorem that if pab then pa or pb. Applying it twice, we see that if pabc then pa or pb or pc. Applying it "s" times, we see that since p_{1}q_{1} q_{2} ... q_{s}, then p_{1}q_{j} for some j. When one prime divides another prime, they must be equal, so p_{1}=q_{j}. Since the order in which they are listed doesn't matter, we can interchange q_{1} and q_{j}, so p_{1}=q_{1}. Dividing by p_{1}, we see that
p_{2} p_{3} ... p_{r} = q_{2} q_{3} ... q_{s} (eq. 4)
By the same reasoning, we see that p_{2}=q_{2}, p_{3}=q_{3}, 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.
This theorem uses the fact that if pab then pa or pb
The webmaster and author of this Math Help site is Graeme McRae.