3. Tétel

Oszthatóság, oszthatósági szabályok és tételek. Prímszámok. Számrendszerek.

Részletes kidolgozás az emelt szintű matematika érettségi szóbeli vizsgájára. Ez a tétel átfogja a számelmélet alapjait: az oszthatósági szabályokat, a prímszámok tulajdonságait és a számelmélet alaptételét. Szerepel benne az emelt szinten elvárt Euklidész-féle bizonyítás a prímszámok végtelenségéről [cite: 82], valamint a számrendszerek közötti átváltások és műveletek szabályai[cite: 82].

Oszthatóság és oszthatósági szabályok

Definíció: Az $a$ egész szám osztója a $b$ egész számnak ($a \mid b$), ha létezik olyan $k$ egész szám, amelyre igaz, hogy $b = a \cdot k$. Ekkor $b$-t az $a$ többszörösének nevezzük[cite: 82]. A 0 minden számnak többszöröse, de nullával nem osztunk.

Oszthatósági szabályok 10-es számrendszerben:

  • 2-vel, 5-tel, 10-zel: Csak az utolsó számjegyet kell vizsgálni. Egy szám akkor osztható 2-vel, ha utolsó számjegye páros (0, 2, 4, 6, 8). 5-tel osztható, ha 0-ra vagy 5-re végződik.
  • 4-gyel, 25-tel: Az utolsó két számjegyből álló számot kell vizsgálni. Pl. 4-gyel osztható, ha az utolsó két jegyből álló szám osztható 4-gyel.
  • 8-cal: Az utolsó három számjegyből álló szám osztható kell legyen 8-cal.
  • 3-mal, 9-cel: A számjegyek összegét vizsgáljuk. Egy szám akkor osztható 3-mal (vagy 9-cel), ha a számjegyeinek összege osztható 3-mal (vagy 9-cel)[cite: 82].
  • 6-tal: Ha a szám 2-vel és 3-mal is osztható (mivel a 2 és a 3 relatív prímek).

Legnagyobb közös osztó (LNKO) és Legkisebb közös többszörös (LKKT):

Két szám LNKO-ját úgy kapjuk, hogy a közös prímtényezőket a kisebbik hatványon összeszorozzuk. Az LKKT-t úgy számítjuk, hogy az összes előforduló prímtényezőt a legnagyobb előforduló hatványon összeszorozzuk[cite: 82]. Fontos összefüggés két pozitív egész számra: $\text{LNKO}(a,b) \cdot \text{LKKT}(a,b) = a \cdot b$.

Prímszámok és a Számelmélet Alaptétele

Definíciók:

  • Prímszám (törzsszám): Olyan pozitív egész szám, amelynek pontosan két pozitív osztója van: az 1 és önmaga (pl. 2, 3, 5, 7, 11...). Az 1 nem prímszám és nem is összetett szám[cite: 82].
  • Összetett szám: Olyan pozitív egész szám, amelynek kettőnél több pozitív osztója van[cite: 82].
  • Relatív prímek: Két egész szám relatív prím, ha a legnagyobb közös osztójuk 1[cite: 82].
Tétel: A számelmélet alaptétele

Minden 1-nél nagyobb összetett szám egyértelműen (a tényezők sorrendjétől eltekintve) felbontható prímszámok szorzatára[cite: 82].

$$ n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dots \cdot p_k^{\alpha_k} $$

Osztók számának meghatározása (Emelt szintű követelmény):

Ha egy $n$ természetes szám prímtényezős felbontása a fenti alakú, akkor a pozitív osztóinak száma (jelölése gyakran $d(n)$) könnyen meghatározható a kitevők segítségével[cite: 82]:

$$ d(n) = (\alpha_1 + 1)(\alpha_2 + 1)\dots(\alpha_k + 1) $$

Ezt a kombinatorika (független választások) segítségével indokolhatjuk: minden $p_i$ prímtényező a $0, 1, \dots, \alpha_i$ kitevők bármelyikével szerepelhet egy osztóban, ami pontosan $(\alpha_i + 1)$ lehetőséget jelent minden egyes prím esetében.

Kiemelt bizonyítás: A prímszámok végtelensége

Az emelt szintű érettségi vizsgán az egyik legszebb és leggyakrabban előforduló számonkérés Euklidész híres bizonyítása[cite: 82].

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

Bizonyítás (Indirekt módon):

Tegyük fel indirekt módon, hogy véges sok prímszám létezik. Ha véges sok van, akkor ezeket sorba tudjuk rendezni és fel tudjuk sorolni: $p_1, p_2, p_3, \dots, p_n$, ahol $p_n$ az "utolsó", azaz a legnagyobb prímszám.

Képezzünk ebből a véges halmazból egy új $N$ számot úgy, hogy az összes prímszámot összeszorozzuk, és a szorzathoz hozzáadunk 1-et:

$$ N = (p_1 \cdot p_2 \cdot \dots \cdot p_n) + 1 $$

