Základní věta aritmetiky: jedinečná faktorizace čísel a aplikace
Objevte Základní větu aritmetiky: jedinečnou faktorizaci, příklady, důkazy a využití v kryptografii a teorii čísel.
Základní věta aritmetiky (nazývaná také věta o jedinečné faktorizaci) je věta z teorie čísel. V nejčastějším tvaru říká, že každé kladné celé číslo n > 1 lze zapsat jako součin prvočísel, a tento zápis je jedinečný až na pořadí činitelů. Jinými slovy: pokud existují dva zápisy n = p1 · p2 · ... · pk = q1 · q2 · ... · qm, kde p_i a q_j jsou prvočísla, pak m = k a po přeuspořádání jsou p_i = q_i pro každé i. Nálezení prvočíselného rozkladu čísla se nazývá faktorizace.
Formulace a poznámky
- Věta platí pro celá kladná čísla větší než 1; číslo 1 je zvláštní případ (je jednotkou a považuje se za prázdný součin prvočísel).
- Standardní „kanonický“ tvar faktorizace zapisuje prvočísla s exponenty: n = p1a1 · p2a2 · ... · prar, kde p1 < p2 < ... < pr jsou různá prvočísla a a_i jsou kladná celá čísla. Tento zápis je jednoznačný.
Příklady
Správné rozklady v kanonickém tvaru jsou například:
6936 = 23 · 3 · 172
1200 = 24 · 3 · 52
Pokud by někdo našel jiný rozklad téhož čísla, lze prvočísla seřadit a porovnat exponenty — vždy dostaneme tentýž kanonický zápis.
Náčrt důkazu
Existují dvě části: existence a jedinečnost.
- Existence: Pro každé n > 1 existuje faktorizace do prvočísel. Důkaz obvykle použije princip matematické indukce nebo procede dělení: pokud n není prvočíslem, existí dělitel 1 < a < n, tedy n = a·b, a opakováním rozkladu a a b (které jsou menší než n) nakonec získáme součin prvočísel.
- Jedinečnost: Klíčovým nástrojem je Eukleidův lemmát: pokud p je prvočíslo a p dělí součin ab, pak p dělí a nebo p dělí b. Pomocí tohoto lemmatu se ukáže, že pokud by existovaly dva různé rozklady do prvočísel, muselo by nějaké prvočíslo z prvního rozkladu dělit produkt druhého, a tedy dělit některé jeho prvočíslo — což nutně znamená rovnost těchto prvočísel. Postupným odstraňováním stejných prvočísel z obou stran dostaneme kontradikci, pokud by rozklady byly rozdílné.
Aplikace
Základní věta aritmetiky je fundamentální v teorii čísel a má mnoho praktických i teoretických použití:
- Kryptografie: Například bezpečnost RSA a jiných systémů závisí na obtížnosti faktorizace velkých čísel složených z dvou velkých prvočísel.
- Výpočetní aritmetika: Výpočet největšího společného dělitele (NSD) a nejmenšího společného násobku (NSN) lze zjednodušit pomocí prvočíselných rozkladů.
- Teoretické funkce: Mnohé aritmetické funkce (pliky Eulerova funkce φ(n), počet dělitelů τ(n), součet dělitelů σ(n) apod.) se snadno vyjadřují pomocí prvočíselného rozvoje n.
- Algoritmy faktorizace: Existence faktorizace je zaručena, ale nalezení faktorizace pro velmi velká čísla může být výpočetně náročné. Používané metody zahrnují zkoušení dělitelů (trial division), Pollardovo rho, kvadratický síto, síto čísel nebo elliptic curve factorization (ECM).
Obecná rozšíření a omezení
V jiných algebraických strukturách (např. v některých prstencích celých čísel rozšířených o komplexní čísla) nemusí platit jedinečná faktorizace; proto vznikla teorie jednoznačných oborů faktorizace (Unique Factorization Domains, UFD). V těchto oborech má každý neprvotný prvek jediný zápis jako součin ireducibilů až na jednotky a pořadí.
Základní věta aritmetiky tedy poskytuje pevný základ pro práci s celými čísly a je jedním z pilířů klasické aritmetiky a teorie čísel.
Důkaz
První, kdo dokázal větu, byl Euklides. První podrobný a správný důkaz podal Carl Friedrich Gauß ve svém díle Disquisitiones Arithmeticae.
Někteří lidé si mohou myslet, že věta platí všude. Věta však neplatí v obecnějších číselných soustavách, jako jsou algebraická celá čísla. Poprvé se o tom zmínil Ernst Kummer v roce 1843 ve své práci o Fermatově poslední větě. Další informace o ní: přečtěte si článek Algebraická teorie čísel.
Důkaz se skládá ze dvou částí: nejprve ukážeme, že každé číslo lze zapsat jako součin prvočísel, a poté ukážeme, že pokud číslo podruhé zapíšeme jako součin prvočísel, pak oba seznamy prvočísel musí být stejné.
První část důkazu
Ukážeme, že pokud ne každé číslo větší než 1 lze zapsat jako součin prvočísel, dostáváme se do jakési nemožnosti. Poté tedy dojdeme k závěru, že musí platit, že každé číslo lze zapsat jako součin prvočísel.
Podívejte se, co se stane, když někdo řekne, že zná celé kladné číslo větší než 1, které nelze zapsat jako součin prvočísel. V takovém případě ho požádáme, aby uvedl všechna čísla větší než 1, která nelze zapsat jako součin prvočísel. Jedno z těchto čísel musí být nejmenší: nazvěme ho n. Toto číslo n samozřejmě nemůže být 1. Dále to nemůže být prvočíslo, protože prvočíslo je "součinem" jediného prvočísla: sebe sama. Musí to tedy být součin čísel. Tedy -
n = ab
kde a i b jsou celá kladná čísla, která jsou samozřejmě menší než n. Ale: n bylo nejmenší číslo, které nelze zapsat jako součin prvočísel. Musí tedy být možné zapsat a a b jako součin prvočísel, protože obě jsou menší než n. Pak ale součin
n = ab
lze zapsat také jako součin prvočísel. To je nemožné, protože jsme řekli, že n nelze zapsat jako součin prvočísel.
Nyní jsme ukázali nemožnost, která existuje, pokud by první část věty nebyla pravdivá. Tímto způsobem jsme nyní dokázali první část věty.
Druhá část důkazu
Nyní musíme dokázat, že existuje pouze jeden způsob, jak zapsat kladné číslo větší než 1 jako součin prvočísel.
K tomu použijeme následující lemma: jestliže prvočíslo p dělí součin ab, pak dělí a nebo dělí b (Euklidovo lemma). Nejprve nyní toto lemma dokážeme. Dobře, předpokládejme nyní, že p nedělí a. Pak jsou p a a koprimátem a máme Bezoutovu identitu, která říká, že musí existovat celá čísla x a y taková, že
px + ay = 1.
Vynásobením všeho koeficientem b získáme
pbx + aby = b,
Vzpomeňte si, že ab může být dělitelné p. Nyní tedy máme na levé straně dva členy, které jsou dělitelné p. Člen na pravé straně je tedy také dělitelný p. Nyní jsme dokázali, že pokud p nedělí a, musí dělit b. To dokazuje lemma.
Nyní dokážeme, že celé číslo větší než 1 můžeme zapsat pouze jedním způsobem jako součin prvočísel. Vezměme dva součiny prvočísel A a B, které mají stejný výsledek. Pro výsledek součinů tedy víme, že A = B. Vezměme libovolné prvočíslo p z prvního součinu A. Dělí A, takže dělí i B. S několikanásobným použitím lemmatu, které jsme právě dokázali, vidíme, že p pak musí dělit alespoň jeden činitel b z B. Ale všechny činitele jsou samy prvočísla, takže i b je prvočíslo. Víme však, že p je také prvočíslo, takže p se musí rovnat b. Nyní tedy dělíme A prvočíslem p a dělíme také B prvočíslem p. A dostaneme výsledek jako A* = B*. Opět můžeme vzít prvočíslo p z prvního součinu A* a zjistit, že je rovno nějakému číslu v součinu B*. Pokračujeme-li tímto způsobem, nakonec vidíme, že prvočinitelé obou součinů musí být přesně stejní. To dokazuje, že kladné celé číslo můžeme zapsat jako součin prvočísel pouze jedním jedinečným způsobem.
Otázky a odpovědi
Otázka: Co je základní věta aritmetiky?
Odpověď: Základní věta aritmetiky je věta z teorie čísel, která říká, že každé kladné celé číslo větší než 1 lze zapsat jako součin prvočísel a že existuje pouze jeden způsob, jak číslo zapsat.
Otázka: Jak lze tuto větu použít?
Odpověď: Tuto větu lze použít v kryptografii.
Otázka: Co se stane, když dva lidé najdou dva různé způsoby zápisu stejného čísla?
Odpověď: Pokud dva lidé najdou dva různé způsoby zápisu stejného čísla, pak jediné, co se může lišit, je pořadí zápisu prvočísel.
Otázka: Co je to faktorizace?
Odpověď: Faktorizace je hledání všech prvočísel, která tvoří dané číslo.
Otázka: Je 6936 příkladem prvočísla?
Odpověď: Ne, 6936 není prvočíslo; lze ho zapsat jako 23 - 3 - 172.
Ne, 6936 není prvočíslo; lze ho zapsat jako 23 - 3 - 172.
Vyhledávání