Temeljni stavek aritmetike: edinstvena faktorizacija in praštevila
Temeljni stavek aritmetike (imenovan tudi stavek o edinstveni faktorizaciji) je stavek iz teorije števil. Izrek pravi, da lahko vsako pozitivno celo število, večje od 1, zapišemo kot zmnožek praštevil (ali pa je celo število samo praštevilo). Izrek dalje zagotavlja, da je ta zapis edinstven do vrstnega reda faktorjev: če sta dve razstavi istega števila v zmnožek praštevil, se praštevila ujemajo, le vrstni red se lahko razlikuje. Iskanje praštevil v zapisu se imenuje faktorizacija.
Izjava
Bolj natančno: za vsak n > 1 obstajajo praštevila p1, p2, ..., pk in pozitivna cela števila a1, a2, ..., ak takšna, da je
n = p1a1 × p2a2 × ... × pkak,
pri čemer so p1, p2, ..., pk med sabo različna. Ta predstavitev je edinstvena do permutacije faktorjev (torej edinstvena, če faktorje uredimo npr. naraščajoče).
Primeri
- 6936 = 23 × 3 × 172
- 1200 = 24 × 3 × 52
- 30 = 2 × 3 × 5 (tukaj so vsi eksponenti enaki 1)
Skica dokaza
Dokaz ima dva dela: obstoj in edinstvenost.
- Obstoj: dokazujemo z indukcijo po n. Če je n praštevilo, smo končali. Če ni, obstajata a, b > 1 s n = a·b, pri čemer sta a in b manjša od n. Po indukciji ju lahko vsak izrazimo kot produkt praštevil, torej tudi n.
- Edinstvenost: temelji na Euklidovem pojmu: če praštevilo p deli produkt a·b, potem p deli a ali p deli b. S tem trditvijo iterativno pokažemo, da se pri dveh razstavah morajo pojavljati isti praštevili z enakimi eksponenti. Če bi bilo drugače, bi nek p delil produkt drugih praštevil, kar po Euklidu ni mogoče, razen če p deli enega izmed njih.
Pomen in uporabe
Temeljni stavek aritmetike je eden temeljnih rezultatov v teoriji števil in služi kot osnova za mnoge pojme in algoritme: izračun največjega skupnega delitelja (gcd), najmanjšega skupnega večkratnika (lcm), aritmetičnih multiplicativnih funkcij (npr. funkcija d(n) — število deliteljev, σ(n) — vsota deliteljev) in drugih lastnosti deljenja.
V praksi ima izrek pomembno vlogo tudi v kriptografiji, predvsem v sistemih, kot je RSA, kjer varnost temelji na težavnosti faktorizacije velikih števil. Čeprav je razstavljanje na praštevila vedno mogoče glede na temeljni izrek, je za zelo velika celo števila iskanje faktorjev računsko zahtevno; zato so razviti številni algoritmi za faktorizacijo (npr. Pollardov rho, kvadratno sito, splošno številsko polje — GNFS).
Razširitve in omejitve
Temeljni stavek velja v prstanu celih števil Z. Vendar se ideja edinstvene faktorizacije razširi na pojme, kot so unikatni faktorizacijski domene (UFD), kjer ima vsak element edinstveno faktoriranje v irreducible elemente. V nekaterih drugih kolobarjih (npr. Z[√−5]) pa edinstvena faktorizacija ne velja — zato je v algebri posebna pozornost namenjena pogojem, pod katerimi imamo edinstvenost faktorizacije.
Opombe
- V praksi je pri prikazu razstav pogosto priročno praštevila urediti naraščajoče, da dobimo enoličen zapis.
- Pri računalniških in kriptografskih aplikacijah običajno ne iščemo vseh praštevil razstave (to bi bilo prepočasno za velika števila), ampak uporabljamo specializirane algoritme, ki poiščejo vsaj enega velikega faktorja.
Dokaz
Prvi, ki je dokazal trditev, je bil Evklid. Prvi podroben in pravilen dokaz je v Disquisitiones Arithmeticae Carla Friedricha Gaußa.
Nekateri morda mislijo, da je trditev resnična povsod. Vendar izrek ne velja v splošnejših številskih sistemih, kot so algebrska cela števila. To je leta 1843 prvič omenil Ernst Kummer v svojem delu o Fermatovem zadnjem izreku. Za več informacij o tem preberite algebraično teorijo števil.
Dokaz je sestavljen iz dveh delov: najprej pokažemo, da lahko vsako število zapišemo kot zmnožek praštevil, nato pa pokažemo, da če število drugič zapišemo kot zmnožek praštevil, morata biti oba seznama praštevil enaka.
Prvi del dokaza
Pokažemo, da če ne moremo vsakega števila, večjega od 1, zapisati kot produkt praštevil, pridemo do neke vrste nemožnosti. Zato potem sklepamo, da mora biti res, da je vsako število mogoče zapisati kot produkt praštevil.
Poglejmo, kaj se zgodi, če nekdo reče, da pozna pozitivno celo število, večje od 1, ki ga ni mogoče zapisati kot produkt praštevil. V tem primeru ga prosimo, naj navede vsa števila, večja od 1, ki jih ni mogoče zapisati kot produkt praštevil. Eno od teh števil mora biti najmanjše: imenujmo ga n. Seveda to število n ne more biti 1. Poleg tega ne more biti praštevilo, saj je praštevilo 'produkt' enega samega praštevilskega števila: samega sebe. Torej mora biti produkt števil. Torej -
n = ab
kjer sta a in b pozitivni celi števili, ki sta seveda manjši od n. Toda: n je bilo najmanjše število, ki ga ni mogoče zapisati kot produkt praštevil. Torej mora biti mogoče a in b zapisati kot produkta praštevil, saj sta oba manjša od n. Toda potem je produkt
n = ab
lahko zapišemo tudi kot produkt praštevil. To je nemogoče, ker smo rekli, da n ni mogoče zapisati kot produkt praštevil.
Zdaj smo pokazali, da je nemogoče, če prvi del izreka ne bi bil resničen. Na ta način smo dokazali prvi del trditve.
Drugi del dokaza
Zdaj moramo dokazati, da lahko pozitivno število, večje od 1, le na en način zapišemo kot produkt praštevil.
Za to uporabimo naslednjo lemo: če praštevilo p deli produkt ab, potem deli a ali deli b (Evklidova lema). Najprej bomo dokazali to lemo. Predpostavimo, da p ne deli a. Potem sta p in a koprimalna in imamo Bezoutovo identiteto, ki pravi, da morata obstajati celi števili x in y, tako da
px + ay = 1.
Če vse pomnožimo z b, dobimo
pbx + aby = b,
Spomnimo se, da bi ab lahko delili s p. Tako imamo zdaj na levi strani dva izraza, ki sta deljiva s p. Torej je tudi izraz na desni strani deljiv s p. Zdaj smo dokazali, da če p ne deli a, mora deliti b. To dokazuje lemo.
Zdaj bomo dokazali, da lahko celo število, večje od 1, zapišemo samo na en način kot produkt praštevil. Vzemimo dva produkta praštevil A in B, ki imata enak rezultat. Za izid produktov torej vemo, da je A = B. Vzemimo poljubno praštevilo p iz prvega produkta A. Deli A, torej deli tudi B. Če večkrat uporabimo lemo, ki smo jo pravkar dokazali, vidimo, da mora p deliti vsaj en faktor b iz B. Toda vsi faktorji so praštevilski, torej je tudi b praštevilo. Vemo pa, da je tudi p praštevilo, zato mora biti p enak b. Zato zdaj delimo A s p in delimo tudi B s p. In dobimo rezultat, kot je A* = B*. Spet lahko vzamemo praštevilo p iz prvega produkta A* in ugotovimo, da je enako nekemu številu v produktu B*. Če tako nadaljujemo, na koncu vidimo, da morata biti prafaktorja obeh produktov popolnoma enaka. To dokazuje, da lahko pozitivno celo število zapišemo kot produkt praštevil samo na en edinstven način.
Vprašanja in odgovori
V: Kaj je temeljni stavek aritmetike?
O: Temeljni stavek aritmetike je stavek iz teorije števil, ki pravi, da lahko vsako pozitivno celo število, večje od 1, zapišemo kot produkt praštevil in da obstaja samo en način zapisa števila.
V: Kako lahko ta izrek uporabimo?
O: Ta izrek se lahko uporablja v kriptografiji.
V: Kaj se zgodi, če dva človeka najdeta dva različna načina za zapis istega števila?
O: Če dva človeka najdeta dva različna načina zapisa istega števila, se lahko razlikujeta le vrstni red zapisa praštevil.
V: Kaj je faktorizacija?
O: Faktorizacija je iskanje vseh praštevil, ki sestavljajo dano število.
V: Ali je 6936 primer praštevil?
O: Ne, 6936 ni praštevilo; lahko ga zapišemo kot 23 - 3 - 172.
Ne, 6936 ni praštevilo; lahko ga zapišemo kot 23 - 3 - 172.
