Induction on . The statement is true for . For the inductive step, let and suppose that the claim holds for all natural numbers . If is prime, we are done. Otherwise is composite, so there exist with and . By the inductive hypothesis both and can be written as products of primes, and hence so can their product .