Prime factorization

Task number: 3327

Prove that every natural number is a product of prime numbers.

A product in the wider sense is denoted by the symbol \(\displaystyle\prod_{k\in A}k\).

An empty product is equal to one, i.e. \(\displaystyle \prod_{k\in \emptyset} k = 1\).

Similarly the product of a single-element set equals the element itself, i.e. \(\displaystyle\prod_{k\in \{a\}} k = a\).

  • Solution

    The assertion is true for the number one – the empty product, and also for all primes – the product of a single-element set.

    We proceed by induction on the given number \(n\). Assume that the assertion is true for all \(m<n\). We must investigate the case where \(n\) is composite, i.e. \(n=m_1m_2\), where \(m_1,m_2\in \mathbb N, m_1,m_2 >1\).

    From the second condition it follows that \(m_1,m_2 < n\), so we may use the inductive hypothesis on \(m_1\) and \(m_2\) and factor them into (non-empty) sets of prime numbers, i.e. \(\displaystyle\prod_{k\in A_1} k = m_1\), \(\displaystyle\prod_{k\in A_2} k = m_2\).

    But then \(\displaystyle\prod_{k\in A_1\cup A_2} k = \left(\prod_{k\in A_1} k\right)\left( \prod_{k\in A_2} k\right) = m_1m_2=n\), so the union of both sets of factors \(A_1\cup A_2\) yields the desired factorization of \(n\).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email