Theorem NT 5.1: Every natural number is either prime or divisible by a prime.
Theorem NT 5.2: Suppose is prime and are integers, where . If then for at least one of the .
Theorem NT 5.3: If is an integer greater than 1 then can be written as a product of primes.
(HINT: Prove using strong induction. Consider two cases, when is prime, and when it is composite)