Page 2 of 10

Lesson 26 Handout – Strong Induction examples

Theorem NT 5.1: Every natural number n>1 is either prime or divisible by a prime.

Theorem NT 5.2: Suppose p is prime and a_{1}, a_{2}, a_{3}, \ldots, a_{n} are n integers, where n \geq 2. If p \mid a_{1} \cdot a_{2} \cdot a_{3} \cdot \ldots \cdot a_{n}, then p \mid a_{i} for at least one of the a_{i}(1 \leq i \leq n).

Theorem NT 5.3: If n is an integer greater than 1 then n can be written as a product of primes.
(HINT: Prove using strong induction. Consider two cases, when k+1 is prime, and when it is composite)

« Older posts Newer posts »