Základná veta aritmetiky (nazývaná aj veta o jedinečnej faktorizácii) je veta z teórie čísel. Veta hovorí, že každé kladné celé číslo väčšie ako 1 možno zapísať ako súčin prvočísel (alebo celé číslo je samo prvočíslo) a že tento zápis je jednoznačný až na poradie prvočísel. Hľadanie takéhoto rozkladu sa nazýva faktorizácia.
Formálne znenie
Pre každé celé číslo n > 1 existujú prvočísla p₁ <= p₂ <= ... <= p_k a prirodzené exponenty a₁, a₂, ..., a_k ≥ 1 také, že
n = p₁a₁ × p₂a₂ × ... × p_ka_k.
Tento zápis je jednoznačný v tom zmysle, že ak existuje iný zápis n = q₁b₁ × ... × q_mb_m s prvočíslami q_j, potom m = k a po preskupení platí q_j = p_j a b_j = a_j pre všetky j (teda jediné, čo sa môže líšiť, je poradie činiteľov).
Príklady
Pre ilustráciu:
6936 = 23 × 3 × 172
1200 = 24 × 3 × 52
Ak niekto nájde iný rozklad týchto čísel na prvočísla, možno činitele zoradiť a zistí sa, že rozklady sú rovnaké až na poradie.
Náčrt dôkazu
Existencia rozkladu: ak n je prvočíslo, rozklad je triviálny. Ak nie je, má prvočíselný deliteľ p (každé zložené číslo má prvočíselný deliteľ — napr. najmenší netriviálny deliteľ je prvočíslo). Potom n = p × m a rekurzívne rozložíme m; tento proces končí, pretože faktorizované čísla sa zmenšujú. Tým získame rozklad n na prvočísla.
Jedinečnosť: kľúčovou pomôckou je Euclidovo lemmma: ak p je prvočíslo a p delí súčin ab, potom p delí a alebo p delí b. Z tohto lemmatu vyplýva, že ak by existovali dva rôzne rozklady n = p₁ × ... × p_r = q₁ × ... × q_s, tak p₁ by muselo deliť niektoré q_j, takže p₁ = q_j; po odstránení tohto spoločného faktora dostaneme menší kontradikčný prípad. Opakovaním sa dospeje k tomu, že všetky prvky rozkladov sa zhodujú (a zvyšné exponenty tiež), takže rozklad je jednoznačný až na poradie.
Dôsledky a aplikácie
- Každé prirodzené číslo má tzv. kanonický (alebo primárny) rozklad do prvočísel, čo umožňuje definovať exponenty vp(n) (p-adická valuations) — počet násobností prvočísla p v n.
- Výpočet najväčšieho spoločného deliteľa (NSD) a najmenšieho spoločného násobku (NSN) dvoch čísel sa dá pohodlne vyjadriť cez exponenty: pre každé prvočíslo p je vp(gcd(a,b)) = min(vp(a), vp(b)) a vp(lcm(a,b)) = max(vp(a), vp(b)).
- Mnoho aritmetických funkcií (počet deliteľov τ(n), súčet deliteľov σ(n), Möbiova funkcia μ(n) a pod.) sa najjednoduchšie študuje pomocou kanonického rozkladu, pretože súto tieto funkcie multiplicatívne a ich hodnoty sa dajú vyjadriť cez exponenty v rozklade.
- V kryptografii je fundamentálna skutočnosť, že hoci rozklad na prvočísla existuje a je jedinečný, nájdenie tohto rozkladu pre čísla s veľkými faktormi môže byť výpočtovo náročné. Práve táto ťažkosť sa využíva v systémoch ako RSA: verejný kľúč obsahuje súčin dvoch veľkých prvočísel, zatiaľ čo bezpečnosť závisí na zložitosti faktorizácie tohto súčinu.
- V algebraickom zobrazení sa veta o jedinečnej faktorizácii prirodzených čísel rozširuje do pojmu jednoznačná faktorizácia v prstencoch — tzv. unique factorization domains (UFD). Nie v každom integrálnom dome však platí jedinečnosť (známy príklad zlyhania je Z[√-5], kde 6 má dvojaký rozklad na irreducibilné prvky).
Faktorizácia v praxi
Algoritmy faktorizácie sa líšia podľa veľkosti a typu čísel: pre malé čísla stačí trial division, pre väčšie sú používané Pollardovo rho, elliptic curve factorization alebo najefektívnejší známy algoritmus pre všeobecné veľké čísla — number field sieve. Výskum v oblasti faktorizácie a počítačovej bezpečnosti je aktívny, keďže zlepšenie algoritmov má priamy dopad na kryptografické protokoly.
Zhrnutie: Základná veta aritmetiky poskytuje kanonický a jednoznačný spôsob zápisu každého prirodzeného čísla (>1) ako súčinu prvočísel. Je to základný pilier teórie čísel a má široké dôsledky v aritmetike, algebraickej štruktúre prstencov a v praktických aplikáciách, najmä v kryptografii.