Exercise 4.4-11

[Spdwal]

Exercise 4.4-11

[muzimuzhi]

Test extension

Let $n$ and $d$ denote integers. We say that $d$ is a divisor of $n$ if $n = cd$ for some integer $c$. An integer $n$ is called a prime if $n > 1$ and if the only positive divisors of $n$ are $1$ and $n$. Prove, by induction, that every integer $n > 1$ is either a prime or a product of primes.

[muzimuzhi]

Prove by induction.

Let $A(n)$ be an assertion that integer $n$ is either a prime or a production of primes.

• STEP 1. $A(2)$ is true, since $2$ is a prime.
• STEP 2. Suppose $A(k)$ ($1 < k \leq n$) is true. We prove $A(n+1)$ is true.
  • If $n + 1$ itself is a prime, $A(n+1)$ holds.
  • If $n + 1$ is not a prime, there exists a positive integer $d$, $1 < d < n+1$, such that $n = cd$ for some $c$. Hence $1 < c < n+1$. Since $A(d)$ holds, $d$ is either a prime or a production of primes. The same is true for $c$. Therefore $n + 1 = cd$ is a production of primes. $A(n+1)$ holds.

In conclusion, $A(n)$ holds for every integer $n>1$.

[soulomoon]

push