A kapott $N$ szám 1-nél nagyobb, így a számelmélet alaptétele értelmében [cite: 82] kell, hogy legyen prímosztója. Vizsgáljuk meg, osztható-e $N$ az általunk feltételezett "összes" prímszám valamelyikével!

Ha $N$-et elosztjuk $p_1$-gyel, $p_2$-vel, vagy bármelyik $p_i$-vel a listából, a maradék mindig pontosan 1 lesz, hiszen a szorzat rész osztható velük, az utána álló +1 miatt viszont a maradék 1 marad.

Tehát az $N$ szám a listán szereplő egyetlen prímszámmal sem osztható. Ebből két eset lehetséges:

  1. Maga $N$ is prímszám, és mivel nagyobb, mint $p_n$, találtunk egy új prímet.
  2. $N$ összetett szám, de prímosztói nincsenek a listán, így létezik olyan prímszám, ami a felsorolásunkból kimaradt.

Mindkét eset ellentmond az indirekt feltevésünknek, miszerint fel tudtuk sorolni az összes prímszámot. Mivel az indirekt feltevés ellentmondásra vezetett, az állítás igaz: végtelen sok prímszám van. Q.E.D.

Számrendszerek és Helyiértékes írásmód

Egy $q$ alapú számrendszerben ($q > 1$ egész) a számokat a $0, 1, \dots, (q-1)$ számjegyek segítségével írjuk fel[cite: 82]. A helyiértékes írásmód (pozicionális számrendszer) lényege, hogy egy számjegy tényleges értéke attól függ, hogy a számban milyen pozíciót (helyiértéket) foglal el.

Egy $N$ természetes szám alaki értékeiből ($a_k$) így kapjuk meg a valódi értéket:

$$ N = a_k \cdot q^k + a_{k-1} \cdot q^{k-1} + \dots + a_1 \cdot q^1 + a_0 \cdot q^0 $$

Átváltás számrendszerek között[cite: 82]:

  • $n$ alapúból 10-es alapúba: A fenti polinom alakot használva, a helyiértékeket a számjegyekkel megszorozva és összeadva kapjuk meg a 10-es számrendszerbeli értéket.
  • 10-es alapúból $n$ alapúba: A 10-es számrendszerbeli számot maradékosan osztjuk az $n$ alappal. A maradékokat feljegyezzük, a hányadost újra osztjuk, egészen addig, amíg a hányados 0 nem lesz. A feljegyzett maradékokat fordított sorrendben (az utolsótól az első felé) leírva kapjuk az $n$ alapú alakot.

Műveletek $n$ alapú számrendszerben (Emelt szint)[cite: 82]:

Az írásbeli összeadás és kivonás algoritmusa $n \le 9$ alapú számrendszerben is megegyezik a 10-es számrendszerben megszokottal, csupán a "tízes átlépés" helyett "$n$-es átlépés" történik. Például 5-ös számrendszerben $3_5 + 4_5 = 12_5$, mert $3+4=7$, ami egy ötös csoport és kettő maradék.

Alkalmazások és Matematikatörténet

Az emelt szóbeli vizsgán extra pontokért (4 pont) szükséges a tételhez kapcsolódó alkalmazások vagy történeti vonatkozások ismertetése[cite: 250].

Matematikatörténet:

  • Eratoszthenész szitája: Ókori görög módszer egy adott számig az összes prímszám megkeresésére. A módszer lényege, hogy felírjuk a számokat, majd a 2-től kezdve minden prímnek a többszöröseit "kiszitáljuk" (kihúzzuk).
  • Euklidész (i.e. 300 körül): Elemek című művében nemcsak a geometriát rendszerezte, hanem a számelmélet alapjait is lefektette. Az LNKO megkeresésére szolgáló Euklideszi-algoritmus, és a fentebb bizonyított prímszámok végtelenségére vonatkozó tétel is tőle származik.

Gyakorlati és tudományos alkalmazások:

  • Kriptográfia (Titkosítás): Az internetes biztonság alapja az RSA algoritmus. Ez a titkosítás azon a matematikai aszimmetrián alapul, hogy bár két hatalmas prímszámot összeszorozni számítógéppel is a másodperc töredéke, a kapott óriási szorzatot (összetett számot) visszafejteni az eredeti prímtényezőkre számításelméletileg rendkívül lassú, szinte lehetetlen feladat.
  • Informatika és Számítástechnika: A számítógépek hardveresen kettes (bináris) számrendszert használnak ($n=2$), mivel a logikai kapuk (feszültség van/nincs) ezt tudják értelmezni. A memória-címzések és a színkódolások viszont gyakran a kettes számrendszerrel rokon 16-os (hexadecimális) számrendszert használják a rövidebb, ember számára is olvashatóbb leírás érdekében.
  • ISBN vonalkódok és Ellenőrzőösszegek: A könyveken található ISBN számok, a bankszámlaszámok és a személyi igazolvány számok is az oszthatóság elvein (moduláris aritmetika) alapuló ellenőrző számjegyeket tartalmaznak, amik kiszűrik az elgépeléseket.