Integer is Expressible as Product of Primes/Proof 1

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

Aiming for a contradiction, suppose this supposition is false.

Let $m$ be the smallest integer which can not be expressed as the product of primes.

As a prime number is trivially a product of primes, $m$ can not itself be prime.

Hence:

$\exists r, s \in \Z: 1 < r < m, 1 < s < m: m = r s$

As $m$ is our least counterexample, both $r$ and $s$ can be expressed as the product of primes.

Say $r = p_1 p_2 \cdots p_k$ and $s = q_1 q_2 \cdots q_l$, where all of $p_1, \ldots, p_k, q_1, \ldots, q_l$ are prime.

Hence $m = r s = p_1 p_2 \cdots p_k q_1 q_2 \cdots q_l$, which is a product of primes.

Hence there is no such counterexample.

$\blacksquare$


Sources