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\).
