MAIN CONCEPTS
We use the induction hypothesis for some where to show that an integer has the factorization
Get the Printer Friendly Version

Here is the proof.
We first show that any integer  has the above factorization and then show the uniqueness of the factorization in the next section. Whenever we mention ‘factorization’ or proposition, we are simply referring to that stated in the theorem.

The method we use for the proof is induction. If , then clearly  has the above factorization as a product of prime powers namely,

We then make the induction hypothesis that any integer  such that  has the above factorization. We assume the induction hypothesis to be true in order to show that induction hypothesis true implies the main proposition true.

When  is prime,  already has the above factorization as a product of prime powers, namely  itself. If  is not prime, then we can write

for integers  with  and . By our induction hypothesis, there exist primes  and positive integers  such that  are distinct primes and  and so

And by substituting back into , we have

which says that  can be factored as a product of prime powers. While the notation looks messy at this point, it is necessary to label terms as  and  because we do not know yet whether these terms are the same as the  in the original factorization.

If  for some  and , we replace  by . And we can now write  where  are distinct primes and  are positive integers.

While I can simply conclude and say that by induction, any integer  has the factorization, I like to elaborate slightly further. This is where the process of induction is in action. Remember our induction hypothesis which says that the proposition is true for any integer  such that . Well, it turns out that this is true for . So now I just pick an integer more than 2, and it will satisfy the proposition. I pick 3, it is prime and so proposition true. I then pick 4,  and since we know the proposition is true for 2, the proposition is true for 4. I then repeat the process for  so on and so forth.

One way to look at it is that the induction hypothesis  allows me prove the proposition is true for each successive increase of k starting with .

That should be enough of method of prove by induction. It takes more readings of other proofs for the reader to get acquainted with the techniques. We will prove the uniqueness property in the following section.