Sz´amelm´eleti alapfogalmak ´ . Az a ∈ IN sz´am oszt´oja a b ∈ IN sz´amnak ha l´etezik c ∈ IN melyre a·c = b. 1. Defin´ıcio ♦ Jel¨ol´ese: a|b. ´lda. 2. Pe a|0 b´armely a sz´amra teljes¨ ul, mivel c = 0 univerz´alisan megfelel: a · 0 = 0. 0|b csak b = 0 eset´en teljes¨ ul, mert b´armely c-re 0 · c = b-b˝ol b = 0 k¨ovetkezik. a|1 csak a = 1-re lesz igaz, mert a · c = 1-b˝ol a = 1 (´es c = 1) k¨ovetkezik. 1|b b´armely b-re teljes¨ ul, hiszen c = b v´alaszt´assal 1 · b = b. a|a b´armely a eset´en fenn´all, hiszen a · 1 = a. (c = 1)2 ´ . A p ∈ IN sz´amt pr´ım, ha p-nek pontosan k´et oszt´oja van. Egy term´eszetes 3. Defin´ıcio sz´am ¨osszetett, ha egyn´el nagyobb ´es nem pr´ım. ♦ Jel¨ol´es: p ∈ IP ´lda. 0 6∈ IP, 1 6∈ IP, 2 ∈ IP, 3 ∈ IP, 4 6∈ IP, 5 ∈ IP, ... 2 4. Pe 5. T´ etel. (Sz´amelm´elet alapt´etele) Minden egyn´el nagyobb term´eszetes sz´am a t´enyez˝ ok sorrendj´et˝ol eltekintve egy´ertelm˝ uen fel´ırhat´ o pr´ımsz´ amok szorzatak´ent. Vezess¨ uk most be a π(x) f¨ uggv´enyt, amely a pozit´ıv sz´amokon van ´ertelmezve ´es megadja, hogy x-ig h´any pr´ımsz´am van. ´lda. π(1) = 0, π(2) = 1, π(2.371) = 1, π(10) = 4, ... 2 6. Pe 7. T´ etel. (Pr´ımsz´ amt´etel, De la Vall´ee Poussin, Hadamard, (egym´ ast´ ol f¨ uggetlen¨ ul, 1896)) lim x→∞
π(x) = 1. x/ ln x
A t´etel azt fejezi ki, hogy x-ig k¨or¨ ulbel¨ ul a π(x) ∼ lnxx form´aval is jel¨olni.
x ln x
pr´ımsz´am van. Ezt a t´enyt szokt´ak m´eg
´lda. Megvizsg´aljuk, hogy mekkora az es´elye annak, hogy a 150 jegy˝ 8. Pe u sz´amok k¨oz¨ ul egyet v´eletlenszer˝ uen kiv´alasztva az pr´ımsz´am lesz. M´ask´eppen fogalmazva, meghat´arozzuk, hogy a 150 jegy˝ u sz´amok k¨oz¨ott mennyi a pr´ımek ar´anya. Ha egy p pr´ım 150 jegy˝ u, akkor 10149 < p < 10150 . ³
´
³
´
π 10150 − π 10149 ∼
µ
¶
10150 10149 10 1 − = 10149 − . 150 149 ln 10 ln 10 150 ln 10 149 ln 10
Annak a val´osz´ın˝ us´ege, hogy egy v´eletlenszer˝ uen kiv´alasztott 150 jegy˝ u sz´am pr´ım: µ
¶
1 1 π (10150 ) − π (10149 ) 10 ∼ − = 0.0029. 150 149 10 − 10 9 ln 10 150 149 1 Mivel 0.0029 ≈ 345, a kapott eredm´enyt u ´gy szeml´eltethetj¨ uk, hogy a 150 jegy˝ u sz´amok k¨oz¨ ul ´atlagosan minden 345-¨odik pr´ım. Ehhez hozz´at´eve, hogy a pr´ımek keres´es´en´el p´aros
1
sz´amokkal nem pr´ob´alkozunk, nagyj´ab´ol minden 172-edik k´ıs´erletre fogunk pr´ımsz´amra bukkanni.2 ´ . A d ∈ IN sz´amot az a ∈ IN ´es b ∈ IN sz´amok legnagyobb k¨oz¨os oszt´oj´anak 9. Defin´ıcio nevezz¨ uk, ha • d|a ´es d|b (d k¨oz¨os oszt´o); • ha d1 6= d ´es d1 |a, d1 |b akkor d1 < d (d a k¨oz¨os oszt´ok k¨oz¨ ul a legnagyobb). ♦
Jel¨ol´es: d = gcd(a, b).
´lda. gcd(10, 0) = 10, gcd(10, 4) = 2, gcd(10, 21) = 1. 2 10. Pe ´ . Ha gcd(a, b) = 1 akkor az a ´es b sz´amokat relat´ıv pr´ımeknek nevezz¨ 11. Defin´ıcio uk. ♦ A legnagyobb k¨oz¨os oszt´o meghat´aroz´as´ara k´et elj´ar´ast ismertet¨ unk. Az els˝o az ´altal´anos iskol´ab´ol ismert, ennek a m´odszernek egy gyeng´ej´ere fel fogjuk h´ıvni a figyelmet. A m´asodik algoritmus az ´okori G¨or¨ogorsz´agb´ol sz´armazik, enn´el jobb m´odszert l´enyeg´eben ma sem lehet mondani a legnagyobb k¨oz¨os oszt´o meghat´aroz´as´ara.
I. gcd(a, b) meghat´ aroz´ asa pr´ımt´ enyez˝ okre val´ o bont´ assal Legyen ismert az a ´es b term´eszetes sz´amok pr´ımfelbont´asa: a = pα1 1 pα2 2 . . . pαs s
b = pβ1 1 pβ2 2 . . . pβs s
,
,
ahol megengedj¨ uk, hogy a kitev˝ok k¨oz¨ott lehet 0 is, de az azonos pr´ımalaphoz tartoz´o kitev˝ok ¨osszege pozit´ıv legyen. Teh´at b´armelyik pi a k´et pr´ımfelbont´as valamelyik´eben t´enylegesen szerepeljen. Ekkor min{α1 ,β1 } min{α2 ,β2 } p2
gcd(a, b) = p1
s ,βs } . . . pmin{α s
.
A probl´ema az, hogy nagy a ´es b sz´amok eset´en a pr´ımfaktoriz´aci´ot nem lehet bel´athat´o id˝on bel¨ ul el˝oa´ll´ıtani. ´lda. a = 4200 = 23 · 3 · 52 · 7, b = 980 = 22 · 5 · 72 , gcd(a, b) = 22 · 5 · 7 = 140. 2 12. Pe
II. gcd(a, b) meghat´ aroz´ asa Euklideszi algoritmussal Az algoritmus ismertet´es´ehez sz¨ uks´eg lesz az al´abbi t´etelre. 13. T´ etel. (Marad´ekos oszt´as t´etele) Legyenek a > b > 0 tetsz˝ oleges term´eszetes sz´amok. Ekkor egy´ertelm˝ uen l´eteznek olyan q ´es r term´eszetes sz´amok melyekre a=q·b+r
,
2
0≤r
A t´etelben szerepl˝o r-et oszt´asi marad´eknak is szok´as h´ıvni, m´ıg q-ra haszn´alhatjuk a h´anyados elnevez´est. Az euklideszi algoritmus sor´an marad´ekos oszt´asokat v´egz¨ unk egym´as ut´an, eg´eszen addig m´ıg a marad´ek 0 nem lesz. Ez el˝obb ut´obb be fog k¨ovetkezni, mert a marad´ekos oszt´asokn´al a marad´ekok cs¨okken˝o sorozatot alkotnak. A legnagyobb k¨oz¨os oszt´o az utols´o nem nulla marad´ek lesz: gcd(a, b) = rn . a = q1 · b + r1 , b = q2 · r1 + r2 , r1 = q3 · r2 + r3 , .. .
0 < r1 < b 0 < r 2 < r1 0 < r 3 < r2 .. .
rn−2 = qn · rn−1 + rn , rn−1 = qn+1 · rn ,
0 < rn < rn−1 (rn+1 = 0)
´lda. Mivel egyenl˝o 1547 ´es 560 legnagyobb k¨oz¨os oszt´oja? 14. Pe 1547 = 2 · 560 + 427 , 560 = 1 · 427 + 133 , 427 = 3 · 133 + 28 , 133 = 4 · 28 + 21 , 28 = 1 · 21 + 7 , 21 = 3 · 7 ,
0 < 427 < 560 0 < 133 < 427 0 < 28 < 133 0 < 21 < 28 0 < 7 < 21
Teh´at gcd(1547, 560) = 7. 2 15. T´ etel. Ha gcd(a, b) = c akkor l´eteznek olyan x ´es y eg´esz(!) sz´amok, melyekre c = ax + by. Az el˝oz˝o t´etelben szerepl˝o x ´es y egy¨ utthat´okat az Euklideszi algoritmus sz´am´ıt´asait felhaszn´alva lehet kisz´amolni. Minden sorban – fel¨ ulr˝ol lefel´e haladva – a marad´ekot fejezz¨ uk ki a-val ´es b-vel, ´es felhaszn´aljuk a kor´abbi sz´amol´asok eredm´eny´et is. ´lda. 16. Pe 427 = 1547 − 2 · 560; 133 = 560 − 1 · 427 = 3 · 560 − 1 · 1547; 28 = 427 − 3 · 133 = 4 · 1547 − 11 · 560; 21 = 133 − 4 · 28 = 47 · 560 − 17 · 1547; 7 = 28 − 1 · 21 = 21 · 1547 − 58 · 560. Teh´at x = 21 ´es y = −58. 2 ´ . Legyen n > 0 term´eszetes sz´am. Bevezetj¨ 17. Defin´ıcio uk az Euler-f´ele ϕ f¨ uggv´enyt az al´abbi m´odon. Legyen ϕ(1) = 1, tov´abb´a n > 1 eset´en ϕ(n) megadja, hogy az 1, 2, . . . , n− 1 sz´amok k¨oz¨ ul h´any n-hez relat´ıv pr´ım van. ♦ ´lda. ϕ(6) = 2, mert az 1, 2, 3, 4, 5 k¨oz¨ 18. Pe ul csak az 1 ´es 5 relat´ıv pr´ım 6-hoz. (gcd(2, 6) = 2, gcd(3, 6) = 3, gcd(4, 6) = 2.) 2 asa n = pα1 1 pα2 2 . . . pαs s akkor 19. T´ etel. Ha 1 < n pr´ımfelbont´ Ã
1 ϕ(n) = n 1 − p1
!Ã
!
Ã
1 1 1− ... 1 − p2 ps 3
!
.
´lda. 20. Pe ϕ(6) = 6(1 − 1/2)(1 − 1/3) = 2; n = p ∈ IP eset´en ϕ(p) = p(1 − 1/p) = p − 1; n = pq (p, q ∈ IP) eset´en ϕ(n) = pq(1−1/p)(1−1/q) = (p−1)(q−1) = n−p−q+1.2
4
Kongruenci´ak Az oszthat´os´ag, a pr´ımsz´amfogalom, az Euklideszi algoritmus term´eszetes sz´amokra adott ´ertelmez´ese egyszer˝ u megfontol´asok ut´an kiterjeszthet˝o az eg´esz sz´amok halmaz´ara. A tov´abbiakban az eg´esz sz´amok k¨or´eben vizsg´al´odunk. ´ . Legyenek a, b, m ∈ ZZ. Azt mondjuk, hogy a kongruens b modulo m, ha 21. Defin´ıcio m|(a − b). ♦ Jel¨ol´es: a ≡ b (mod m) ´lda. Az m = 0, ±1 esetek nem t´ 22. Pe ul ´erdekesek. Ugyanis a ≡ b (mod 0) akkor ´es csak akkor igaz, ha 0|(a − b), azaz ha a = b. A 0 modulusra n´ezve minden sz´am csak ¨onmag´aval kongruens. a ≡ b (mod ± 1) viszont b´armely a ´es b eg´eszekre teljes¨ ul, hiszen ±1|(a − b) mindig igaz. Most szeretn´enk meghat´arozni, hogy mely x eg´eszek lesznek kongruensek 13-mal modulo 5. Azaz mely x-ekre teljes¨ ul, hogy 5|(x−13). Pl. x = 13, vagy x = 18 j´o lesz, de k¨onny˝ u tov´abbi p´eld´akat mutatni: x = 23, x = 28, s˝ot x = 8, x = 3, vagy x = −2 is megfelel. Minden olyan x eg´esz j´o lesz, amely x = 5k+3 alak´ u. Teh´at x = . . . , −2, 3, 8, 13, 18, 23, 28, . . .. ´ Altal´aban azt az x-et szoktuk keresni, melyre 0 ≤ x < m, jelen esetben 0 ≤ x = 3 < 5. 2 23. T´ etel. (Euler-Fermat t´etel) Ha gcd(a, m) = 1 akkor aϕ(m) ≡ 1 (mod m). Ha m = p pr´ım, ´es p 6 |a akkor a t´etel az ap−1 ≡ 1
(mod p) alakot ¨olti.
334
´lda. 32005 = 3334·6+1 = (36 ) · 31 ≡ 1334 · 3 = 3 (mod 7). Ebb˝ol k¨ovetkezik, 24. Pe hogy ha 2005. m´arcius 11-e p´entek, akkor 32005 nap m´ ulva p´entek + 3 nap = h´etf˝o lesz. 2 ´ . Az a ´es b eg´eszek egym´as multiplikat´ıv inverzei modulo m, ha ab ≡ 1 25. Defin´ıcio (mod m). ♦ 26. T´ etel. Egy a eg´esz sz´amnak akkor ´es csak akkor l´etezik multiplikat´ıv inverze modulo m ha gcd(a, m) = 1. ´lda. Az a = 3-nak l´etezik multiplikat´ıv inverze modulo 10, mert 3 ´es 10 relat´ıv 27. Pe pr´ımek. K¨onny˝ u l´atni, hogy a = 3 eset´en b = 7 vagy b = −3 vagy pl. b = 77 is j´o. ´ Altal´aban itt is azon b ´ert´eket keress¨ uk, melyre 0 < b < m teljes¨ ul, jelen p´eld´aban teh´at 0 < b = 7 < 10. 2
I. Multiplikat´ıv inverz meghat´ aroz´ asa Euklideszi algoritmussal Ha gcd(a, m) = 1 akkor l´eteznek x ´es y eg´eszek, melyekre ax + bm = 1. Mivel 1 ≡ ax + bm ≡ ax (mod m), 5
ez´ert a multiplikat´ıv inverze ´eppen az x egy¨ utthat´o lesz, melyet az Euklideszi algoritmusb´ol tudtunk kisz´amolni. A gyakorlat szemponj´ab´ol ezt a meghat´aroz´asi m´odszert prefer´aljuk. Az Euler-Fermat t´etel is lehet˝os´eget ny´ ujt a multiplikat´ıv inverz megad´as´ara.
II. Multiplikat´ıv inverz meghat´ aroz´ asa Euler-Fermat t´ etellel Ha gcd(a, m) = 1 akkor aϕ(m) = a · aϕ(m)−1 ≡ 1
(mod m),
teh´at a multiplikat´ıv inverze ´eppen aϕ(m)−1 lesz, melynek meghat´aroz´as´ara haszn´aljuk valamilyen lehet˝oleg gyors hatv´anyoz´o elj´ar´ast.
6