2. Számelmélet

A természetes számok halmazán értelmezett számelmélet a matematika egyik legősibb ága. Az emelt szintű érettségi az alábbi fogalmak és tételek magabiztos alkalmazását várja el:

• Oszthatóság: Az $a$ egész szám osztója a $b$ egész számnak (jelölése: $a|b$), ha létezik olyan $k$ egész szám, amelyre $b = a \cdot k$.
• Prímszám: Olyan természetes szám, amelynek pontosan két pozitív osztója van: az $1$ és önmaga (pl. 2, 3, 5, 7, 11). Fontos: az 1 nem prímszám és nem is összetett szám!
• Összetett szám: Olyan természetes szám, amelynek kettőnél több pozitív osztója van.
• Relatív prímek: Két vagy több egész szám relatív prím, ha a legnagyobb közös osztójuk (LNKO) pontosan $1$. Nem szükséges, hogy maguk a számok prímek legyenek (pl. a 8 és a 15 relatív prímek).
• Oszthatósági szabályok: Ismerni kell a 2, 3, 4, 5, 6, 8, 9, és 10 hatványaira vonatkozó szabályokat. Például egy szám akkor osztható 9-cel, ha a számjegyeinek összege osztható 9-cel.

Tétel (A számelmélet alaptétele): Minden 1-nél nagyobb természetes szám felbontható prímszámok szorzatára, és ez a felbontás – a tényezők sorrendjétől eltekintve – egyértelmű.

Tétel Bizonyítással: Végtelen sok prímszám van.

Ezt az állítást Euklidész bizonyította először az i. e. 3. században, egy zseniális indirekt bizonyítással.

Bizonyítás:

1. Tegyük fel az állítás ellenkezőjét (indirekt feltevés): Tegyük fel, hogy véges sok prímszám létezik. Ha véges sok van, akkor ezeket fel tudjuk sorolni: $p_1, p_2, p_3, \dots, p_n$, ahol $p_n$ a létező legnagyobb prímszám.
2. Képezzünk egy új $P$ számot úgy, hogy az összes felsorolt prímszámot összeszorozzuk, majd az eredményhez hozzáadunk 1-et:
   $$P = (p_1 \cdot p_2 \cdot p_3 \cdot \dots \cdot p_n) + 1$$
3. Vizsgáljuk meg a $P$ szám oszthatóságát! Ha a $P$-t elosztjuk az eredeti listánk bármelyik $p_k$ prímszámával, a maradék mindig 1 lesz (hiszen a szorzat rész osztható $p_k$-val).
4. Ez azt jelenti, hogy $P$ egyetlen általunk ismert (listázott) prímszámmal sem osztható.
5. A számelmélet alaptétele szerint viszont $P$-nek lennie kell prímtényezős felbontásának. Mivel egyetlen "régi" prím sem osztja, ezért $P$-nek vagy saját magának is egy új prímszámnak kell lennie (ami nagyobb $p_n$-nél), vagy olyan prímszámok szorzatának, amelyek nem szerepeltek a listánkon.
6. Mindkét esetben találtunk egy olyan prímszámot, ami nem volt benne a "minden prímet tartalmazó" véges listánkban. Ez ellentmondás. Az indirekt feltevésünk tehát hamis, a prímszámok száma végtelen. $\blacksquare$

Tétel: Osztók számának meghatározása

Ha egy $n$ természetes szám prímtényezős felbontása (kanonikus alakja) $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dots \cdot p_k^{\alpha_k}$, akkor az $n$ szám pozitív osztóinak számát (melyet gyakran $d(n)$-nel jelölünk) a kitevők segítségével kiszámíthatjuk:

Magyarázat: Egy osztó megalkotásakor a $p_1$ prímszámot $0$-tól $\alpha_1$-ig bármilyen kitevővel választhatjuk (ez $\alpha_1+1$ lehetőség). Ezt kombináljuk a többi prím választási lehetőségeivel.

A mindennapi életben a 10-es alapú (decimális) helyiértékes számrendszert használjuk. Azonban az informatika (2-es, 8-as, 16-os alap) és a mértékegységek (pl. 60-as alap az időnél) miatt más alapok ismerete is elengedhetetlen. Emelt szinten vizsgakövetelmény az $n$ alapú ($n \le 9$) számrendszerekben történő számítás, összeadás és kivonás.

Átírás 10-es alapúból $n$ alapúba: Folyamatos maradékos osztást alkalmazunk az $n$ alappal, a maradékokat pedig fordított sorrendben olvassuk össze.

Műveletek $n$ alapú számrendszerben: Az összeadás és kivonás szabályai megegyeznek a 10-es alapúéval, csupán a "tízes átlépés" helyett "$n$-es átlépés" történik (pl. 5-ös számrendszerben az $1 + 4 = 10_{(5)}$).

Határozza meg a legkisebb olyan $N$ természetes számot, amely pontosan 15 pozitív osztóval rendelkezik!