---
tag: 020K0X7HVR
kind: statement
role: theorem
name: Existence of prime factorization
msc: [11A51]
uses: [0AEKDFCYFA, 0SPBEDVNW1]
sources:
  - url: https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
    locator: Existence
---

## Statement

Each positive integer $n$ has a [[prime factorization|0AEKDFCYFA]].
That is, there are [[prime numbers|0SN0MAEKYX]] $p_1, \dots, p_k$, with $k \ge 0$, such that $n = p_1 p_2 \cdots p_k$.

## Remarks

The proof uses strong induction on $n$. If $n = 1$, take $k = 0$. If $n$ is prime, take $k = 1$. Otherwise $n = a b$ with $1 < a, b < n$, and we join the factorizations of $a$ and $b$.
The [[fundamental theorem of arithmetic|084HH1NDCB]] adds that the factorization is unique, up to the order of the factors.

## Explanations

### L1 human

Split each number that is not prime into two smaller factors. Continue until all the pieces are prime.
The pieces always get smaller, so the splitting stops.
For example, $84 = 2 \cdot 42 = 2 \cdot 2 \cdot 21 = 2 \cdot 2 \cdot 3 \cdot 7$.