1.1. Oszthatóság és Prímszámok
A számelmélet alapvető fogalma az oszthatóság, amely az egészek körében értelmezett.
1.1.1. Definíció (Oszthatóság):
Legyenek $a, b \in \mathbb{Z}$. Azt mondjuk, hogy $a$ osztja $b$-t (jelölése: $a|b$), ha létezik olyan $k \in \mathbb{Z}$ egész szám, amelyre $b = a \cdot k$.
Fontos észrevételek:
- A nulla minden számmal osztható ($a|0$ minden $a$-ra).
- A nulla csak a nullát osztja ($0|b \implies b=0$).
- Egységnek nevezzük azokat a számokat, amelyek minden egészet osztanak (ezek az 1 és a -1).
1.1.2. Definíció (Prímszám):
Egy $p$ egész számot prímszámnak nevezünk, ha $p \neq 0, \pm 1$ (tehát nem nulla és nem egység), és csak a triviális osztói vannak (önmaga, az ellentettje és az egységek).
Megjegyzés: A jegyzetben általában a pozitív prímekre ($2, 3, 5, \dots$) korlátozódunk.
1.2. A Számelmélet Alaptétele (1.1.3. Tétel)
A tétel kimondja, hogy minden egységtől és nullától különböző egész szám lényegében egyértelműen felbontható prímszámok szorzatára.
1.1.3. Tétel:
Minden $1$-től, $0$-tól és $(-1)$-től különböző egész szám felbontható prímek szorzatára és ez a felbontás a tényezők sorrendjétől és előjelétől eltekintve egyértelmű.
A felbonthatóság bizonyítása (Algoritmikus eljárás):
Megadunk egy egyszerű eljárást, amely tetszőleges $n \in \mathbb{Z}, |n| > 1$ egészt prímtényezők szorzatára bont:
- Az eljárás végig fenntartja az $n$ egy ($\pm 1$-től különböző) egészek szorzatára való bontását. Kezdetben ez maga az $n$ szám, mint egytényezős szorzat.
- Ha egy ponton az $n = a_1 \cdot a_2 \cdot \dots \cdot a_k$ szorzatnál tartunk, és az összes $a_i$ tényező prím, akkor az eljárás megáll.
- Ha a tényezők között van összetett szám (legyen ez $a_i$), akkor annak van valódi osztója, így felírható $a_i = b \cdot c$ alakban, ahol $|b|, |c| > 1$ egészek.
- Ekkor az eljárás az $n$ felbontásában az $a_i$-t helyettesíti a $(b \cdot c)$ szorzattal, majd az eljárás ugyanígy folytatódik tovább.
Miért áll meg az eljárás?
Mivel az $n$ felbontásában a tényezők száma minden lépésben pontosan eggyel növekszik, és minden tényező abszolút értéke legalább $2$, az eljárás véges sok lépésben megáll. A lépésszám legfeljebb $\log_2 |n|$, az eredmény pedig az $n$ prímtényezőkre bontása. □
Prímtényezős Felbontó
1.3. A prímek száma és $\pi(n)$
1.2.1. Tétel: A prímek száma végtelen.
Bizonyítás (Indirekt):
Tegyük fel indirekt, hogy a prímek száma véges: $p_1, p_2, \dots, p_k$ az összes (pozitív) prím.
Legyen $N = p_1 \cdot p_2 \cdot \dots \cdot p_k + 1$. Ekkor $N$ (az 1.1.3. Tétel állítása szerint – itt az egyértelműséget nem is kell kihasználni) prímtényezők szorzatára bomlik (vagy maga is prím).
Azonban $N$ nem osztható a $p_1, p_2, \dots, p_k$ prímek egyikével sem (ugyanis mindegyikkel osztva 1 maradékot ad), így $N$ minden prímtényezője hiányzik a $p_1, p_2, \dots, p_k$ felsorolásból.
Ez az ellentmondás bizonyítja a tételt. □
1.2.3. Tétel: (A Nagy Prímszámtétel)
Jelölje $\pi(n)$ az $n$-nél nem nagyobb pozitív prímszámok számát.
1.4. A kongruencia fogalma és alapvető jellemzése
A kongruencia a számelmélet egyik legfontosabb eszköze, amely a maradékos osztáson alapuló egyenlőséget fogalmazza meg.
1.3.1. Definíció (Kongruencia):
Legyenek $a, b, m \in \mathbb{Z}, m \neq 0$ tetszőleges egészek. Azt mondjuk, hogy $a$ kongruens $b$-vel modulo $m$, ha $a$-t és $b$-t $m$-mel maradékosan osztva azonos maradékokat kapunk. Ennek a jele: $a \equiv b \pmod m$. Az $m$ számot a kongruencia modulusának nevezzük.
1.3.2. Állítás:
Tetszőleges $a, b, m \in \mathbb{Z}, m \neq 0$ egészekre $a \equiv b \pmod m$ akkor és csak akkor igaz, ha $m \mid a - b$.
Bizonyítás:
Jelölje $r_1$, illetve $r_2$ az $a$, illetve $b$ maradékát $m$-mel osztva. Eszerint $a = k_1 \cdot m + r_1$ és $b = k_2 \cdot m + r_2$ valamely $k_1, k_2$ és $0 \le r_1, r_2 \le |m| - 1$ egészekre.
Mivel $a$ és $b$ szerepe szimmetrikus, ezért feltehető, hogy $r_1 \ge r_2$. Ezekből:
vagyis $(a - b)$-t $m$-mel osztva a maradék $r_1 - r_2$.
Így $m \mid a - b$ akkor és csak akkor teljesül, ha $r_1 - r_2 = 0$, azaz $r_1 = r_2$. Ez pedig definíció szerint valóban ekvivalens azzal, hogy $a \equiv b \pmod m$ fennáll. ■
1.4.1. Műveletek kongruenciákkal (Tétel)
1.3.3. Tétel:
Tegyük fel, hogy $a \equiv b \pmod m$ és $c \equiv d \pmod m$ fennállnak az $a,b,c,d,m$ egészekre és $k \ge 1$ tetszőleges. Ekkor igazak az alábbiak:
- (i) $a + c \equiv b + d \pmod m$
- (ii) $a - c \equiv b - d \pmod m$
- (iii) $a \cdot c \equiv b \cdot d \pmod m$
- (iv) $a^k \equiv b^k \pmod m$
Bizonyítás:
A tétel feltételei az 1.3.2. Állítás szerint azt jelentik, hogy $m \mid a - b$ és $m \mid c - d$.
Mivel $m$-mel osztható számok összege és különbsége is nyilván $m$-mel osztható, ezért ezekből következik, hogy:
és $m \mid (a - b) - (c - d) = (a - c) - (b - d)$
vagyis (ismét az 1.3.2. Állítás miatt) a tétel (i) és (ii) állításai igazak.
Mivel egy $m$-mel osztható szám bármely többszöröse is nyilván $m$-mel osztható, ezért $m \mid a - b$-ből $m \mid c(a - b) = ac - bc$ következik.
Hasonlóan, $m \mid c - d$ miatt $m \mid b(c - d) = bc - bd$.
Ismét kihasználva, hogy $m$-mel osztható számok összege $m$-mel osztható, kapjuk:
Ez épp a tétel (iii) állítása (az 1.3.2. Állítást használva).
Végül a (iv) állítás következik a (iii)-ból: ha azt a $c = a$ és $d = b$ szereposztásban alkalmazzuk, akkor az $a^2 \equiv b^2 \pmod m$ kongruenciát kapjuk.
Erre és az $a \equiv b \pmod m$ kongruenciára újra (iii)-at alkalmazva kapjuk az $a^3 \equiv b^3 \pmod m$ kongruenciát, stb. $(k - 1)$ további ilyen lépés után jutunk az $a^k \equiv b^k \pmod m$ eredményre. □
Kidolgozott példa: Maradék meghatározása nagy számokra
Feladat:
Határozza meg a $(123 \cdot 46) + 11^4$ kifejezés 7-tel való osztási maradékát az 1.3.3. Tétel tulajdonságainak felhasználásával!
Megoldás menete a tétel alapján:
1. Alap-maradékok:
$123 \equiv 4 \pmod{7}$
$46 \equiv 4 \pmod{7}$
$11 \equiv 4 \pmod{7}$
2. Szorzat (iii. állítás):
$123 \cdot 46 \equiv 4 \cdot 4 = 16$
$16 \equiv \mathbf{2} \pmod{7}$
3. Hatvány (iv. állítás):
$11^4 \equiv 4^4 \pmod{7}$
$4^2 = 16 \equiv 2 \implies (4^2)^2 \equiv 2^2 = \mathbf{4}$
4. Összeg (i. állítás):
$2 + 4 = \mathbf{6} \pmod{7}$
Végeredmény:
A tétel segítségével a maradék meghatározásához elegendő a részeredmények maradékaival elvégezni a műveleteket.
1.4.2. Kongruenciák egyszerűsítése
1.3.4. Tétel:
Legyenek $a, b, c, m$ tetszőlegesek és $d = (c, m)$ (ahol a gömbölyű zárójel a legnagyobb közös osztót jelöli). Ekkor $a \cdot c \equiv b \cdot c \pmod{m}$ akkor és csak akkor igaz, ha $a \equiv b \pmod{\frac{m}{d}}$.
Bizonyítás:
Legyen $c' = \frac{c}{d}$ és $m' = \frac{m}{d}$. Nyilván $c'$ és $m'$ egészek (mert $d$ közös osztója $c$-nek és $m$-nek). Továbbá $(c', m') = 1$, ugyanis ellenkező esetben $(c', m') \cdot d$ egy $d$-nél nagyobb közös osztója volna $c$-nek és $m$-nek.
$a \cdot c \equiv b \cdot c \pmod{m}$ az 1.3.2. Állítás szerint azt jelenti, hogy $m \mid ac - bc = c(a - b)$. Ez ekvivalens azzal, hogy $m' \mid c'(a - b)$ (mert az $m \cdot k = c(a - b)$ egyenlet is ekvivalens az $m' \cdot k = c'(a - b)$ egyenlettel). Megmutatjuk, hogy ez tovább ekvivalens az $m' \mid a - b$ oszthatósággal – amivel (ismét az 1.3.2. Állítás miatt) a tétel bizonyítása teljes lesz.
Valóban, egyrészt $m' \mid a - b$-ből nyilván következik $m' \mid c'(a - b)$ (hiszen $m'$-vel osztható szám bármely többszöröse is az). Megfordítva, ha $m' \mid c'(a - b)$, akkor $c'$ és $a - b$ prímtényezős felbontásának egyesítése már tartalmazza az $m'$ prímtényezős felbontását. Mivel azonban $(c', m') = 1$, ezért $c'$ és $m'$ prímtényezős felbontásában nincs közös prím, így $m'$ prímtényezős felbontását teljes egészében az $a - b$ prímtényezős felbontásának kell tartalmaznia. Vagyis $m' \mid a - b$ valóban igaz. ■
Speciális eset: Ha $(c, m) = 1$, akkor a kongruenciát egyszerűen eloszthatjuk $c$-vel, és a modulus változatlan marad: $ac \equiv bc \pmod m \implies a \equiv b \pmod m$.