A számelmélet alaptétele

A számelmélet alaptétele, röviden SzAT a számelmélet egyik legalapvetőbb tétele, mely szerint minden 1-nél nagyobb természetes szám felbomlik, méghozzá (a szorzótényezők sorrendjétől eltekintve) egyféleképpen, prímszámok szorzatára.^[1] Azaz minden természetes számnak van ún. kanonikus felbontása vagy prímfelbontása: ${\displaystyle n=\prod p_{i}^{\alpha _{i}}}$.

Például: ${\displaystyle 12=2\cdot 2\cdot 3}$. Ha összevonjuk az azonos tényezőket, így fogalmazhatunk: minden 1-nél nagyobb összetett szám pontosan egyféleképpen írható fel prímhatványok szorzataként: ${\displaystyle 12=2^{2}\cdot 3}$. Ezt az „egyféle” felírást a szám kanonikus alakjának is nevezik.

Az egység olyan szám, illetve elem, mellyel minden szám, illetve elem osztható. Az egész számok körében az egységek az egy és a mínusz egy. Azt mondjuk, hogy két szám, illetve elem asszociált, ha egymás egységszeresei.

Az egész számok körében: ha n 0-tól és egységtől (1, ‒1) különböző egész szám, akkor felírható prímek szorzataként és ha ${\displaystyle n=p_{1}\cdots p_{r}=q_{1}\cdots q_{s}}$ két ilyen felírás, akkor ${\displaystyle r=s}$ és a ${\displaystyle p_{1},\dots ,p_{r}}$ illetve a ${\displaystyle q_{1},\dots ,q_{s}}$ számok kölcsönösen megfeleltethetők egymásnak úgy, hogy az egymással megfeleltetett számok egymás asszociáltjai (azaz azonosak vagy egymás ellentettjei) ${\displaystyle -12=(-2)\cdot 2\cdot 3=2\cdot 2\cdot (-3)}$. Egy kevésbé nehézkes, bár kissé homályosabb megfogalmazás szerint, minden 1-nél nagyobb abszolút értékű egész szám felbomlik, mégpedig a tényezők sorrendjétől és előjelétől eltekintve egyértelműen, prímek szorzatára.

Különös módon, bár már Eukleidész is igazolt az alaptétellel ekvivalens állításokat és persze hallgatólagosan minden számelmélettel foglalkozó matematikus használta, először Gauss mondta ki és bizonyította be 1801-ben kiadott Disquisitiones Arithmeticae című művében.

Külön-külön bizonyítjuk azt, hogy minden 1-nél nagyobb összetett szám előáll prímszámok szorzataként (egzisztencia), illetve, hogy csak egyféleképpen (unicitás). Az első bizonyításhoz a teljes indukció, a másodikhoz a végtelen leszállás módszerét alkalmazzuk.

Létezés. A legkisebb, 1-nél nagyobb egész szám a 2, ami prímszám, tehát igaz rá az állítás. Most tegyük fel, hogy az állítás igaz minden ${\displaystyle N}$-nél kisebb egész számra. Ekkor, ha ${\displaystyle N}$ maga is prímszám, akkor készen vagyunk. Ha nem, akkor felbontható ${\displaystyle N=a\cdot b}$ alakra, ahol mind ${\displaystyle a}$ és mind ${\displaystyle b}$ 1-nél nagyobb és ${\displaystyle N}$-nél kisebb szám. Viszont ${\displaystyle a}$ és ${\displaystyle b}$ - az indukciós feltevés szerint - felbontható prímszámok szorzatára, tehát a szorzatuk, ${\displaystyle N}$ is. Ezzel az egzisztenciát bebizonyítottuk.

Egyértelműség. Tegyük fel az állításunk ellenkezőjét, vagyis hogy van olyan 1-nél nagyobb természetes szám, ami többféleképpen is felírható prímszámok szorzataként. Az ilyen számok között kell legyen egy legkisebb, jelöljük őt ${\displaystyle N}$-nel. Eszerint

${\displaystyle N=p_{1}\cdots p_{r}=q_{1}\cdots q_{s}}$

alakban írható, ahol a ${\displaystyle p_{1},\dots ,p_{r}}$ és a ${\displaystyle q_{1},\dots ,q_{s}}$ sorozatok nem egymás átrendezései. Ha van olyan prímszám, ami mindkét oldalon előfordul, mondjuk ${\displaystyle p_{1}=q_{1}}$, akkor vele egyszerűsítve

