Základní věta aritmetiky

Základní věta aritmetiky je matematická věta z oboru aritmetiky, která tvrdí, že každé přirozené číslo větší než 1 lze rozložit na součin prvočísel, a to jednoznačně až na jejich pořadí.

Pro každé přirozené číslo ${\displaystyle c\,\!}$ existuje právě jedna skupina celých kladných čísel ${\displaystyle n,m_{1},m_{2},\ldots ,m_{n}\,\!}$ a právě jedna skupina podle velikosti seřazených prvočísel: ${\displaystyle p_{1}<p_{2}<\ldots <p_{n}\,\!}$ tak, že
${\displaystyle p_{1}^{m_{1}}\cdot p_{2}^{m_{2}}\cdot p_{3}^{m_{3}}\cdot \ldots \cdot p_{n}^{m_{n}}=c}$

K níže uvedenému důkazu je potřeba Eukleidovo lemma – pokud prvočíslo dělí součin dvou celých čísel, pak dělí alespoň jedno z těchto čísel.

Důkaz věty se skládá ze dvou částí – důkazu existence a důkazu jednoznačnosti rozkladu.

Ukážeme, že každé celé číslo ${\displaystyle n>1}$ je buď prvočíslo, nebo součin prvočísel.

Důkaz provedeme pomocí silné matematické indukce:

• Pro ${\displaystyle n=2}$ tvrzení platí, protože 2 je prvočíslo.
• Nechť tvrzení platí pro všechna čísla ${\displaystyle 2\leq m<n}$. Ukážeme, že platí i pro ${\displaystyle n}$.

Pokud je ${\displaystyle n}$ prvočíslo, je hotovo. Jinak existují celá čísla ${\displaystyle a,b}$ taková, že ${\displaystyle n=ab}$, kde ${\displaystyle 1<a\leq b<n}$. Podle indukčního předpokladu lze ${\displaystyle a}$ rozložit na součin prvočísel ${\displaystyle p_{1}p_{2}\dots p_{j}}$ a ${\displaystyle b}$ na součin prvočísel ${\displaystyle q_{1}q_{2}\dots q_{k}}$.

Potom ale platí ${\displaystyle n=ab=p_{1}p_{2}\dots p_{j}\cdot q_{1}q_{2}\dots q_{k}}$, tedy i ${\displaystyle n}$ je součinem prvočísel.

Nyní pro spor předpokládejme, že existuje číslo ${\displaystyle n>1}$, které má dva různé prvočíselné rozklady. Zvolme nejmenší takové číslo ${\displaystyle n}$. Pak existují prvočísla ${\displaystyle p_{1},\dots ,p_{j}}$ a ${\displaystyle q_{1},\dots ,q_{k}}$, taková, že

${\displaystyle n=p_{1}p_{2}\dots p_{j}=q_{1}q_{2}\dots q_{k}}$, přičemž ještě předpokládáme, že tyto rozklady nejsou shodné ani po libovolném přeuspořádání činitelů.

Protože ${\displaystyle p_{1}}$ dělí součin ${\displaystyle q_{1}q_{2}\dots q_{k}}$, podle Eukleidova lemmatu dělí některé z prvočísel ${\displaystyle q_{i}}$. Bez újmy na obecnosti předpokládejme, že ${\displaystyle p_{1}}$ dělí ${\displaystyle q_{1}}$. Protože ${\displaystyle p_{1}}$ a ${\displaystyle q_{1}}$ jsou prvočísla, musí platit ${\displaystyle p_{1}=q_{1}}$.

Zkrácením stejného prvočísla na obou stranách rovnosti dostaneme

${\displaystyle p_{2}\dots p_{j}=q_{2}\dots q_{k}}$.

Tedy číslo ${\displaystyle n'={\frac {n}{p_{1}}}}$ má také dva různé prvočíselné rozklady, přičemž ${\displaystyle n'<n}$, což je ale v rozporu s předpokladem, že ${\displaystyle n}$ je nejmenší číslo s dvěma různými rozklady.

• Prvočíslo
• Prvočíselný rozklad
• Největší společný dělitel
• Nejmenší společný násobek

• Obrázky, zvuky či videa k tématu základní věta aritmetiky na Wikimedia Commons

Zdroj