Prove by strong induction that every n 1 can be written as

Prove by strong induction that every n > 1 can be written as a product of primes: n = p_1 p_2 middot middot middot p_k (where the primes in the product need not be distinct). For example, 792 = 2 times 2 times 2 times 3 times 3 times 11. You may find the previous problem helpful. [The fundamental theorem of arithmetic additionally asserts that this factorization into primes is unique up to reordering of the primes.]

Solution

To prove by using the principle of mathematical induction

Base Case: (n=2)

2 can be written as the product of one prime,which is itself, hence the base case is satisfied

Inductive Step: Let us assume that for some k, that each integer ranging from 2 <= n <= k, can be written as product of primes

Hypothesis Step: Now we need to prove that (k+1) should also be written as the product of primes

Case 1: If (k+1) is a prime number, then it can be written as itself, hence this case is satisfied

Case 2: The number (k+1) is not a prime number, then it will hae atleast two factors, let the two factors be f1 and f2

(k+1) = f1 * f2

Since both the numbers product is equal to (k+1) and none can be 1, because it will contradict the case 1, that (k+1) is a prime

Hence we can say both the factors f1 and f2 lies between 2 <= f1,f2 <= k

Since we have already proved in the inductive step that for every number between 2 <=n <= k, it can be written in the prime factorization

Hence using the primciple of strong induction, every number n > 1 can be written as product of primes