Integer is Expressible as Product of Primes/Proof 3

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n$ be an integer such that $n > 1$.


Then $n$ can be expressed as the product of one or more primes.


Proof

The proof proceeds by induction.

For all $n \in \N_{> 1}$, let $\map P n$ be the proposition:

$n$ can be expressed as a product of prime numbers.


First note that if $n$ is prime, the result is immediate.


Basis for the Induction

$\map P 2$ is the case:

$n$ can be expressed as a product of prime numbers.

As $2$ itself is a prime number, and the result is immediate.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $\map P j$ is true, for all $j$ such that $2 \le j \le k$, then it logically follows that $\map P {k + 1}$ is true.


So this is the induction hypothesis:

For all $j \in \N$ such that $2 \le j \le k$, $j$ can be expressed as a product of prime numbers.

from which it is to be shown that:

$k + 1$ can be expressed as a product of prime numbers.


Induction Step

This is the induction step:


If $k + 1$ is prime, then the result is immediate.

Otherwise, $k + 1$ is composite and can be expressed as:

$k + 1 = r s$

where $2 \le r < k + 1$ and $2 \le s < k + 1$

That is, $2 \le r \le k$ and $2 \le s \le k$.

Thus by the induction hypothesis, both $r$ and $s$ can be expressed as a product of primes.

So $k + 1 = r s$ can also be expressed as a product of primes.


So $\map P k \implies \map P {k + 1}$ and the result follows by the Second Principle of Mathematical Induction.


Therefore, for all $n \in \N_{> 1}$:

$n$ can be expressed as a product of prime numbers.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Integer_is_Expressible_as_Product_of_Primes/Proof_3&oldid=391609"