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.
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 = 23 * 3 * 172
1200 = 24 * 3 * 52
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 = p1a1 p2a2 ... pkak, ahol p1 < p2 < ... < pk 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.
Keres