Osnovni izrek aritmetike

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.