Integer is Expressible as Product of Primes/Proof 1
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
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): $\S 13.1$: The fundamental theorem of arithmetic
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Theorem $4$
- 1982: Martin Davis: Computability and Unsolvability (2nd ed.) ... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $6$
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): $\S 1.14$: Exercise $19 \ \text{(c)}$