Rozklad na prvočísla
Úloha číslo: 3304
Dokažte, že každé přirozené číslo je součinem prvočísel.
Součin je míněn v širším významu vyjádřeným symbolem \(\displaystyle\prod_{k\in A}k\).
Prázný součin je roven jedné, t.j. \(\displaystyle \prod_{k\in \emptyset} k = 1\).
Podobně součin přes jednoprvkovou množinu je roven příslušnému prvku, t.j. \(\displaystyle\prod_{k\in \{a\}} k = a\).
Řešení
Tvrzení platí pro jedničku – prázný součin, a také pro všechna prvočísla – součin přes jednoprvkovou množinu.
Dále postupujeme indukcí podle velikosti daného čísla \(n\). Předpokládejme, že tvrzení platí pro všechna \(m<n\). Zbývá ošetřit případ, je-li \(n\) složené, čili \(n=m_1m_2\), kde \(m_1,m_2\in \mathbb N, m_1,m_2 >1\).
Z druhé podmínky vyplývá i \(m_1,m_2 < n\), tedy na \(m_1\) i na \(m_2\) lze použít indukční předpoklad a rozložit je na součin (neprázdných) množin prvočísel t.j. \(\displaystyle\prod_{k\in A_1} k = m_1\), \(\displaystyle\prod_{k\in A_2} k = m_2\).
Potom ale \(\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\), tedy sjednocení obou dílčích rozkladů \(A_1\cup A_2\) je hledaným rozkladem čísla \(n\) na prvočísla.
