AlegsaOnline.com

Az aritmetika alaptétele: egyedi faktorizáció és prímszámok

Az aritmetika alaptétele: minden egész szám egyedi prímszám-szorzattal írható fel. Ismerd meg az egyedi faktorizáció elvét, illusztráló példákat és kriptográfiai alkalmazásait.

Szerző: Leandro Alegsa

29-01-2026

Az aritmetika alaptétele (más néven az egyedi faktorizáció tétele) a számelmélet egyik alapvető tétele. A tétel röviden így fogalmazható meg: minden 1-nél nagyobb pozitív egész szám felírható prímszámok szorzataként, és ez a felírás egyedi a prímszámok sorrendjét leszámítva. Másképp: ha két prímekből álló szorzat adja ugyanazt a számot, akkor a tényezők ugyanazok, csak esetleg más sorrendben fordulnak elő.

Példák:

6936 = 2³ * 3 * 17²

1200 = 2⁴ * 3 * 5²

Ha valaki más módon írná fel ugyanazokat a számokat prímszámok szorzataként, akkor a prímszámokat a megfelelő sorrendbe állítva ugyanazokat a tényezőket kapjuk (az egyetlen eltérés a sorrend lehet).

Mit értünk prímen és mi a tétel pontos hatóköre?

Prímszám alatt olyan 1-nél nagyobb természetes számot értünk, amelynek csak 1 és önmaga a pozitív osztója. A tétel tehát a 2, 3, 4, ... számokra vonatkozik; a 1 különleges eset: nem prímszám és nem is tekintjük a tétel alanyaként, mivel a 1-nek nincs nemtriviális prímosztója.

Canonicalis alak és hatványok

Gyakran a felírást a következő kanonikus formában adjuk meg:

n = p₁^a1 p₂^a2 ... p_k^ak, ahol p₁ < p₂ < ... < p_k prímszámok és az a_i pozitív egész kitevők. Ez a forma egyértelműsíti a tényezők sorrendjét és az egyes prímszámok előfordulásainak számát (a kitevőket).

Bizonyítás vázlata

Létezés: A létezést egyszerű indukcióval vagy osztók vizsgálatával mutatjuk meg. Ha n prímszám, kész. Ha nem, van két nemtriviális osztója n = ab, ahol 1 < a, b < n. Ekkor a és b kisebbek, őket feltételezés szerint felírhatjuk prímszámok szorzataként, így n is felírható.
Egyediség: Az egyediséget az ún. Eukleidész lemma (ha p prímszám és p osztja ab-t, akkor p osztja a-t vagy b-t) segítségével igazoljuk. Két különböző prímfelbontást feltételezve lépésről lépésre megmutatható, hogy az egyik felbontás minden prímtényezője megtalálható a másikban, így a kitevők is megegyeznek, tehát a felbontások csak sorrendben térhetnek el.

Alkalmazások és jelentőség

A tétel alapvető szerepet játszik az aritmetikai függvények, például az osztók számát (τ(n)), az osztók összegét (σ(n)) vagy Euler-féle φ(n) függvényt vizsgáló képletek kialakításában, mert ezek számítása a prímtényezők kitevőin alapul.
Az kriptográfiában is fontos: sok nyilvános kulcsú titkosítási eljárás (például az RSA) a nagy számok prímtényezőkre bontásának nehézségére alapoz. A nagy semiprímek (két nagy prímszám szorzatai) faktorizálása számításilag nagy erőforrást igényel, ezért ezek a módszerek biztonságosnak tekinthetők bizonyos paramétereknél.
A tétel segít továbbá az olyan alapvető műveletekben, mint a legnagyobb közös osztó (lnko) és legkisebb közös többszörös (lkkt) számítása: ezek egyszerűen a prímtényezők kitevőinek minimuma illetve maximuma alapján adhatók meg.

Gyakorlati tényezőzési módszerek

A kis számok faktorizálása egyszerű próbás osztással elvégezhető. Nagyobb számok esetén gyorsabb algoritmusokat használnak, például Pollard-rho, kvadratikus szita és a általános számmező-szita (GNFS). Ezek fejlődése határozza meg, milyen nagyságú számok tekinthetők gyakorlatilag faktorizálhatatlannak napjaink számítástechnikai lehetőségei mellett.

Összefoglalva: az aritmetika alaptétele biztosítja, hogy a prímtényezőkre bontás mindig lehetséges és egyértelmű (sorrenden kívül), és ez a tulajdonság a számelmélet és a gyakorlati alkalmazások — köztük a kriptográfia — egyik sarokköve.

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.

Kérdések és válaszok

K: Mi az aritmetika alaptétele?

V: Az aritmetika alaptétele a számelmélet egyik tétele, amely kimondja, hogy minden 1-nél nagyobb pozitív egész szám felírható prímszámok szorzataként, és csak egyféleképpen írható fel.

K: Hogyan használható ez a tétel?

V: Ez a tétel a kriptográfiában használható.

K: Mi történik, ha két ember két különböző módot talál ugyanannak a számnak az írására?

V: Ha két ember két különböző módot talál ugyanannak a számnak az írására, akkor az egyetlen dolog, ami különbözhet, az a prímek írási sorrendje.

K: Mi az a faktorizálás?

V: A faktorizálás egy adott számot alkotó összes prímszám megtalálása.

K: A 6936 példa a prímszámra?

V: Nem, a 6936 nem prímszám; felírható úgy is, hogy 23 - 3 - 172.

Nem, a 6936 nem prímszám; felírható 23 - 3 - 172 alakban.