´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) Pr´ımsz´ amok A (pozit´ıv) pr´ımsz´amok sorozata a k¨ovetkez˝ o: 2, 3, 5, 7, 11, 13, 17, 19, .... 1. T´ etel. V´egtelen sok pr´ımsz´am van. Els˝ o bizony´ıt´ as. (Euklid´esz) Tegy¨ uk fel, hogy ´all´ıt´ asunk nem igaz, teh´ at v´eges sok pr´ımsz´ am l´etezik, legyenek ezek: p1 , p2 , ..., pk . Tekints¨ uk az A = p1 p2 · · · pk + 1 sz´ amot, amelynek van egy q pr´ımoszt´ oja. A feltev´es szerint q = pi valamely i-re, hiszen csak a p1 , p2 , ..., pk pr´ımek l´eteznek ´es k¨ ovetkezik, hogy pi | 1, ami ellentmond´as. M´ asodik bizony´ıt´ as. Megmutatjuk, hogy minden n ≥ 1 sz´ amn´ al van nagyobb pr´ımsz´ am. Legyen N = n! + 1 > 1, ´ıgy N -nek van legal´abb egy p pr´ımoszt´ oja. Itt p > n, mert ha p ≤ n lenne, akkor p | n!, ahonnan p | 1, ami ellentmond´as. n Harmadik bizony´ıt´ as. Tekints¨ uk az Fn = 22 + 1, n ≥ 0 sz´ amsorozatot. Minden Fn sz´ amnak l´etezik n egy qn pr´ımoszt´oja. Az Fn = 22 + 1 sorozat tagjai p´aronk´ent relat´ıv pr´ımek, l´ asd Feladat. ´Igy a qn pr´ımsz´amok p´aronk´ent k¨ ul¨onb¨oz˝ok, teh´at q1 , q2 , ... pr´ımsz´ amok v´egtelen sorozata. n
2. Feladat. Igazoljuk, hogy az Fn = 22 + 1, n ≥ 0 sorozat tagjai p´aronk´ent relat´ıv pr´ımek. n
3. Megjegyz´ es. Az Fn = 22 + 1, n ≥ 0 sz´ amokat Fermat-sz´ amoknak, az ilyen alak´ u pr´ımeket pedig Fermat-pr´ımeknek nevezz¨ uk. Fermat azt sejtette, hogy az Fn sz´ amok mind pr´ımek. Nos, F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537 pr´ımek, F5 viszont nem pr´ım, oszthat´ o 641-gyel (ezt el˝ osz¨or Euler igazolta). Nem tudjuk, hogy l´eteznek-e tov´ abbi Fermat-pr´ımek. A 2 az egyed¨ uli p´aros pr´ımsz´am, a t¨ obbi pr´ım 4k − 1 alak´ u (3, 7, 11, 19, ...) vagy 4k + 1 alak´ u (5, 13, 17, 29, ...). 4. T´ etel. 1) V´egtelen sok 4k − 1 alak´ u pr´ım l´etezik. 2) V´egtelen sok 4k + 1 alak´ u pr´ım l´etezik. Bizony´ıt´ as. 1) Az euklid´eszi bizony´ıt´ashoz hasonl´ oan tegy¨ uk fel, hogy v´eges sok 4k − 1 alak´ u pr´ım l´etezik: p1 , p2 , ..., pr . Legyen B = 4p1 p2 · · · pr − 1. Azonnali, hogy 2 - B ´es p1 - B, p2 - B, ..., pr - B. K¨ovetkezik, hogy B-nek minden pr´ımoszt´ oja 4k + 1 alak´ u, de akkor B maga is 4k + 1 alak´ u, s ez ellentmond´as. 2) A m´asodik ´all´ıt´as hasonl´ok´eppen igazolhat´ o. Tegy¨ uk fel, hogy v´eges sok 4k + 1 alak´ u pr´ımsz´ am van: p1 , p2 , ..., ps . Ha a C = 4p1 p2 · · · ps + 1 sz´ amot vizsg´aljuk, akkor nem jutunk ellentmond´ asra, mert megt¨ ort´enhet, hogy C-nek p´ aros sz´ am´ u 4k − 1 alak´ u pr´ımoszt´oja van. Legyen D = (2p1 p2 · · · ps )2 + 1, melyre 2 - D, p1 - D, p2 - D, ..., ps - D. Kapjuk, hogy D-nek l´etezik egy q = 4k − 1 alak´ u pr´ımoszt´ oja. ´Igy q | x2 + 1, ahol x = 2p1 p2 · · · ps , q−1 2 q−1 2k−1 ≡ − 1 (mod q). A Fermat-t´etel szerint azaz x ≡ − 1 (mod q), innen x ≡ (−1) 2 ≡ (−1) q−1 x ≡ 1 (mod q), ´es kapjuk, hogy −1 ≡ 1 (mod q). Innen q = 2, ellentmond´ as. M´ask´epp: Legyen n > 1. Olyan 4k + 1 alak´ u pr´ımet szerkeszt¨ unk, amely n-n´el nagyobb. Tekints¨ uk 2 2 az m = (n!) + 1 p´aratlan sz´am valamely p pr´ımoszt´ oj´ at. Ekkor p p´ aratlan, p > n ´es (n!) ≡ − 1 p−1 (mod p), (n!)p−1 ≡ (−1) 2 (mod p). A Fermat-t´etel szerint (n!)p−1 ≡ 1 (mod p), ´es kapjuk, hogy p−1 p−1 (−1) 2 ≡ 1 (mod p). Innen (−1) 2 = 1, azaz p ≡ 1 (mod 4). A 2 ´es 3 pr´ımek kiv´etel´evel minden pr´ım 6k − 1 alak´ u (5, 11, 17, ...) vagy 6k + 1 alak´ u (7, 13, 19, ...). Itt a 3-n´al nagyobb 6k, 6k + 2, 6k + 3 ´es 6k + 4 alak´ u sz´ amok biztosan ¨ osszetettek. A 6k + 5 alak´ u sz´ amok helyett tekinthetj¨ uk a 6k − 1 alak´ uakat. Hasonl´ok´eppen igazolhat´o, hogy v´egtelen sok 6k − 1 alak´ u ´es v´egtelen sok 6k + 1 alak´ u pr´ımsz´ am l´etezik. Mindezekn´el ´altal´anosabb a k¨ovetkez˝ o t´etel: 5. T´ etel. (Dirichlet) Minden ak + b, k ≥ 0 sz´ amtani sorozatban, ahol (a, b) = 1, v´egtelen sok pr´ımsz´am van. 6. Feladat. Igazoljuk, hogy v´egtelen sok 6k − 1 alak´ u pr´ımsz´ am van.
1
´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) Megold´ as. Tegy¨ uk fel, hogy v´eges sok 6k − 1 alak´ u pr´ım l´etezik: p1 , p2 , ..., pr . Legyen N = 6p1 p2 · · · pr − 1. Azonnali, hogy 2 - N ´es p1 - N, p2 - N, ..., pr - N . K¨ ovetkezik, hogy N -nek minden pr´ımoszt´oja 6k + 1 alak´ u, de akkor N maga is 6k + 1 alak´ u, ami ellentmond´ as. 7. Feladat. Igazoljuk, hogy minden n ≥ 2 sz´ am fel´ırhat´ o pr´ımek ¨ osszegek´ent. Megold´ as. n = 2k = 2| + 2 + n = 2k + 1 = |2 + 2 + {z... + 2}, {z... + 2} +3. k
k−1
8. Megjegyz´ es. A (mindm´aig bizony´ıtatlan) 1742-ben kimondott Goldbach-sejt´es szerint minden n > 2 p´aros sz´am fel´ırhat´o k´et pr´ımsz´am ¨ osszegek´ent. Ebb˝ol azonnal k¨ovetkezik, hogy minden n > 5 p´ aratlan sz´ am fel´ırhat´ o h´arom pr´ımsz´ am ¨ osszegek´ent. Itt n = 3 + (n − 3), ahol n − 3 > 2 p´ aros sz´ am. 9. Feladat. Igazoljuk, hogy minden n ≥ 12 sz´ am fel´ırhat´ o k´et o am ¨ osszegek´ent. ¨sszetett sz´ n 2 10. Feladat. Fel´ırhat´o-e Fn = 2 + 1, n ≥ 0 k´et pr´ımsz´ am ¨ osszegek´ent? 11. T´ etel. Minden n > 1 sz´amhoz megadhat´ o n egym´ asut´ ani ¨ osszetett sz´ am. Bizony´ıt´ as. Legyen ak = (n + 1)! + k + 1, ahol k ∈ {1, 2, ..., n}. Ezek egym´ asut´ ani sz´ amok ´es mindegyik ¨osszetett, hiszen k + 1 | ak ´es ak > k + 1 minden k ∈ {1, 2, ..., n} eset´en. Legyen dn = pn+1 − pn . Az el˝oz˝o t´etel szerint a (dn )n≥1 sorozat nem korl´ atos. Ez a t´etel nem jelenti azt, hogy nagy sz´ amokat vizsg´ alva a pr´ımek egyre ritk´ abban fordulnak el˝ o. L´eteznek olyan pr´ımsz´amok, melyek k¨ ul¨onbs´ege 2. Ilyen pr´ımek, u ´gynevezett ikerpr´ımek, p´eld´aul a k¨ ovetkez˝ok: (3, 5), (5, 7), (11, 13), (17, 19), ..., (109 + 7, 109 + 9), .... Vannak olyan pr´ımek, s˝ ot v´egtelen sok, l´asd Feladat, amelyek nem tagjai ikerpr´ımsz´ amp´ aroknak, pl. 23, 37, 47, .... A pr´ımsz´ amelm´elet egy nevezetes, mindm´aig megoldatlan k´erd´ese az, hogy l´etezik-e v´egtelen sok ikerpr´ımsz´ amp´ ar. 12. Feladat. Lehet-e a p, p + 2, p + 4 sz´ amok mindegyike pr´ımsz´ am? 13. Feladat. Ha p, q ≥ 5 ikerpr´ımek, akkor 12 | p + q. Megold´ as. 6-tal osztva minden p > 3 pr´ımsz´ am 6k + 1 vagy 6k + 5 alak´ u. Ha p, q ≥ 5 ikerpr´ımek, akkor ´ıgy p = 6k − 1 ´es q = 6k + 1 alak´ u, ugyanazzal a k-val. Innen azonnali, hogy p + q = 12k oszthat´o 12-vel. 14. Feladat. Lehetnek-e 2n − 1 ´es 2n + 1 ikerpr´ımek, ahol n ≥ 1? P 15. T´ etel. (Pr´ımsz´amt´etel) Ha π(x) = p≤x 1 jel¨ oli a pr´ımsz´ amok sz´ am´ at x-ig, akkor lim
x→∞
azaz π(x) ∼
x log x
π(x) x log x
= 1,
(a ∼ jelet olvasd: aszimptotikusan egyenl˝ o).
Innen azonnali, hogy
π(x) = 0. x→∞ x lim
Megjegyz´ es. Ha (an )n≥1 egy term´eszetes sz´ amokb´ ol ´all´ o sorozat, akkor jel¨ olje u(x) = u(x) 1 a sorozat x-n´ e l nem nagyobb tagjainak a sz´ a m´ a t. Az adott sorozat s˝ u r˝ u s´ e g´ e n a lim x→∞ x an ≤x hat´ar´ert´eket ´ertj¨ uk, felt´eve, hogy ez l´etezik. A p´ aros sz´ amok s˝ ur˝ us´ege p´eld´ aul 1/2, a n´egyzetsz´amok s˝ ur˝ us´ege nulla, ´es az el˝obbiek szerint a pr´ımsz´ amok s˝ ur˝ us´ege is nulla, azaz a pr´ımek ritk´ an” fordulnak ” el˝ o a term´eszetes sz´amok k¨oz¨ott. Jel¨olje pn az n-edik pr´ımsz´amot. ´Igy p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, ... ´es pn → ∞, ha n → ∞. P
16.
17. T´ etel. (Csebisev) Ha n ≥ 2, akkor l´etezik olyan p pr´ımsz´ am, melyre n < p < 2n. 2
´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) 18. Feladat. Igazoljuk, hogy pn+1 < 2pn minden n ≥ 1 eset´en. Megold´ as. Azonnali a Csebisev-t´etelb˝ol: pn ´es 2pn k¨ oz¨ ott van pr´ım, ´ıgy pn+1 < 2pn . 19. Feladat. A Csebisev-t´etel alkalmaz´ asak´ent igazoljuk, hogy minden n ≥ 2 eset´en pn < 2n . Megold´ as. Indukci´oval bizony´ıtunk. Ha n = 2, akkor p2 = 3 < 22 , igaz. Tegy¨ uk fel, hogy a tulajdons´ag igaz valamely k ≥ 2-re, azaz pk < 2k . Akkor a T´etel alapj´ an 2k ´es 2k+1 k¨ oz¨ ott l´etezik k+1 pr´ımsz´am, amely nagyobb mint pk , ´ıgy pk+1 < 2 . 20. T´ etel. (A pr´ımsz´amt´etel m´asik alakja) pn = 1, n→∞ n log n lim
azaz pn ∼ n log n. 21. Feladat. Igazoljuk, hogy l´etezik v´egtelen sok olyan pr´ımsz´ am, melyeknek els˝ o sz´ amjegye 1-es (10-es sz´amrendszerben fel´ırva). Megold´ as. A Csebisev-t´etel szerint minden k ≥ 1-re 10k ´es 2 · 10k k¨ oz¨ ott van pr´ımsz´ am, ´es ez olyan sz´ am, amelynek els˝o jegye 1-es ´es k + 1-jegy˝ u. ´Igy k¨ ul¨ onb¨ oz˝ o k ´ert´ekekre k¨ ul¨ onb¨ oz˝ o ilyen pr´ımeket kapunk. 22. Feladat. Lehet-e egy pozit´ıv eg´eszekb˝ ol ´all´ o v´egtelen sz´ amtani sorozat minden tagja pr´ımsz´am? Megold´ as. Legyen a, a + r, a + 2r, ..., a + nr, ... egy sz´ amtani sorozat, ahol a > 1 (a = 1 nem pr´ım) ´es r ≥ 0. Ha r = 0, akkor lehet minden tag pr´ım, pl. 2, 2, 2, .... Ha r ≥ 1, akkor a + ar = a(1 + r) ¨osszetett (a ≥ 2, 1 + r ≥ 2), nem lehet minden tag pr´ım. 23. Megjegyz´ es. P´eld´ak v´eges sok tag´ u sz´ amtani sorozatokra, amelyek tagjai mind pr´ımek. H´aromtag´ u: 3, 7, 11 ´es 3, 11, 19, n´egytag´ u: 41, 47, 53, 59, ¨ ottag´ u: 5, 11, 17, 23, 29, hattag´ u: 7, 37, 67, 97, 127, 157, t´ıztag´ u: 199 + 210k, 0 ≤ k ≤ 9. 24. T´ etel. (Ben Green, Terence Tao, 2004) Minden k ≥ 1 sz´ amra a pr´ımsz´ amok sorozat´ aban l´etezik v´egtelen sok k hossz´ us´ag´ u sz´amtani sorozat. Tov´abbi feladatok: 25. Feladat. Mutassuk meg, hogy v´egtelen sok olyan pr´ımsz´ am van, amely nem tagja egyetlen ikerpr´ımsz´amp´arnak sem. Megold´ as. A Dirichlet-t´etel szerint v´egtelen sok 15k + 7 alak´ u pr´ım l´etezik, ahol (15, 7) = 1. Itt (15k + 7) − 2 = 15k + 5 oszthat´o 5-tel, (15k + 7) + 2 = 15k + 9 oszthat´ o 3-mal, teh´ at nem pr´ım. 26. Feladat. Mutassuk meg, hogy minden k ≥ 1 eset´en l´etezik v´egtelen sok olyan p pr´ımsz´ am, hogy a p − k, ..., p − 2, p − 1, p + 1, p + 2, ..., p + k sz´ amok mindegyike ¨ osszetett sz´ am (azaz l´etezik v´egtelen sok u ´n. izol´alt” pr´ım). ” Megold´ as. Legyen q pr´ım, u ´gy, hogy q ≥ k + 2 ´es legyen a = 2 · 3 · · · (q − 2)(q − 1)(q + 1)(q + 2) · · · (2q − 2), ahol (a, q) = 1. A Dirichlet-t´etel alapj´an l´etezik v´egtelen sok p = a` + q alak´ u pr´ım. Itt minden 1 ≤ i ≤ k-ra p − i = (a` + q) − i = 2 · 3 · · · (q − 2)(q − 1)(q + 1)(q + 2) · · · (2q − 2)` + q − i = = (q − i)(2 · 3 · · · (q − i − 1)(q − i + 1) · · · (q − 2)(q − 1)(q + 1)(q + 2) · · · (2q − 2)` + 1). K¨ovetkezik, hogy (q − i) | (p − i) ´es q − i ≥ q − k ≥ 2 ´es q − i < (a` + q) − i = p − i, teh´ at p − i ¨osszetett. Hasonl´oan, p + j ¨osszetett minden 1 ≤ j ≤ k-ra. 27. Feladat. Milyen n sz´amokra pr´ım n4 + 4? 3
´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) 28. T´ abl´ azat. A π(x) f¨ uggv´eny ´ert´ekei: x pi(x) ---------------------------------------------------------------------10 4 100 25 1 000 168 10 000 1 229 100 000 9 592 1 000 000 78 498 10 000 000 664 579 100 000 000 5 761 455 1 000 000 000 50 847 534 10 000 000 000 455 052 511 100 000 000 000 4 118 054 813 1 000 000 000 000 37 607 912 018 10 000 000 000 000 346 065 536 839 100 000 000 000 000 3 204 941 750 802 1 000 000 000 000 000 29 844 570 422 669 10 000 000 000 000 000 279 238 341 033 925 100 000 000 000 000 000 2 623 557 157 654 233 1 000 000 000 000 000 000 24 739 954 287 740 860 10 000 000 000 000 000 000 234 057 667 276 344 607 100 000 000 000 000 000 000 2 220 819 602 560 918 840 1 000 000 000 000 000 000 000 21 127 269 486 018 731 928 10 000 000 000 000 000 000 000 201 467 286 689 315 906 290 Forr´ as: http://primes.utm.edu/howmany.shtml#table
4
´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) 29. π(x) ´es x/ log x grafikonja (2 ≤ x ≤ 100, Maple) p:=plot([seq([n,nops(select(isprime,[$1..n]))],n=2..100)], x=0..100,y=0..30, color=red): q:=plot(x/ln(x),x=2..100,y=0..30,color=green): plots[display](\{p,q\}, title=‘pi(x) es x/log x osszehasonlitasa‘);
>
pi(x) es x/log x osszehasonlitasa 30 28 26 24 22 20 18 y
16 14 12 10 8 6 4 2 0
20
40
x
60
5
80
100
