A számelmélet alaptétele

Bizonyíték

Az első, aki bebizonyította a tételt, Euklidész volt. Az első részletes és helyes bizonyítást Carl Friedrich Gauß Disquisitiones Arithmeticae című művében találjuk.

Egyesek azt gondolhatják, hogy a tétel mindenhol igaz. A tétel azonban nem igaz az általánosabb számrendszerekben, például az algebrai egész számokban. Ezt először Ernst Kummer említette 1843-ban, a Fermat utolsó tételéről szóló munkájában. Erről bővebben: olvasd el az algebrai számelméletet.

A bizonyítás két részből áll: először megmutatjuk, hogy minden számot fel lehet írni prímszámok szorzataként; másodszor megmutatjuk, hogy ha egy számot másodszor is prímszámok szorzataként írunk fel, akkor a prímszámok két listájának meg kell egyeznie.

A bizonyítás első része

Megmutatjuk, hogy ha nem minden 1-nél nagyobb szám írható fel prímszámok szorzataként, akkor valamiféle lehetetlenségbe kerülünk. Tehát ezek után arra a következtetésre jutunk, hogy igaznak kell lennie, hogy minden számot fel lehet írni prímszámok szorzataként.

Nézzük meg, mi történik, ha valaki azt mondja, hogy ismer egy 1-nél nagyobb pozitív egész számot, amely nem írható fel prímszámok szorzataként. Ebben az esetben megkérjük, hogy nevezze meg az összes olyan 1-nél nagyobb számot, amely nem írható fel prímszámok szorzataként. Az egyik ilyen számnak a legkisebbnek kell lennie: nevezzük n-nek. Természetesen ez az n szám nem lehet 1. Továbbá nem lehet prímszám, mert a prímszám egyetlen prímszám "szorzata": önmaga. Tehát számok szorzatának kell lennie. Tehát -

n = ab

ahol mind a, mind b pozitív egész számok, amelyek természetesen kisebbek n-nél. De: n volt a legkisebb szám, amely nem írható fel prímszámok szorzataként. Tehát a-t és b-t fel kell tudni írni prímszámok szorzataként, mert mindkettő kisebb n-nél. De akkor a szorzata

n = ab

felírható prímszámok szorzataként is. Ez azért lehetetlen, mert azt mondtuk, hogy n nem írható fel prímszámok szorzataként.

Most megmutattuk azt a lehetetlenséget, amely akkor áll fenn, ha a tétel első része nem lenne igaz. Ezzel bebizonyítottuk a tétel első részét.

A bizonyítás második része

Most be kell bizonyítanunk, hogy csak egyféleképpen lehet 1-nél nagyobb pozitív számot prímszámok szorzataként leírni.

Ehhez a következő lemmát használjuk: ha egy p prímszám osztja az ab szorzatot, akkor vagy osztja az a-t, vagy osztja a b-t (Euklidész lemma). Először is bizonyítsuk be ezt a lemmát. Nos, tegyük fel, hogy p nem osztja meg a-t. Akkor p és a négyes számú, és megvan Bezout azonossága, amely azt mondja, hogy kell lennie olyan x és y egész számoknak, hogy

px + ay = 1.

Ha mindent megszorozunk b-vel, akkor

pbx + aby = b,

Emlékezzünk, hogy ab osztható p-vel. Tehát most a bal oldalon van két olyan tag, amely osztható p-vel. Tehát a jobb oldalon lévő tag szintén osztható p-vel. Most bebizonyítottuk, hogy ha p nem osztja meg a-t, akkor b-t is meg kell osztania. Ez bizonyítja a lemma helyességét.

Most bebizonyítjuk, hogy az 1-nél nagyobb egész számot csak egyféleképpen írhatjuk fel prímszámok szorzataként. Vegyünk két olyan A és B prímszám szorzatot, amelyeknek ugyanaz az eredménye. Tehát a termékek eredményére tudjuk, hogy A = B. Vegyünk az első termékből A bármelyik prímszámot p-t. Ez osztja A-t, tehát osztja B-t is. Az imént bizonyított lemma többszöri alkalmazásával láthatjuk, hogy p-nek ekkor B legalább egy b tényezőjét kell osztania. De a tényezők mindegyike maga is prímszám, tehát b is prímszám. De tudjuk, hogy p szintén prím, tehát p-nek egyenlőnek kell lennie b-vel. Így most A-t osztjuk p-vel, és B-t is osztjuk p-vel. És olyan eredményt kapunk, mint A* = B*. Ismét vehetünk egy p prímszámot az első A* szorzatból, és megállapíthatjuk, hogy az egyenlő a B* szorzat valamelyik számával. Ha így folytatjuk, a végén látjuk, hogy a két termék prímtényezőinek pontosan azonosnak kell lenniük. Ez azt bizonyítja, hogy egy pozitív egész számot csak egyetlen egyedi módon írhatunk fel prímtényezők szorzataként.