## Prime factorization

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$$.  