Mathematical-Reasoning · Unit 13 · Video 3 · Interactive Practice

Strong Induction: Every Integer Above 1 Factors into Primes

IKey Formulas

Statement	Formula
Second Principle ( $M \in \mathbb{Z}$ , $T \subseteq \mathbb{Z}$ ): two conditions	$M \in T$ , and for every $k \ge M$ : $\{M, M+1, \ldots, k\} \subseteq T \implies k+1 \in T$
Second Principle: conclusion	$\{n \in \mathbb{Z} \mid n \ge M\} \subseteq T$
Inductive step, Extended Principle vs Second Principle	$P(k) \implies P(k+1)$ vs $P(M), P(M+1), \ldots, P(k) \implies P(k+1)$
Composite case of the prime-factor theorem ( $M = 2$ )	$k+1 = a \cdot b$ with $1 \lt a \le k$ and $1 \lt b \le k$

Key Insight: The inductive assumption is still made for one arbitrary $k$ , but it covers every case from $M$ through $k$ . Use the Second Principle when the proof for $k+1$ needs cases earlier than $k$ , as when $k+1$ splits into two smaller factors.

IIWhere the Stronger Assumption Is Used

When $k+1 = a \cdot b$ is composite, both factors lie in $2, \ldots, k$ , but neither equals $k$ .

k + 1 40 Factor pair Assumption

IIIUnwinding the Inductive Assumption

Each composite number splits into two smaller factors, and the splitting stops only when every factor is prime.

n Split 0

💡 This proof shows that a factorisation into primes exists. Whether different ways of splitting always end in the same primes is a separate question that this argument does not settle.

IVQuiz Questions

Problem 1 · The Inductive Assumption

Given: A proof by the Second Principle that $P(n)$ holds for every natural number $n \ge 2$ . In the inductive step, $k$ is a natural number with $k \ge 2$ and the goal is $P(k+1)$ . What is the full inductive assumption the Second Principle provides?

✅ Correct! With

M = 2

the inductive assumption is every case from

P(2)

through

P(k)

❌ That is the Extended Principle's step.

P(k)

is only the last case of the assumption; the Second Principle provides every case from

P(2)

through

P(k)

❌ That assumes the goal.

P(k+1)

is what the inductive step must prove, so it cannot be part of the assumption.

❌ The list starts at the starting value $M = 2$ .

P(1)

is not part of the theorem, and here it is false:

1

is neither prime nor a product of primes.

Show solution

The Second Principle with starting value $M$ has the inductive step: let $k \ge M$ and prove that if $P(M), P(M+1), \ldots, P(k)$ are true, then $P(k+1)$ is true. With $M = 2$ the assumption is

P(2),\ P(3),\ \ldots,\ P(k).

It may not include $P(k+1)$ (that is the goal) and does not include $P(1)$ (the statement starts at $2$ ). Option a names only the last of these cases, so it is not the full assumption: the answer is c.

Problem 2 · Which Cases the Step Uses

Given: In the proof that every natural number greater than $1$ is prime or a product of primes, take $k+1 = 40$ and split it as $40 = 5 \cdot 8$ . Which cases of the inductive assumption does Case 2 of the argument use?

✅ Correct!

5

is prime and

8 = 2 \cdot 2 \cdot 2

, so joining the lists gives

40 = 5 \cdot 2 \cdot 2 \cdot 2

❌ $39$ is not a factor of $40$ .

P(39)

is true (

39 = 3 \cdot 13

), but the argument for

40

never uses it; ordinary induction would offer only this case, which is why it does not help.

❌ Those belong to a different split.

40 = 2 \cdot 20

would use

P(2)

and

P(20)

, but this split is

5 \cdot 8

, so the argument uses the cases for its own two factors.

❌ $P(40)$ is the goal. The inductive assumption covers only

P(2)

through

P(39)

; the argument proves

P(40)

from

P(5)

and

P(8)

Show solution

