´ A SZAMELM ´ ´ BEVEZETES ELETBE v´ azlat az el˝oad´ashoz† (2013 ˝oszi f´el´ev) Waldhauser Tam´ as
1. Oszthat´ os´ ag, legnagyobb k¨ oz¨ os oszt´ o, pr´ımfaktoriz´ aci´ o az eg´ esz sz´ amok k¨ or´ eben Az oszthat´ os´ agi rel´ aci´ o alapvet˝ o tulajdons´ agai oja a b eg´esz sz´ amnak (b t¨ obbsz¨ or¨ ose a-nak), ha l´etezik olyan 1.1. Defin´ıci´ o. Azt mondjuk, hogy az a eg´esz sz´ am oszt´ c eg´esz sz´ am, amelyre b = ac. Jel¨ ol´ es. Az oszthat´os´ agi rel´ aci´ ot | jel¨oli: a | b ⇐⇒ ∃c ∈ Z : b = ac. 1.2. T´ etel. Tetsz˝ oleges a, b, c eg´esz sz´ amokra ´erv´enyesek az al´ abbiak: (1) a | a;
(6) a | 1 ⇐⇒ a = ±1;
(2) (a | b ´es b | c) =⇒ a | c;
(7) 0 | a ⇐⇒ a = 0;
(3) (a | b ´es b | a) ⇐⇒ b = ±a;
(8) (a | b ´es a | c) =⇒ a | b ± c;
(4) 1 | a; (5) a | 0;
(9) a | b =⇒ a | bc; (10) a | b ⇐⇒ ac | bc, ha c 6= 0; (11) a | b =⇒ |a| ≤ |b|, ha b 6= 0.
R´ eszbenrendez´ esek 1.3. Defin´ıci´ o. Adott A halmazon ´ertelmezett rel´ aci´ o n A-beli elemekb˝ol alkotott elemp´arok halmaz´ at ´ertj¨ uk, azaz egy tetsz˝oleges ρ ⊆ A × A halmazt. Jel¨ ol´ es. Az egyszer˝ us´eg kedv´e´ert (a, b) ∈ ρ helyett gyakran azt ´ırjuk, hogy aρb. 1.4. Defin´ıci´ o. R´ eszbenrendez´ esi rel´ aci´ o nak nevezz¨ uk a ρ ⊆ A × A rel´ aci´ ot, ha rendelkezik az al´ abbi h´arom tulajdons´aggal: (1) ∀a ∈ A : aρa (reflexivit´as); (2) ∀a, b ∈ A : (aρb ´es bρa) =⇒ a = b (antiszimmetria); (3) ∀a, b, c ∈ A : (aρb ´es bρc) =⇒ aρc (tranzitivit´as). Ha m´eg a k¨ovetkez˝ o tulajdons´ ag is teljes¨ ul, akkor ρ-t teljes rendez´ esnek (vagy line´ aris rendez´esnek) nevezz¨ uk: (4) ∀a, b ∈ A : aρb vagy bρa (dichot´ omia). Jel¨ ol´ es. A r´eszbenrendez´eseket szok´ as a ≤ szimb´olummal jel¨olni, m´eg akkor is, ha az alaphalmaz elemei esetleg nem is sz´ amok. Ha a ≤ b de a 6= b, akkor azt ´ırjuk, hogy a < b. eszbenrendezett halmaz on egy (A; ≤) p´art ´ert¨ unk, ahol A egy nem¨ ures halmaz, ´es ≤ r´eszbenrendez´es 1.5. Defin´ıci´ o. R´ A-n. 1.6. Defin´ıci´ o. Legyen (A; ≤) egy r´eszbenrendezett halmaz, ´es legyen a, b ∈ A. Azt mondjuk, hogy b fedi a-t, ha a < b, de nem l´etezik olyan c ∈ A, amelyre a < c < b. Ezt a t´enyt a ≺ b jel¨oli, ´es a ≺ rel´ aci´ ot az adott r´eszbenrendez´eshez esi rel´ aci´ o nak h´ıvjuk. tartoz´ o fed´ 1.7. T´ etel. V´eges r´eszbenrendezett halmazt egy´ertelm˝ uen meghat´ arozza a fed´esi rel´ aci´ oja. 1.8. Defin´ıci´ o. Egy v´eges (A; ≤) r´eszbenrendezett halmaz Hasse-diagramj´ an egy ´abr´at ´ert¨ unk, amelyn´el A elemeit (s´ıkbeli) pontokkal ´abr´azoljuk oly m´odon, hogy a < b eset´en a b-nek megfelel˝o pont f¨oljebb” van, mint az a-nak megfelel˝o ” pont, ´es e k´et pontot akkor ´es csak akkor k¨otj¨ uk ¨ossze, ha b fedi a-t. † A term´ eszetes sz´ amok halmaz´ at N, a nemnegat´ıv eg´ esz sz´ amok halmaz´ at N0 jel¨ oli, azaz N = {1, 2, 3, . . .} ´ es N0 = {0, 1, 2, . . .}. A csillaggal jel¨ olt t´ eteleket nem bizony´ıtjuk.
1
1.9. Defin´ıci´ o. Legyen (A; ≤) egy r´eszbenrendezett halmaz. Az a ∈ A elemet minim´ alis elemnek nevezz¨ uk, ha nincs uk, ha ˝o mindenki m´asn´al kisebb. Hasonl´oan a ∈ A maxim´ alis, ha nincs n´ala kisebb elem, ´es legkisebb elemnek nevezz¨ n´ala nagyobb elem, ´es a ∈ A legnagyobb, ha ˝o mindenki m´asn´al nagyobb. Form´alisan: • a minim´alis ⇐⇒ ∄b ∈ A: b < a; • a legkisebb ⇐⇒ ∀b ∈ A: a ≤ b; • a maxim´alis ⇐⇒ ∄b ∈ A: b > a; • a legnagyobb ⇐⇒ ∀b ∈ A: a ≥ b.
6. A pr´ımsz´ amok eloszl´ asa
1.10. Megjegyz´ es. Az 1.2. T´etelbeli (1)-(5) tulajdons´ agok szerint (N0 ; |) r´eszbenrendezett halmaz, amelynek a legkisebb eleme 1, a legnagyobb eleme pedig 0 (!).
6.3. T´ etel. V´egtelen sok 4k + 1 alak´ u pr´ımsz´ am van.
1.11. T´ etel. R´eszbenrendezett halmazban legf¨ oljebb egy legkisebb elem l´etezhet. Ha van legkisebb elem, akkor az minim´ alis elem is, s˝ ot o ˝ az egyetlen minim´ alis elem. Hasonl´ o ´erv´enyes a legnagyobb elemre is.
Elemi ´ all´ıt´ asok a pr´ımsz´ amok eloszl´ as´ ar´ ol 6.1. T´ etel. V´egtelen sok pr´ımsz´ am van. 6.2. T´ etel. V´egtelen sok 4k − 1 alak´ u pr´ımsz´ am van. 6.4. T´ etel∗ (Dirichlet t´ etele). Ha egy nemkonstans sz´ amtani sorozat kezd˝ otagja ´es differenci´ aja egym´ ashoz relat´ıv pr´ım, akkor a sz´ amtani sorozatban v´egtelen sok pr´ımsz´ am tal´ alhat´ o. 6.5. T´ etel∗ (Csebisev t´ etele). B´ armely sz´ am ´es a k´etszerese k¨ oz¨ ott van pr´ımsz´ am. Pontosabban: minden n term´eszetes sz´ amhoz l´etezik olyan p pr´ımsz´ am, amelyre n < p ≤ 2n.
Legnagyobb k¨ oz¨ os oszt´ o
6.6. T´ etel. A szomsz´ ados pr´ımek k¨ oz¨ ott tetsz˝ olegesen nagy h´ezagok tal´ alhat´ ok. (Azaz minden N ∈ N eset´en lehet tal´ alni N egym´ ast k¨ ovet˝ o¨ osszetett sz´ amot.)
oz¨ os oszt´ o j´ anak nevezz¨ uk, ha kiel´eg´ıti a 1.12. Defin´ıci´ o. A d eg´esz sz´ amot az a ´es b eg´esz sz´ amok legnagyobb k¨ k¨ ovetkez˝ o k´et felt´etelt: (1) d | a ´es d | b; (2) ∀k ∈ Z : (k | a ´es k | b) =⇒ k | d. A t eg´esz sz´ am legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ose a-nak ´es b-nek, ha kiel´eg´ıti a k¨ovetkez˝ o k´et felt´etelt: (1) a | t ´es b | t; (2) ∀k ∈ Z : (a | k ´es b | k) =⇒ t | k.
unk k´et pr´ımsz´amot, ha k¨ ul¨onbs´eg¨ uk 2. 6.7. Defin´ıci´ o. Ikerpr´ımnek nevez¨
Jel¨ ol´ es. Az a ´es b sz´ amok legnagyobb k¨oz¨os oszt´oj´ at lnko (a, b) vagy (a, b), legkisebb k¨oz¨os t¨obbsz¨or¨os¨ uket pedig lkkt (a, b) vagy [a, b] jel¨oli.
6.9. Lemma∗ . A
1.13. Megjegyz´ es. A legnagyobb k¨oz¨os oszt´o nem egy´ertelm˝ u: az 1.2. T´etel (3) a´ll´ıt´asa szerint ha d legnagyobb k¨oz¨os ´ oszt´oja a-nak ´es b-nek, akkor −d is az (de e k´et sz´ amon k´ıv¨ ul nincs m´as legnagyobb k¨oz¨os oszt´o). Altal´ aban a k´et ´ert´ek k¨ oz¨ ul a nemnegat´ıvat szoktuk tekinteni. 1.14. Megjegyz´ es. Jel¨olje Da az a term´eszetes sz´ am pozit´ıv oszt´oinak halmaz´ at: Da = {c ∈ N : c | a}. Az 1.12. Defin´ıci´ o szerint lnko (a, b) nem m´as, mint a (Da ∩ Db ; |) r´eszbenrendezett halmaz legnagyobb eleme. Az oszthat´ os´ agi rel´ aci´ o nem dichot´ om, ´ıgy nem vil´agos, hogy l´etezik-e egy´altal´an legnagyobb eleme ennek a r´eszbenrendezett halmaznak. Term´eszetesebbnek t˝ unhetne a legnagyobb k¨ oz¨os oszt´ot a (Da ∩ Db ; ≤) r´eszbenrendezett halmaz legnagyobb elemek´ent defini´alni (err˝ol legal´abb vil´agos, hogy l´etezik). Tegy¨ uk fel, hogy d = lnko (a, b) az 1.12. Defin´ıci´ o ´ertelm´eben. Ha k ∈ Da ∩ Db , akkor k | d ´es ´ıgy az 1.2. T´etel utols´o all´ıt´asa szerint k ≤ d. Teh´ ´ at d legnagyobb eleme a (Da ∩ Db ; ≤) r´eszbenrendezett halmaznak is. L´ atjuk teh´ at, hogy a legnagyobb k¨oz¨os oszt´o k´etf´ele lehets´eges defin´ıci´ oja egybeesik, amennyiben l´etezik b´armely k´et sz´ amnak legnagyobb k¨ oz¨ os oszt´oja az 1.12. Defin´ıci´ o szerint. Az euklideszi algoritmus seg´ıts´eg´evel be fogjuk bizony´ıtani, hogy a legnagyobb k¨ oz¨ os oszt´o val´ oban mindig l´etezik.
n−1
6.8. T´ etel. Az n-edik pr´ımsz´ am nem nagyobb, mint 22
.
Analitikus eredm´ enyek a pr´ımsz´ amok eloszl´ as´ ar´ ol, a pr´ımsz´ amt´ etel
∗
P∞
1 n=1 n
harmonikus sor divergens, m´ıg a
P∞
1 n=1 n2
sor konvergens.
6.10. Lemma . Minden nemnegat´ıv val´ os x-re teljes¨ ul a log (1 + x) ≤ x egyenl˝ otens´eg. 6.11. T´ etel. A pr´ımsz´ amok reciprokaib´ ol alkotott sor divergens, azaz X1 = ∞. p p 6.12. Megjegyz´ es. Ez a t´etel durv´ an fogalmazva azt ´all´ıtja, hogy sok” pr´ımsz´am van (n´egyzetsz´ amb´ol viszont a 6.9. Lem” ma szerint kev´es” van). Ismert t´eny, hogy kev´es” p´aratlan t¨ok´eletes sz´ am, illetve kev´es” ikerpr´ım van (ebb˝ol persze m´eg ” ” ” nem der¨ ul ki, hogy v´egtelen sok van-e bel˝ol¨ uk). 6.13. Megjegyz´ es. A harmonikus sor lassan diverg´al, a pr´ımsz´amok reciprokaib´ ol alkotott sor m´eg lassabban. P´eld´ aul P 1 o o¨tvenmilli´ o tagja). p<1018 p < 4 (ez kb. a sor els˝
6.14. Defin´ıci´ o. A pr´ımsz´amok eloszl´ as´ anak pontosabb vizsg´alat´an´ al hasznos a π (x) f¨ uggv´eny, az u ´ gynevezett pr´ımos sz´ amn´al nem nagyobb pr´ımek sz´ am´ at: sz´ aml´ al´ o f¨ uggv´ eny , amely megadja az x pozit´ıv val´ X π (x) = 1. p≤x
Marad´ ekos oszt´ as, euklideszi algoritmus, line´ aris diofantoszi egyenletek
∗
6.15. T´ etel (pr´ımsz´ amt´ etel). A π (x) pr´ımsz´ aml´ al´ o f¨ uggv´eny aszimptotikusan ekvivalens az lim
1.15. T´ etel (a marad´ ekos oszt´ as t´ etele). Ha a, b ∈ Z, ´es b 6= 0, akkor l´eteznek olyan egy´ertelm˝ uen meghat´ arozott q ´es r eg´esz sz´ amok, amelyekre a = bq + r ´es 0 ≤ r < |b|. 1.16. Defin´ıci´ o. Adott a ´es b eg´esz sz´ amok eset´en az el˝oz˝ o t´etelbeli q ´es r kisz´ am´ıt´as´ at marad´ ekos oszt´ asnak nevezz¨ uk. Az a sz´ am az osztand´ o , b az oszt´ o , q a h´ anyados, ´es r a marad´ ek . 1.17. Lemma. Tetsz˝ oleges a, b, k ∈ Z eset´en a ´es b k¨ oz¨ os oszt´ oi ugyanazok, mint a − kb ´es b k¨ oz¨ os oszt´ oi. 1.18. T´ etel (euklideszi algoritmus). B´ armely k´et term´eszetes sz´ amnak van legnagyobb k¨ oz¨ os oszt´ oja, ´es az az euklideszi algoritmussal megkaphat´ o. Az a = r0 , b = r1 term´eszetes sz´ amokon v´egrehajtott euklideszi algoritmus marad´ekos oszt´ asok ism´etelt elv´egz´es´et jelenti: r0 = q1 r1 + r2 r1 = q2 r2 + r3 r2 = q3 r3 + r4 .. . ri−1 = qi ri + ri+1 .. .
(0 ≤ r2 < r1 ) ; (0 ≤ r3 < r2 ) ; (0 ≤ r4 < r3 ) ; (0 ≤ ri+1 < ri ) ;
x→∞ ∗
π (x) x log x
x log x
f¨ uggv´ennyel, azaz
= 1.
6.16. K¨ ovetkezm´ eny . Az n-edik pr´ımsz´ am aszimptotikusan n log n, azaz limn→∞ jel¨ oli).
pn n log n
= 1 (pn az n-edik pr´ımsz´ amot
5. Sz´ amok felbont´ asa hatv´ anyok ¨ osszeg´ ere
Az elj´ ar´ as v´eges sz´ am´ u l´ep´es ut´ an v´eget ´er: l´etezik olyan n ∈ N, hogy rn+1 = 0. A legnagyobb k¨ oz¨ os oszt´ o az utols´ o nemnulla marad´ek, azaz lnko (a, b) = rn . A legnagyobb k¨ oz¨ os oszt´ o kifejezhet˝ o a k´et sz´ am line´ aris kombin´ aci´ ojak´ent”: ” l´eteznek olyan x, y eg´esz sz´ amok, melyekre ax + by = lnko (a, b).
Pitagoraszi sz´ amh´ armasok, a nagy Fermat-t´ etel 1.19. Defin´ıci´ o. Azt mondjuk, hogy az a, b eg´esz sz´ amok relat´ıv pr´ımek, ha lnko (a, b) = 1. 3
2
2
2
5.1. Defin´ıci´ o. Az (x, y, z) ∈ N sz´ amh´armast pitagoraszi sz´ amh´ armasnak nevezz¨ uk, ha x + y = z . Az (x, y, z) pitagoraszi sz´ amh´armas primit´ıv , ha lnko (x, y, z) = 1. 5.2. Megjegyz´ es. Tetsz˝oleges (x, y, z) pitagoraszi sz´ amh´armas eset´en (x/d, y/d, z/d) primit´ıv pitagoraszi sz´ amh´armas, ahol d = lnko (x, y, z). Teh´ at elegend˝ o a primit´ıv pitagoraszi sz´ amh´armasokat meghat´ arozni, mert ezekb˝ ol minden pitagoraszi sz´ amh´armas megkaphat´o (egy konstanssal val´ o szorz´ assal). 5.3. Lemma. Primit´ıv pitagoraszi sz´ amh´ armasban a tagok p´ aronk´ent is relat´ıv pr´ımek. Ford´ıtva, ha egy pitagoraszi sz´ amh´ armasban valamelyik k´et tag relat´ıv pr´ım, akkor a sz´ amh´ armas primit´ıv. 5.4. Lemma. Ha (x, y, z) primit´ıv pitagoraszi sz´ amh´ armas, akkor x ´es y parit´ asa k¨ ul¨ onb¨ oz˝ o, z pedig p´ aratlan. 5.5. T´ etel. Legyen (x, y, z) primit´ıv pitagoraszi sz´ amh´ armas, ´es tegy¨ uk fel, hogy x p´ aros. Ekkor l´eteznek olyan u, v term´eszetes sz´ amok, melyekre u > v, u 6≡ v (mod 2) , lnko (u, v) = 1, ´es x = 2uv, y = u2 − v 2 , z = u2 + v 2 .
(△)
Ford´ıtva, a (△) formul´ akkal defini´ alt (x, y, z) sz´ amh´ armas mindig primit´ıv pitagoraszi sz´ amh´ armas. 5.6. T´ etel. Az x4 + y 4 = z 2 egyenletnek nincs pozit´ıv eg´eszekb˝ ol a ´ll´ o megold´ asa. 5.7. K¨ ovetkezm´ eny. Az x4 + y 4 = z 4 egyenletnek nincs pozit´ıv eg´eszekb˝ ol a ´ll´ o megold´ asa.
1.20. T´ etel. Tetsz˝ oleges a, b nemnulla eg´esz sz´ amok eset´en
a lnko(a,b)
´es
b lnko(a,b)
relat´ıv pr´ım.
1.21. T´ etel. Tetsz˝ oleges a, b, c ∈ Z eset´en ha a ´es b relat´ıv pr´ım, akkor a | bc ⇐⇒ a | c. 1.22. T´ etel (Euklidesz lemm´ aja). Tetsz˝ oleges a, b, c eg´esz sz´ amok eset´en ha lnko (a, b) 6= 0, akkor a | bc ⇐⇒
a lnko(a,b)
| c.
1.23. T´ etel. Tetsz˝ oleges adott a, b, c nemnulla eg´esz sz´ amok eset´en az ax + by = c k´ etismeretlenes line´ aris diofantoszi egyenlet akkor ´es csak akkor oldhat´ o meg, ha lnko (a, b) | c. Ha (x0 , y0 ) egy megold´ as, akkor b´ armely t ∈ Z eset´en az al´ abbi (x, y) p´ ar is megold´ as, tov´ abb´ a minden megold´ as el˝ oa ´ll ilyen alakban a t sz´ am alkalmas megv´ alaszt´ as´ aval: b · t; x = x0 + lnko (a, b) a · t. y = y0 − lnko (a, b)
Pr´ımsz´ am, felbonthatatlan sz´ am, a sz´ amelm´ elet alapt´ etele 1.24. Defin´ıci´ o. A p ≥ 2 term´eszetes sz´ amot felbonthatatlan sz´ amnak nevezz¨ uk, ha csak u ´ gy bonthat´o k´et term´ealis szetes sz´ am szorzat´ara, hogy az egyik t´enyez˝ o maga p. (Ekkor a m´asik t´enyez˝ o sz¨ uks´egk´eppen 1; ilyenkor trivi´ faktoriz´ aci´ o r´ol besz´el¨ unk.) Form´alisan: ∀a, b ∈ N : p = ab =⇒ (p = a vagy p = b) .
5.8. T´ etel∗ (nagy Fermat-t´ etel). Ha n ≥ 3, akkor az xn + y n = z n egyenletnek nincs pozit´ıv eg´eszekb˝ ol a ´ll´ o megold´ asa. 1.25. Defin´ıci´ o. A p ≥ 2 term´eszetes sz´ amot pr´ımsz´ amnak nevezz¨ uk, ha valah´anyszor oszt´oja egy szorzatnak, mindannyiszor oszt´oja a szorzat egyik t´enyez˝ oj´enek. Form´alisan: ∀a, b ∈ N : p | ab =⇒ (p | a vagy p | b) .
N´ egyzetsz´ amok ¨ osszegei
1.26. T´ etel. A pr´ımsz´ amok ´es a felbonthatatlan sz´ amok ugyanazok. 5.9. Lemma. Ha a ´es b el˝ oa ´ll k´et n´egyzetsz´ am ¨ osszegek´ent, akkor ab is el˝ oa ´ll.
1.27. Lemma. Legyen p pr´ımsz´ am, n ∈ N ´es a1 , . . . , an ∈ N. Ha p | a1 · . . . · an , akkor p | ai valamely i ∈ {1, . . . , n}-re.
5.10. Lemma. A 4k + 1 alak´ u pr´ımsz´ amok el˝ oa ´llnak k´et n´egyzetsz´ am ¨ osszegek´ent.
1.28. T´ etel (a sz´ amelm´ elet alapt´ etele). B´ armely term´eszetes sz´ am felbonthat´ o pr´ımsz´ amok szorzat´ ara, ´es ez a felbont´ as a t´enyez˝ ok sorrendj´et˝ ol eltekintve egy´ertelm˝ u.
5.11. Lemma. Tegy¨ uk fel, hogy n el˝ oa ´ll k´et relat´ıv pr´ım n´egyzetsz´ am ¨ osszegek´ent. Ekkor n egyetlen pr´ımoszt´ oja sem lehet 4k + 3 alak´ u. 5.12. T´ etel (Fermat-f´ ele k´ et n´ egyzetsz´ am t´ etel). Pontosan azok a sz´ amok a ´llnak el˝ o k´et n´egyzetsz´ am ¨ osszegek´ent, amelyek pr´ımfelbont´ as´ aban a 4k + 3 alak´ u pr´ımek p´ aros kitev˝ ovel szerepelnek. 5.13. T´ etel∗ (Lagrange-f´ ele n´ egy n´ egyzetsz´ am t´ etel). Minden term´eszetes sz´ am el˝ oa ´ll n´egy n´egyzetsz´ am o ¨sszegek´ent.
αn 1 es b = pβ1 1 · . . . · pβnn (azokat 1.29. K¨ ovetkezm´ eny. Legyen az a ´es b term´eszetes sz´ amok pr´ımfelbont´ asa a = pα 1 · . . . · pn ´ a pr´ımeket, amelyek csak az egyik sz´ amban fordulnak el˝ o, a m´ asikban nulla kitev˝ ovel t¨ untetj¨ uk fel ). Ekkor teljes¨ ulnek az al´ abbiak: (1) a | b ⇐⇒ αi ≤ βi (i = 1, . . . , n) ; min(α1 ,β1 ) min(αn ,βn ) ; (2) lnko (a, b) = p1 · . . . · pn max(α1 ,β1 ) max(αn ,βn ) (3) lkkt (a, b) = p1 · . . . · pn .
5.14. Megjegyz´ es. Lagrange t´etele ´eles abban az ´ertelemben, hogy h´arom n´egyzetsz´ am ¨osszegek´ent nem lehet minden term´eszetes sz´ amot el˝o´all´ıtani (keress¨ unk ellenp´eld´ at!). A term´eszetes sz´ amok hatv´ any¨osszegekk´ent val´ o el˝o´all´ıt´asaival kapcsolatos probl´em´ akat ¨osszefoglal´ o n´even Waring-probl´emak¨ornek szok´ as nevezni. Edward Waring XVIII. sz´ azadi angol matematikus Meditationes Algebraicae c´ım˝ u m˝ uv´eben azt ´all´ıtotta (bizony´ıt´as n´elk¨ ul), hogy minden sz´ am el˝o´all´ıthat´o kilenc k¨ obsz´am ¨osszegek´ent, illetve tizenkilenc negyedik hatv´ any ¨osszegek´ent. Ezek az a´ll´ıt´asok helyesnek bizonyultak, ´ de csak a huszadik sz´ azadban tal´ altak r´ajuk bizony´ıt´ast. Altal´ aban g (k) jel¨oli azt a legkisebb sz´ amot, amelyre igaz az, hogy minden term´eszetes sz´ am el˝o´all´ıthat´o g (k) darab k-adik hatv´ any ¨osszegek´ent. Az el˝oz˝ oek alapj´ an teh´ at g (2) = 4, g (3) ≤ 9, g (4) ≤ 19, ´es p´eld´ ak mutatj´ ak, hogy 8 k¨ob, illetve 18 negyedik hatv´ any nem mindig el´eg, teh´ at g (3) = 9 ´es g (4) = 19. A g (k) sz´ amok meghat´ aroz´asa igen neh´ez probl´ema, m´eg az sem vil´agos, hogy egy´altal´an l´eteznek§ minden k-ra, b´ar ezt m´ar Waring is sejtette. Hilbert igazolta Waring sejt´es´et, ´es van egy felt´etelezett k´eplet is a g (k) sz´ amokra: k 3 g (k) = 2k + k − 2. 2
2.1. Defin´ıci´ o. Legyen m ≥ 2, a, b ∈ Z. Ha a − b oszthat´o m-mel, akkor azt mondjuk, hogy a kongruens b-vel amot a kongruencia modulus´anak nevezz¨ uk. modulo m. Az m sz´
Bizony´ıtott t´eny, hogy ez a k´eplet legfeljebb v´eges sok k-ra nem helyes, ´es a´ltal´anosan elfogadott az a sejt´es, hogy val´ oj´ aban minden k-ra ´erv´enyes.
Jel¨ ol´ es. A kongruenci´ at ≡ jel¨oli, a modulust ut´ana z´ar´ ojelben t¨ untetj¨ uk fel a mod r¨ovid´ıt´est haszn´ alva (de ezt id˝onk´ent elhagyjuk). Teh´ at a ≡ b (mod m) ⇐⇒ m | a − b.
§
Mit jelentene az, hogy g (k) nem l´ etezik?
1.30. K¨ ovetkezm´ eny. B´ armely k´et a, b term´eszetes sz´ amnak l´etezik legkisebb k¨ oz¨ os t¨ obbsz¨ or¨ ose, ´es lnko (a, b) · lkkt (a, b) = ab.
2. Sz´ amelm´ eleti kongruenci´ ak Kongruenciarel´ aci´ o, marad´ ekoszt´ alyok
2.2. T´ etel. Tetsz˝ oleges m ≥ 2, a, b ∈ Z eset´en a ≡ b (mod m) akkor ´es csak akkor teljes¨ ul, ha a ´es b ugyanazt a marad´ekot adja m-mel osztva.
2.3. T´ etel. Tetsz˝ oleges m, m1 , m2 ≥ 2, a, b, c, a1, b1 , a2 , b2 ∈ Z eset´en ´erv´enyesek az al´ abbiak: (1) a ≡ a (mod m) ; (2) a ≡ b (mod m) =⇒ b ≡ a (mod m) ; (3) (a ≡ b (mod m) ´es b ≡ c (mod m)) =⇒ a ≡ c (mod m) ; a ≡ b1 (mod m) =⇒ a1 ± a2 ≡ b1 ± b2 (mod m) , a1 · a2 ≡ b1 · b2 (mod m) ; (4) 1 a2 ≡ b2 (mod m) m ; (5) ha c 6= 0, akkor ca ≡ cb (mod m) ⇐⇒ a ≡ b mod lnko(m,c) (6) ha lnko (m, c) = 1, akkor ca ≡ cb (mod m) ⇐⇒ a ≡ b (mod m) ; a ≡ b (mod m1 ) ⇐⇒ a ≡ b (mod [m1 , m2 ]) ; a ≡ b (mod m2 )
(7)
4.16. T´ etel. Legyen g primit´ıv gy¨ ok modulo m, legyen k tetsz˝ oleges eg´esz sz´ am, a ´es b pedig relat´ıv pr´ımek m-hez. Ekkor ´erv´enyesek az al´ abbi azonoss´ agok: (1) (2) (3) (4)
indg 1 ≡ 0 (mod ϕ (m)) ; indg (ab) ≡ indg a + indg b (mod ϕ (m)) ; indg ak ≡ k · indg a (mod ϕ (m)) ; indg ab−1 ≡ indg a − indg b (mod ϕ (m)) .
anymarad´ ek modulo m, ha az xn ≡ a (mod m) 4.17. Defin´ıci´ o. Azt mondjuk, hogy az a eg´esz sz´ am n-edik hatv´ kongruenci´ anak van megold´ asa. 4.18. T´ etel. Legyen g primit´ıv gy¨ ok modulo m, ´es legyen a relat´ıv pr´ım m-hez. Ekkor a pontosan akkor n-edik hatv´ anymarad´ek modulo m, ha (n, ϕ (m)) | indg a.
(8) ha a ≡ b (mod m), akkor lnko (a, m) = lnko (b, m) . ekoszt´ aly a´n az a = {b ∈ Z : a ≡ b (mod m)} halmazt ´ertj¨ uk. 2.4. Defin´ıci´ o. Egy a eg´esz sz´ am modulo m marad´ Jel¨ ol´ es. A modulo m marad´ekoszt´alyok halmaz´ at Zm jel¨oli. Teh´ at Zm = {a : a ∈ Z} = 0, 1, . . . , m − 1 .
2.5. Defin´ıci´ o. A modulo m marad´ekoszt´alyok halmaz´ an ´ertelmezz¨ uk az els˝ o h´arom alapm˝ uveletet a k¨ovetkez˝ ok´eppen: tetsz˝oleges a, b ∈ Z eset´en legyen a + b = a + b, a − b = a − b, a · b = a · b.
2.6. T´ etel. A fenti m˝ uveletek j´ oldefini´ altak, azaz marad´ekoszt´ alyok ¨ osszege (k¨ ul¨ onbs´ege, szorzata) nem f¨ ugg att´ ol, hogy az egyes marad´ekoszt´ alyokb´ ol melyik sz´ amot v´ alasztjuk reprezent´ ansnak. 2.7. Megjegyz´ es. A 2.3. T´etelbeli utols´o ´all´ıt´as szerint van ´ertelme egy mod m marad´ekoszt´aly ´es az m modulus legnagyobb k¨ oz¨ os oszt´oj´ ar´ ol besz´elni (hiszen nem f¨ ugg a reprezent´ans v´ alaszt´ as´ at´ ol). K´es˝ obb fontos szerepet j´ atszanak majd azok a marad´ekoszt´alyok, amelyek relat´ıv pr´ımek a modulushoz, ez´ert erre k¨ ul¨on elnevez´est ´es jel¨ol´est vezet¨ unk be. 2.8. Defin´ıci´ o. Az a ∈ Zm marad´ekoszt´alyt reduk´ alt marad´ ekoszt´ aly nak h´ıvjuk, ha lnko (a, m) = 1. Jel¨ ol´ es. A mod m reduk´alt marad´ekoszt´alyok halmaz´ at Z∗m jel¨oli. Teh´ at Z∗m = {a ∈ Zm : lnko (a, m) = 1} .
Ekvivalenci´ ak ´ es oszt´ alyoz´ asok 2.9. Defin´ıci´ o. Ekvivalenciarel´ aci´ o nak nevezz¨ uk a ρ ⊆ A × A rel´ aci´ ot, ha rendelkezik az al´ abbi h´arom tulajdons´ aggal: (1) ∀a ∈ A : aρa (reflexivit´as); (2) ∀a, b ∈ A : aρb =⇒ bρa (szimmetria); (3) ∀a, b, c ∈ A : (aρb ´es bρc) =⇒ aρc (tranzitivit´as). P´ elda. Tetsz˝oleges f : A → B lek´epez´es eset´en a ker f := {(a1 , a2 ) : f (a1 ) = f (a2 )} ⊆ A × A rel´ aci´ o ekvivalenciarel´ aci´ o az A halmazon, amelynek neve az f lek´epez´es mag ja. 2.10. Defin´ıci´ o. Legyen ρ ⊆ A× A egy ekvivalenciarel´ aci´ o ´es a tetsz˝oleges eleme A-nak. Ekkor a {b ∈ A : aρb} halmazt az aly ´anak (vagy blokkj´anak), az ekvivalenciaoszt´alyok halmaz´ at pedig az A halmaz a elem ρ szerinti (ekvivalencia)oszt´ ρ szerinti faktorhalmaz ´anak nevezz¨ uk. Jel¨ ol´ es. Az a elem ρ szerinti oszt´aly´at szok´ as a/ρ-val, aρ -val vagy [a]ρ -val jel¨olni, de mi ink´abb az egyszer˝ ubb a jel¨ol´est haszn´ aljuk. Ez ugyan nem utal ρ-ra, de ´altal´aban kider¨ ul a sz¨ovegk¨ornyezetb˝ol, hogy mi a sz´ oban forg´ o ekvivalenciarel´ aci´ o. A faktorhalmazt A/ρ jel¨oli, teh´ at A/ρ = {a : a ∈ A}.
N´ egyzetes marad´ ekok, Legendre-szimb´ olum egyzetes marad´ ek nak nevezz¨ uk modulo m, ha az x2 ≡ a (mod m) kongruenci´ anak 4.19. Defin´ıci´ o. Az a eg´esz sz´ amot n´ van megold´ asa. Ellenkez˝ o esetben azt mondjuk, hogy a n´ egyzetes nemmarad´ ek modulo m. (Nem el´ır´ as, val´ oban u ´ gy mondjuk, hogy a n´egyzetes nemmarad´ek, nem pedig u ´ gy, hogy a nem n´egyzetes marad´ek.) 4.20. T´ etel. Legyen p p´ aratlan pr´ımsz´ am, g primit´ıv gy¨ ok modulo p. Ekkor a ∈ Z pontosan akkor n´egyzetes marad´ek modulo p, ha p | a vagy indg a p´ aros. 4.21. Defin´ıci´ o. Tetsz˝oleges p p´aratlan pr´ımsz´am ´es p-vel nem oszthat´o a eg´esz sz´ am eset´en ´ertelmezz¨ uk az ap Legendreszimb´ olumot a k¨ovetkez˝ ok´eppen: a 1, ha a n´egyzetes marad´ek mod p; = −1, ha a n´egyzetes nemmarad´ek mod p. p 4.22. T´ etel (Euler-krit´ erium). Ha p p´ aratlan pr´ımsz´ am ´es p ∤ a, akkor p−1 a ≡ a 2 (mod p) . p 4.23. T´ etel. Tetsz˝ oleges p p´ aratlan pr´ımsz´ am ´es p-vel nem oszthat´ o a, b eg´esz sz´ amok eset´en teljes¨ ulnek az al´ abbiak: (1) a ≡ b (mod p) =⇒ ap = pb ; a b (2) ab p = p p ; 2 (3) ap = 1.
4.24. T´ etel. Tetsz˝ oleges p p´ aratlan pr´ımsz´ am eset´en p−1 −1 1, ha p ≡ 1 (mod 4) ; = (−1) 2 = −1, ha p ≡ 3 (mod 4) . p
4.25. T´ etel (Gauss-lemma). Legyen p p´ aratlan pr´ımsz´ am, a pedig p-vel nem oszthat´ o sz´ am. Jel¨ olje n az a, 2a, . . . , p−1 2 a sz´ amok k¨ oz¨ ul azoknak a sz´ am´ at, amelyek p-vel adott oszt´ asi marad´eka nagyobb, mint p2 . Ekkor az ap Legendre-szimb´ olum ´ert´eke (−1)n . 4.26. T´ etel. Az el˝ oz˝ o t´etel jel¨ ol´eseit haszn´ alva p´ aratlan a eset´en p−1
n≡
2 X ai
(mod 2) .
2.11. Defin´ıci´ o. Egy nem¨ ures halmaz oszt´ alyoz´ as´an olyan p´aronk´ent diszjunkt nem¨ ures r´eszhalmazainak halmaz´ at ´ertj¨ uk, amelyek egy¨ utt lefedik az alaphalmazt. Form´alisan: C ⊆ P (A) oszt´alyoz´ as a nem¨ ures A halmazon, ha (1) ∀B ∈ C : B 6= ∅; (2) ∀B S 1 6= B2 ∈ C : B1 ∩ B2 = ∅; (3) B = A.
4.27. T´ etel (n´ egyzetes reciprocit´ asi t´ etel). Tetsz˝ oleges p, q k¨ ul¨ onb¨ oz˝ o p´ aratlan pr´ımsz´ amok eset´en p−1 q−1 p q 2 2 . = (−1) q p
2.12. T´ etel. Legyen A egy nem¨ ures halmaz. Ha ρ ⊆ A × A ekvivalenciarel´ aci´ o, akkor A/ρ oszt´ alyoz´ as az A halmazon. Ha pedig C ⊆ P (A) oszt´ alyoz´ as, akkor az aρb ⇐⇒ ∃B ∈ C : a, b ∈ B formul´ aval defini´ alt ρ rel´ aci´ o ekvivalenciarel´ aci´ o az A halmazon. A most megadott ekvivalenciarel´ aci´ o 7→ oszt´alyoz´ as” ´es oszt´alyoz´ as 7→ ekvivalenciarel´ aci´ o” megfeleltet´esek ” ” egym´ as inverzei.
4.28. T´ etel. Tetsz˝ oleges p p´ aratlan pr´ımsz´ amra p2 −1 2 1, ha p ≡ 1, 7 (mod 8) ; = (−1) 8 = −1, ha p ≡ 3, 5 (mod 8) . p
B∈C
i=1
p
4. Hatv´ anyoz´ as modulo m
Line´ aris kongruenci´ ak ´ es kongruenciarendszerek
Rend, primit´ıv gy¨ ok, index
2.13. Defin´ıci´ o. Line´ aris kongruenci´ a nak nevezz¨ uk az ax ≡ b (mod m) alak´ u egyenletet”, ahol a, b, m adott eg´esz ” sz´ amok, ´es az x ismeretlent is az eg´esz sz´ amok k¨or´eben keress¨ uk.
4.1. Defin´ıci´ o. Azt mondjuk, hogy k j´ o kitev˝ o az a eg´esz sz´ amhoz az m modulusra n´ezve, ha ak ≡ 1 (mod m). 4.2. Defin´ıci´ o. A legkisebb pozit´ıv j´ o kitev˝ot, ami az a eg´esz sz´ amhoz tartozik az m modulusra n´ezve, az a sz´ am modulo m rend j´enek nevezz¨ uk (amennyiben l´etezik egy´altal´an pozit´ıv j´ o kitev˝o).
2.14. T´ etel. Az ax ≡ b (mod m) line´ aris kongruencia akkor ´es csak akkor oldhat´ o meg, ha lnko (a, m) | b. Ha ez teljes¨ ul, m marad´ekoszt´ alyt alkotnak, modulo m pedig lnko (a, m) a megold´ asok sz´ ama. akkor a megold´ asok egyetlen modulo lnko(a,m) Ha x0 egy megold´ as, akkor az ¨ osszes megold´ as: x ≡ x0 + t ·
Jel¨ ol´ es. Az a eg´esz sz´ am mod m rendj´et om (a) jel¨oli. Teh´ at om (a) = min k > 0 : ak ≡ 1 (mod m) .
4.3. Megjegyz´ es. Vil´agos, hogy lnko (a, m) > 1 eset´en nincs j´ o kitev˝o, teh´ at ilyenkor om (a) nem ´ertelmezett. Ha viszont a ´es m relat´ıv pr´ımek, akkor az Euler–Fermat-t´etel szerint ϕ (m) j´ o kitev˝o, teh´ at ekkor om (a) ≤ ϕ (m).
4.4. T´ etel. A j´ o kitev˝ ok ´eppen a rend t¨ obbsz¨ or¨ osei. Prec´ızebben: ha a ´es m relat´ıv pr´ımek, k pedig tetsz˝ oleges eg´esz sz´ am, akkor ak ≡ 1 (mod m) ⇐⇒ om (a) | k. K¨ ovetkez´esk´epp om (a) | ϕ (m). 4.5. K¨ ovetkezm´ eny. A kitev˝ ok modulo om (a) sz´ am´ıtanak. Prec´ızebben: ha a ´es m relat´ıv pr´ımek, k1 , k2 pedig tetsz˝ oleges eg´esz sz´ amok, akkor a
k1
≡a
k2
(mod m) ⇐⇒ k1 ≡ k2 (mod om (a)) .
4.6. K¨ ovetkezm´ eny. Ha a ´es m relat´ıv pr´ımek, akkor a hatv´ anyai om (a)-f´ele k¨ ul¨ onb¨ oz˝ o marad´ekot adnak modulo m, ´es ezeket mind megkapjuk, ha a kitev˝ ot egy mod om (a) teljes marad´ekrendszeren futtatjuk v´egig (p´eld´ aul 1-t˝ ol om (a)-ig). Form´ alisan: n o o n o n k a : k ∈ Z = om (a) ´es ak : k ∈ Z = a, a2 , . . . , aom (a) ⊆ Zm . ok modulo m, ha rendje ´eppen ϕ (m). 4.7. Defin´ıci´ o. Azt mondjuk, hogy a g eg´esz sz´ am primit´ıv gy¨
4.8. T´ etel. A g eg´esz sz´ am akkor ´es csak akkor primit´ıv gy¨ ok modulo m, ha az ¨ osszes mod m reduk´ alt marad´ekoszt´ aly anyak´ent. megkaphat´ o g hatv´ 4.9. Lemma∗ . Ha p pr´ımsz´ am, akkor az xd ≡ 1 (mod p) kongruenci´ anak legf¨ oljebb d megold´ asa lehet modulo p. 4.10. Megjegyz´ es. Meglep˝o lehet, hogy az ´all´ıt´as nem igaz, ha a modulus nem pr´ım (keress¨ unk ellenp´eld´ at!).
m (mod m) lnko (a, m)
2.15. Defin´ıci´ o. Azt mondjuk, hogy az a, b eg´esz sz´ amok egym´ as multiplikat´ıv inverz ei modulo m, ha ab ≡ 1 (mod m). Hasonl´oan a, b ∈ Zm egym´ as multiplikat´ıv inverzei, ha a · b = 1. Jel¨ ol´ es. Ha nem fenyeget a f´elre´ert´es vesz´elye, akkor az a eg´esz sz´ am mod m multiplikat´ıv inverz´et a−1 -gyel jel¨olj¨ uk. Hasonl´oan a ∈ Zm multiplikat´ıv inverz´et a−1 jel¨oli. 2.16. T´ etel. Az a eg´esz sz´ amnak akkor ´es csak akkor van multiplikat´ıv inverze modulo m, ha lnko (a, m) = 1. Ilyenkor a multiplikat´ıv inverz mod m egy´ertelm˝ uen meghat´ arozott. Hasonl´ oan, a ∈ Zm akkor ´es csak akkor rendelkezik multiplikat´ıv inverzzel, ha a ∈ Z∗m . Ilyenkor a multiplikat´ıv inverz egy´ertelm˝ uen meghat´ arozott. 2.17. Defin´ıci´ o. Ha a ´es m relat´ıv pr´ımek, akkor tetsz˝oleges k ∈ N eset´en ´ertelmezz¨ uk az a−k negat´ıv kitev˝oj˝ u hatv´ anyt −1 −1 −k (mod m). Hasonl´ok´eppen a ∈ Z∗m eset´en legyen (a) = ak modulo m: legyen a−k ≡ ak . 2.18. Megjegyz´ es. Meg lehet mutatni, hogy a hatv´ anyoz´ as szok´ asos azonoss´agai ´erv´enyben maradnak az eg´esz kitev˝os mod m hatv´ anyok fenti ´ertelmez´ese mellett.
2.19. Defin´ıci´ o. Adott ai , bi , ni (i = 1, 2, . . . , k) eg´esz sz´ amok eset´en az al´ abbi egyenletrendszert” line´ aris kongruen” uk (az x ismeretlent is term´eszetesen az eg´esz sz´ amok k¨or´eben keress¨ uk): ciarendszer nek nevezz¨ a1 x ≡ b1 (mod n1 ) a2 x ≡ b2 (mod n2 ) .. . ak x ≡ bk (mod nk ) 2.20. Megjegyz´ es. A 2.14. T´etel seg´ıts´eg´evel a kongruenciarendszerbeli kongruenci´ akat k¨ ul¨on-k¨ ul¨on megoldhatjuk (ha van megold´ asuk), ´es ´ıgy a kongruenciarendszert a k¨ovetkez˝ o alakra hozhatjuk: x ≡ c1 (mod m1 ) x ≡ c2 (mod m2 ) .. . x ≡ ck (mod mk )
4.11. T´ etel. Ha p pr´ımsz´ am ´es d | p − 1, akkor a d-edrend˝ u eg´eszek sz´ ama modulo p ´eppen ϕ (d). Speci´ alisan ϕ (p − 1) modulo p inkongruens primit´ıv gy¨ ok van. 4.12. T´ etel∗ . A k¨ ovetkez˝ o modulusokhoz l´etezik primit´ıv gy¨ ok (´es csak ezekhez ): 2, 4, p´ aratlan pr´ımhatv´ anyok, p´ aratlan pr´ımhatv´ anyok k´etszeresei. Ezekben az esetekben a mod m primit´ıv gy¨ ok¨ ok sz´ ama ϕ (ϕ (m)). 4.13. Defin´ıci´ o. Tegy¨ uk fel, hogy g primit´ıv gy¨ok az m modulushoz. Az a eg´esz sz´ am index ´en (az m modulusra ´es a g primit´ıv gy¨ okre n´ezve) olyan i kitev˝ot ´ert¨ unk, amelyre g i ≡ a (mod m).
(t = 0, 1, . . . , lnko (a, m) − 1) .
(∗)
2.21. T´ etel. Ha a (∗) line´ aris kongruenciarendszernek van megold´ asa, akkor megold´ asai egyetlen mod [m1 , m2 , . . . , mk ] marad´ekoszt´ alyt alkotnak. 2.22. T´ etel. A (∗) line´ aris kongruenciarendszer k = 2 eset´en pontosan akkor oldhat´ o meg, ha lnko (m1 , m2 ) | c1 − c2 .
Jel¨ ol´ es. A modulust az egyszer˝ us´eg kedv´e´ert nem ´ırjuk ki (ez t¨obbnyire am´ ugy is vil´agos a sz¨ovegk¨ornyezetb˝ol), teh´ at a index´et r¨ oviden indg a jel¨oli. 4.14. Megjegyz´ es. Vil´agos, hogy ha a ´es m nem relat´ıv pr´ım, akkor indg a nem ´ertelmezett (ugyanis g i mindig relat´ıv pr´ım m-hez). Ha viszont a ´es m relat´ıv pr´ım, akkor a 4.8. T´etel szerint a el˝o´all g hatv´ anyak´ent modulo m, teh´ at ekkor indg a ´ertelmezett. 4.15. Megjegyz´ es. Figyelj¨ uk meg, hogy az index nem m´as, mint a logaritmus mod m anal´ogja. Nem meglep˝ o teh´ at, hogy hasonl´ o tulajdons´ agokkal rendelkezik, amint ezt a k¨ovetkez˝ o t´etelben l´atjuk. A 4.5. K¨ovetkezm´eny szerint az index (ha l´etezik) csak modulo ϕ (m) van meghat´ arozva, ez´ert az indexre vonatkoz´ o al´ abbi azonoss´agokban nem egyenl˝ os´egeket, hanem mod ϕ (m) kongruenci´ akat ´ırunk.
2.23. T´ etel∗ . A (∗) line´ aris kongruenciarendszer akkor ´es csak akkor oldhat´ o meg, ha b´ armely k´et kongruenci´ ab´ ol a ´ll´ o r´eszrendszere megoldhat´ o. Speci´ alisan, p´ aronk´ent relat´ıv pr´ım modulusok eset´en mindig van megold´ as. 2.24. T´ etel (k´ınai marad´ ekt´ etel). Tegy¨ uk fel, hogy az m1 , m2 , . . . , mk modulusok p´ aronk´ent relat´ıv pr´ımek, jel¨ olje a szorM (i = 1, 2, . . . , k). Jel¨ olje yi az Mi yi ≡ 1 (mod mi ) seg´edkongruencia egy megold´ as´ at zatukat M , tov´ abb´ a legyen Mi = m i (i = 1, 2, . . . , k). Ekkor a (∗) line´ aris kongruenciarendszer megold´ asa: x≡
k X i=1
ci Mi yi (mod M ) .
Marad´ ekrendszerek, az Euler-f´ ele ϕ f¨ uggv´ eny, nevezetes kongruenciat´ etelek
3.7. Defin´ıci´ o. Az n term´eszetes sz´ amot t¨ ok´ eletes sz´ amnak nevezz¨ uk, ha megegyezik pozit´ıv val´ odi oszt´oinak ¨osszeg´evel, azaz σ (n) = 2n.
2.25. T´ etel (Wilson t´ etele). Ha p pr´ımsz´ am, akkor (p − 1)! ≡ −1 (mod p). 2.26. Defin´ıci´ o. Modulo m teljes marad´ ekrendszer nek nevezz¨ uk eg´esz sz´ amok egy olyan rendszer´et, amely minden mod m marad´ekoszt´alyb´ ol pontosan egy elemet tartalmaz. 2.27. T´ etel. Ha az a1 , a2 , . . . , am eg´esz sz´ amok teljes marad´ekrendszert alkotnak modulo m, ´es b, c ∈ Z, lnko (c, m) = 1, akkor ca1 + b, ca2 + b, . . . , cam + b is teljes marad´ekrendszer modulo m. 2.28. Defin´ıci´ o. Modulo m reduk´ alt marad´ ekrendszer nek nevezz¨ uk eg´esz sz´ amok egy olyan rendszer´et, amely minden mod m reduk´alt marad´ekoszt´alyb´ ol pontosan egy elemet tartalmaz. 2.29. T´ etel. Ha az a1 , a2 , . . . , ak eg´esz sz´ amok reduk´ alt marad´ekrendszert alkotnak modulo m, ´es c ∈ Z, lnko (c, m) = 1, akkor ca1 , ca2 , . . . , cak is reduk´ alt marad´ekrendszer modulo m. 2.30. Defin´ıci´ o. Jel¨olj¨ uk ϕ (m)-mel az m-n´el nem nagyobb term´eszetes sz´ amok k¨oz¨ ul azoknak a sz´ am´ at, amelyek mele ϕ f¨ uggv´ eny nek hez relat´ıv pr´ımek: ϕ (m) = |{a : 1 ≤ a ≤ m ´es lnko (a, m) = 1}|. Az ´ıgy kapott f¨ uggv´enyt Euler-f´ nevezz¨ uk. T¨ om¨orebben: ϕ : N → N, m 7→ |Z∗m | . 2.31. T´ etel (Euler–Fermat-t´ etel). Ha az a eg´esz sz´ am relat´ıv pr´ım az m modulushoz, akkor aϕ(m) ≡ 1 (mod m). 2.32. K¨ ovetkezm´ eny (kis Fermat-t´ etel). Ha p pr´ımsz´ am, akkor minden a eg´esz sz´ amra ap ≡ a (mod p). 2.33. K¨ ovetkezm´ eny. Ha a ∈ Z relat´ıv pr´ım az m modulushoz, ´es k1 ≡ k2 (mod ϕ (m)), akkor ak1 ≡ ak2 (mod m).
3.8. T´ etel (Euler t´ etele). Az n p´ aros sz´ am akkor ´es csak akkor t¨ ok´eletes, ha el˝ oa ´ll n = 2p−1 (2p − 1) alakban, ahol p ´es 2p − 1 is pr´ımsz´ am. uk. 3.9. Defin´ıci´ o. Az el˝oz˝ o t´etelben szerepl˝o 2p − 1 alak´ u pr´ımsz´amokat Mersenne-pr´ımeknek nevezz¨ 3.10. Megjegyz´ es. Nem neh´ez bel´atni, hogy ahhoz, hogy az Mn = 2n −1 Mersenne-f´ele sz´ am pr´ımsz´am legyen, sz¨ uks´eges, hogy n maga is pr´ım legyen. De ez a felt´etel nem elegend˝ o, p´eld´aul M11 nem pr´ım. Nem ismert, hogy l´etezik-e v´egtelen sok Mersenne-pr´ım, teh´ at azt sem tudjuk, hogy l´etezik-e v´egtelen sok p´aros t¨ok´eletes sz´ am. P´ aratlan t¨ok´eletes sz´ amot egyet sem ismer¨ unk, de nincs bizony´ıtva az sem, hogy ilyen nem l´etezik. A jelenleg∗ ismert legnagyobb pr´ımsz´am is Mersenne-pr´ım: M57 885 161 , ami t´ızes sz´ amrendszerben 17 425 170 sz´ amjegyb˝ol ´all.
Konvol´ uci´ o, ¨ osszegz´ esi ´ es megford´ıt´ asi f¨ uggv´ eny, M¨ obius-f´ ele inverzi´ os formula 3.11. Defin´ıci´ o. Az f ´es g sz´ amelm´eleti f¨ uggv´enyek konvol´ uci´ o j´ an az al´ abbi k´eplettel defini´alt f ∗ g sz´ amelm´eleti f¨ uggv´enyt ´ertj¨ uk: n X f (d) · g (f ∗ g) (n) = . d d|n
3.12. T´ etel. A konvol´ uci´ o m˝ uvelete kommutat´ıv ´es asszociat´ıv, tov´ abb´ a minden f sz´ amelm´eleti f¨ uggv´enyre f ∗δ = δ∗f = f .
3. Sz´ amelm´ eleti f¨ uggv´ enyek Nevezetes sz´ amelm´ eleti f¨ uggv´ enyek, t¨ ok´ eletes sz´ amok amelm´ eleti f¨ uggv´ eny en olyan lek´epez´est ´ert¨ unk, amely a term´eszetes sz´ amok halmaz´ an van ´ertel3.1. Defin´ıci´ o. Sz´ mezve, ´ert´ekei pedig val´ os (vagy komplex) sz´ amok. 3.2. Defin´ıci´ o. Defini´alunk n´eh´ any sz´ amelm´eleti f¨ uggv´enyt (az egyik m´ar ismert): P 1 — n pozit´ıv oszt´oinak sz´ ama; • τ (n) = d|n P • σ (n) = d — n pozit´ıv oszt´oinak ¨osszege;
3.13. T´ etel. Gyeng´en multiplikat´ıv sz´ amelm´eleti f¨ uggv´enyek konvol´ uci´ oja is gyeng´en multiplikat´ıv. P amelm´eleti f¨ uggv´enyt osszegz´ esi f¨ uggv´ eny´en az F (n) = d|n f (d) sz´ 3.14. Defin´ıci´ o. Az f sz´ amelm´eleti f¨ uggv´eny ¨ ´ertj¨ uk. Az f f¨ uggv´enyt az F f¨ uggv´eny megford´ıt´ asi f¨ uggv´ eny´enek nevezz¨ uk. Jel¨ ol´ es. Azt a t´enyt, hogy F az f ¨osszegz´esi f¨ uggv´enye gyakran egyszer˝ uen csak f → F jel¨oli. 3.15. T´ etel. Gyeng´en multiplikat´ıv sz´ amelm´eleti f¨ uggv´eny ¨ osszegz´esi f¨ uggv´enye is gyeng´en multiplikat´ıv. 3.16. T´ etel. A tanult nevezetes sz´ amelm´eleti f¨ uggv´enyek k¨ oz¨ ott fenn´ allnak az al´ abbi ¨ osszef¨ ugg´esek: δ → 1 → τ,
ϕ → id →σ.
d|n
• ϕ (n) = |Z∗n | — az els˝ o n term´eszetes sz´ am k¨oz¨ ul az n-hez relat´ıv pr´ımek sz´ ama; • id (n) = n; • 1 (n) = 1; 1, ha n = 1; • δ (n) = 0, ha n > 1. Qk i 3.3. T´ etel. Legyen az n term´eszetes sz´ am pr´ımt´enyez˝ os felbont´ asa n = i=1 pα i . Ekkor τ (n) =
k Y
(αi + 1) ;
i=1 k i +1 Y −1 pα i i = 1 + pi + p2i + · · · + pα ; i p i−1 i=1 i=1 k k k Y Y Y 1 αi −1 i = ϕ (n) = n · = pα piαi −1 (pi − 1) . 1− i − pi pi i=1 i=1 i=1
σ (n) =
k Y
en multiplikat´ıv , ha f (1) = 1 ´es b´armely 3.4. Defin´ıci´ o. Azt mondjuk, hogy az f sz´ amelm´eleti f¨ uggv´eny gyeng´ egym´ ashoz relat´ıv pr´ım a, b term´eszetes sz´ amok eset´en f (ab) = f (a) · f (b). 3.5. T´ etel. Egy f sz´ amelm´eleti f¨ uggv´eny akkor ´es csak akkor gyeng´en multiplikat´ıv, ha f (1) = 1 ´es tetsz˝ oleges p1 , . . . , pn pr´ımsz´ amok ´es α1 , . . . , αn pozit´ıv kitev˝ ok eset´en
3.17. Defin´ıci´ o. Az n term´eszetes sz´ amot n´ egyzetmentesnek nevezz¨ uk, ha nem oszthat´o egyetlen 1-n´el nagyobb n´egyzetsz´ammal sem. 3.18. Megjegyz´ es. K¨onny˝ u meggondolni, hogy egy sz´ am akkor ´es csak akkor n´egyzetmentes, ha pr´ımfelbont´as´ aban minden pr´ım csak egyszer (azaz els˝ o hatv´ anyon) fordul el˝o. 3.19. Defin´ıci´ o. M¨ obius-f¨ uggv´ eny nek nevezz¨ uk az al´ abbi k´eplettel defini´alt µ sz´ amelm´eleti f¨ uggv´enyt: 0, ha n nem n´egyzetmentes; µ (n) = k (−1) , ha n el˝o´all k k¨ ul¨onb¨oz˝ o pr´ım szorzatak´ent. 3.20. T´ etel. A M¨ obius-f¨ uggv´eny ¨ osszegz´esi f¨ uggv´enye a δ f¨ uggv´eny, azaz µ → δ. 3.21. T´ etel (M¨ obius-f´ ele megford´ıt´ asi k´ eplet). Tetsz˝ oleges F sz´ amelm´eleti f¨ uggv´eny eset´en F -nek egyetlen megford´ıt´ asi f¨ uggv´enye van, m´egpedig F ∗ µ. M´ ask´eppen fogalmazva f → F akkor ´es csak akkor a ´ll fenn, ha f = F ∗ µ. R´eszletesebben: tetsz˝ oleges f, F sz´ amelm´eleti f¨ uggv´enyek eset´en n X X F (d) · µ f (d) ⇐⇒ ∀n ∈ N : f (n) = ∀n ∈ N : F (n) = . d d|n
α1 αn αn 1 f (pα 1 · . . . · pn ) = f (p1 ) · . . . · f (pn ) .
3.6. T´ etel. A τ, σ, ϕ, id, 1, δ sz´ amelm´eleti f¨ uggv´enyek gyeng´en multiplikat´ıvak.
d|n
3.22. K¨ ovetkezm´ eny. Gyeng´en multiplikat´ıv sz´ amelm´eleti f¨ uggv´eny megford´ıt´ asi f¨ uggv´enye is gyeng´en multiplikat´ıv.
∗
2013.08.20. Forr´ as: www.mersenne.org.