${\displaystyle p_{2}\cdots p_{r}=q_{2}\cdots q_{s}}$

adódik és ez az ${\displaystyle N/p_{1}<N}$ szám kétféle felbontása, ami ellentmond annak a feltételezésünknek, hogy a ${\displaystyle N}$ a legkisebb többféleképpen felbontható természetes szám. Feltehetjük tehát, hogy a ${\displaystyle p_{1},\dots ,p_{r}}$ számok egyike sem egyezik meg a ${\displaystyle q_{1},\dots ,q_{s}}$ számok egyikével sem. Tegyük fel, hogy e számok közül ${\displaystyle p_{1}}$ a legkisebb. Ha a ${\displaystyle q_{1}\cdots q_{s}}$ szorzat minden tényezőjét áthelyettesítjük ${\displaystyle p_{1}}$-gyel vett maradékával, akkor egy olyan ${\displaystyle q'_{1}\cdots q'_{s}}$ szorzatot kapunk, aminek egyrészt ${\displaystyle p_{1}}$-gyel vett maradéka ugyanaz, mint ${\displaystyle q_{1}\cdots q_{s}}$-é, tehát 0, másrészt ${\displaystyle q'_{i}<q_{i}}$ (${\displaystyle i=1,\dots ,s}$) miatt a szorzat értéke is kisebb ${\displaystyle N}$-nél. A szorzat értéke legyen ${\displaystyle N'}$. Tehát ${\displaystyle N'}$ egy olyan ${\displaystyle N}$-nél kisebb szám, amely ${\displaystyle p_{1}}$-gyel osztható, azaz létezik olyan prímtényezős felbontása, amelyben ${\displaystyle p_{1}}$ szerepel (a tétel már igazolt első fele miatt az egész ${\displaystyle N'/p_{1}}$ is prímtényezőkre bontható), másrészt ${\displaystyle N'}$ felírható ${\displaystyle p_{1}}$-től különböző prímek szorzataként is, hiszen a ${\displaystyle q'_{i}<p_{1}}$ (${\displaystyle i=1,\dots ,s}$) tényezők közül, amelyik nem prím, az is kizárólag ${\displaystyle p_{1}}$-nél kisebb prímekre bontható. Mindez ellentmond a kiinduló feltevésünknek, miszerint ${\displaystyle N}$ a legkisebb ilyen szám.

A SzAT egyik legelterjedtebb bizonyítása az euklideszi algoritmus és a legnagyobb közös osztó fogalmára épül; ennek fontos általánosítása az euklideszi gyűrűkben értelmezett prímfaktorizáció végrehajthatósága és egyértelműsége. Euklideszi gyűrűre példa a Gauss-egészek és az Eisenstein-egészek gyűrűje. Azokat a gyűrűket, melyekben a számelmélet alaptételével analóg kijelentés igaz, alaptételes gyűrűnek nevezzük. Ha egy integritási tartomány euklideszi gyűrű, akkor főideálgyűrű, és minden főideálgyűrű gyűrű alaptételes gyűrű, de ezek megfordítása nem igaz. Egységelemes integritási tartományokban akkor és csak akkor igaz a SzAT, ha minden felbonthatatlan elem prímelem és főideálok minden növő sorozata megszakad.

Kvadratikus testeknek nevezzük azokat a testeket, amelyek a racionális számok testének egyszerű algebrai négyzetgyök-bővítéseiből adódnak. Ezen kvadratikus testek egészeinek gyűrűit vizsgálva juthatunk el olyan gyűrűkhöz, amelyekben igaz a maradékos osztás tétele, így a számelmélet alaptétele is. Ezen gyűrűk közül néhány számelméleti szempontból ugyanúgy viselkedik, mint például az egész számok gyűrűje. 21 kvadratikus euklideszi test létezik. Ezek a következő számok négyzetgyökeivel állíthatók elő: -1, -2, -3, -7, -11, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 és 73. Bizonyított, hogy nincs több kvadratikus euklideszi test.

• kanonikus alakok listája

• Alice és Bob - 16. rész: Alice és Bob alaptétele
• Alice és Bob - 17. rész: Alice és Bob ókori haverja
• Alice és Bob - 19. rész: Alice és Bob ideáljai