Every number has a prime factorization

Dependencies: None

Every positive number has a prime factorization.

Proof

Let $n$ be the smallest number without a prime factorization. 1 has the empty factorization. Therefore, $n \ge 2$.

Also, $n$ is not prime, so it can be written as a product of factors other than 1 and itself. Therefore, all its factors have a prime factorization. Therefore, $n$ also has a prime factorization. This is a contradiction, which means all numbers have a prime factorization.

Dependency for:

  1. ab is coprime to x iff a and b are coprime to x
  2. Fundamental Theorem of Arithmetic Used in proof

Info:

Transitive dependencies: None