Základná veta aritmetiky — jedinečná faktorizácia prirodzených čísel

Základná veta aritmetiky: jedinečná faktorizácia prirodzených čísel — vysvetlenie, príklady a využitie v kryptografii. Naučte sa, prečo je faktorizácia kľúčová.

Autor: Leandro Alegsa

24-02-2026 19:26

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_k^a_k.

Tento zápis je jednoznačný v tom zmysle, že ak existuje iný zápis n = q₁^b₁ × ... × q_m^b_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 = 2³ × 3 × 17²

1200 = 2⁴ × 3 × 5²

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 v_p(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 v_p(gcd(a,b)) = min(v_p(a), v_p(b)) a v_p(lcm(a,b)) = max(v_p(a), v_p(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.

Dôkaz

Prvý, kto dokázal túto vetu, bol Euklides. Prvý podrobný a správny dôkaz bol v diele Disquisitiones Arithmeticae od Carla Friedricha Gaußa.

Niektorí ľudia si môžu myslieť, že veta platí všade. Veta však neplatí vo všeobecnejších číselných sústavách, ako sú algebraické celé čísla. Prvýkrát sa o tom zmienil Ernst Kummer v roku 1843 vo svojej práci o Fermatovej poslednej vete. Viac informácií o nej nájdete v článku Teória algebraických čísel.

Dôkaz pozostáva z dvoch častí: najprv ukážeme, že každé číslo sa dá zapísať ako súčin prvočísel; potom ukážeme, že ak číslo zapíšeme ako súčin prvočísel druhýkrát, potom musia byť oba zoznamy prvočísel rovnaké.

Prvá časť dôkazu

Ukážeme, že ak nie každé číslo väčšie ako 1 možno zapísať ako súčin prvočísel, dostávame sa do určitej nemožnosti. Potom teda dospejeme k záveru, že musí platiť, že každé číslo sa dá zapísať ako súčin prvočísel.

Teraz sa pozrite, čo sa stane, keď niekto povie, že pozná celé kladné číslo väčšie ako 1, ktoré sa nedá zapísať ako súčin prvočísel. V takom prípade ho požiadame, aby uviedol všetky čísla väčšie ako 1, ktoré sa nedajú zapísať ako súčin prvočísel. Jedno z týchto čísel musí byť najmenšie: nazvime ho n. Samozrejme, toto číslo n nemôže byť 1. Ďalej to nemôže byť prvočíslo, pretože prvočíslo je "súčinom" jediného prvočísla: samého seba. Musí to byť teda súčin čísel. Teda -

n = ab

kde a aj b sú kladné celé čísla, ktoré sú samozrejme menšie ako n. Ale: n bolo najmenšie číslo, ktoré sa nedá zapísať ako súčin prvočísel. Takže musí byť možné zapísať a a b ako súčin prvočísel, pretože obe sú menšie ako n. Ale potom súčin

n = ab

možno zapísať aj ako súčin prvočísel. To je nemožné, pretože sme povedali, že n sa nedá zapísať ako súčin prvočísel.

Teraz sme ukázali nemožnosť, ktorá existuje, ak by prvá časť vety nebola pravdivá. Týmto spôsobom sme teraz dokázali prvú časť vety.

Druhá časť dôkazu

Teraz musíme dokázať, že existuje len jeden spôsob, ako zapísať kladné číslo väčšie ako 1 ako súčin prvočísel.

Na to použijeme nasledujúcu lemu: ak prvočíslo p delí súčin ab, potom delí a alebo delí b (Euklidova lema). Najprv teraz dokážeme túto lemu. No teraz predpokladajme, že p nedelí a. Potom sú p a a koprimátne a máme Bezoutovu identitu, ktorá hovorí, že musia existovať celé čísla x a y také, že

px + ay = 1.

Vynásobením všetkého koeficientom b dostaneme

pbx + aby = b,

Spomeňte si, že ab by mohlo byť deliteľné p. Takže teraz máme na ľavej strane dva členy, ktoré sú deliteľné p. Takže člen na pravej strane je tiež deliteľný p. Teraz sme dokázali, že ak p nedelí a, musí deliť b. To dokazuje lemu.

Teraz dokážeme, že celé číslo väčšie ako 1 môžeme zapísať len jedným spôsobom ako súčin prvočísel. Vezmime si dva súčiny prvočísel A a B, ktoré majú rovnaký výsledok. Pre výsledok súčinov teda vieme, že A = B. Vezmime si ľubovoľné prvočíslo p z prvého súčinu A. Delí A, takže delí aj B. Ak niekoľkokrát použijeme lemu, ktorú sme práve dokázali, vidíme, že p potom musí deliť aspoň jeden faktor b z B. Ale všetky faktory sú samé prvočísla, takže aj b je prvočíslo. Ale vieme, že p je tiež prvočíslo, takže p sa musí rovnať b. Takže teraz delíme A číslom p a tiež delíme B číslom p. A dostaneme výsledok ako A* = B*. Opäť môžeme vziať prvočíslo p z prvého súčinu A* a zistiť, že sa rovná nejakému číslu v súčine B*. Ak budeme takto pokračovať, nakoniec uvidíme, že prvočinitele oboch súčinov musia byť presne rovnaké. To dokazuje, že kladné celé číslo môžeme zapísať ako súčin prvočísel len jedným jedinečným spôsobom.

Otázky a odpovede

Otázka: Čo je základná veta aritmetiky?

Odpoveď: Základná veta aritmetiky je veta z teórie čísel, ktorá hovorí, že každé kladné celé číslo väčšie ako 1 sa dá zapísať ako súčin prvočísel a existuje len jeden spôsob, ako číslo zapísať.

Otázka: Ako sa dá táto veta použiť?

Odpoveď: Túto vetu možno použiť v kryptografii.

Otázka: Čo sa stane, ak dvaja ľudia nájdu dva rôzne spôsoby zápisu toho istého čísla?

Odpoveď: Ak dvaja ľudia nájdu dva rôzne spôsoby zápisu toho istého čísla, potom jediná vec, ktorá sa môže líšiť, je poradie, v akom sú prvočísla zapísané.

Otázka: Čo je to faktorizácia?

Odpoveď: Faktorizácia je hľadanie všetkých prvočísel, ktoré tvoria dané číslo.

Otázka: Je 6936 príkladom prvočísla?

Odpoveď: Nie, 6936 nie je prvočíslo; môžeme ho zapísať ako 23 - 3 - 172.
Nie, 6936 nie je prvočíslo; možno ho zapísať ako 23 - 3 - 172.

Prehľadať