Here $k = 39$ , so the inductive assumption is $P(2), P(3), \ldots, P(39)$ . Since $40 = 5 \cdot 8$ with $1 \lt 5 \le 39$ and $1 \lt 8 \le 39$ , both $P(5)$ and $P(8)$ are in the assumption:

5 \text{ is prime}, \qquad 8 = 2 \cdot 2 \cdot 2.

Joining the two lists of primes gives $40 = 5 \cdot 2 \cdot 2 \cdot 2$ , so $P(40)$ holds. Only $P(5)$ and $P(8)$ were used: answer a.

Problem 3 · Why Both Factors Are at Most k

Given: In Case 2, $k \ge 2$ and $k+1 = a \cdot b$ for natural numbers $a$ and $b$ with $a \gt 1$ and $b \gt 1$ . Which argument correctly shows $a \le k$ , so that $P(a)$ is in the inductive assumption?

✅ Correct! The bound on

a

comes from the other factor being at least

2

; the same argument with the roles swapped gives

b \le k

❌ That bound is too weak.

a \le k+1

still allows

a = k+1

, which is not in the range

2, \ldots, k

the assumption covers. The proof needs

b \gt 1

to rule that out.

❌ The factors need not be prime. For

40 = 5 \cdot 8

the factor

8

is composite; that is exactly why the proof needs

P(8)

❌ Nothing says $a \lt b$ . The given conditions are only

a \gt 1

and

b \gt 1

, and the factors can even be equal (

49 = 7 \cdot 7

). The bound on

a

comes from the other factor:

b \ge 2

, so

a = \frac{k+1}{b} \le \frac{k+1}{2}

, with no ordering needed.

Show solution

Since $b \gt 1$ and $b$ is a natural number, $b \ge 2$ . Then

a = \frac{k+1}{b} \le \frac{k+1}{2}.

And $\frac{k+1}{2} \le k$ is equivalent to $k + 1 \le 2k$ , that is, $k \ge 1$ , which holds since $k \ge 2$ . So $1 \lt a \le k$ , and in the same way $1 \lt b \le k$ . Both factors lie in the range $2, \ldots, k$ that the inductive assumption covers: answer d.

Problem 4 · Transfer: A Prime Divisor

Given: Prove by the Second Principle that every natural number $n \gt 1$ has a prime divisor. Let $P(n)$ be " $n$ has a prime divisor". In the inductive step, $k \ge 2$ , $P(2), \ldots, P(k)$ are assumed, and $k+1 = a \cdot b$ with $1 \lt a \le k$ and $1 \lt b \le k$ . Which sentence completes this composite case correctly?

✅ Correct! Divisibility is transitive:

p \mid a

and

a \mid (k+1)

give

p \mid (k+1)

. Only one earlier case,

P(a)

, is needed, and it can be far below

k

❌ A divisor of $k$ never divides $k+1$ here. If

p \mid k

and

p \mid (k+1)

, then

p \mid 1

, which is impossible for a prime. The useful earlier case is a factor of

k+1

, not

k

❌ Backwards. Writing

k+1 = a \cdot b

with

a \gt 1

and

b \gt 1

shows

k+1

is composite, not prime.

❌ $pq$ is not prime. A product of two primes is composite, so it cannot serve as the prime divisor; one of

p

q

alone does the job.

Show solution

Basis: $2$ is prime and divides itself, so $P(2)$ is true.

Inductive step: let $k \ge 2$ and assume $P(2), \ldots, P(k)$ . If $k+1$ is prime, it is a prime divisor of itself. Otherwise $k+1 = a \cdot b$ with $1 \lt a \le k$ , so $P(a)$ gives a prime $p$ with $p \mid a$ . Since $a \mid (k+1)$ ,

p \mid a \ \text{ and } \ a \mid (k+1) \implies p \mid (k+1).

So $P(k+1)$ is true, and by the Second Principle every natural number $n \gt 1$ has a prime divisor. The step uses $P(a)$ , where $a$ may be much smaller than $k$ , which is why the Second Principle fits: answer b.

Solved: 0 / 4