3. előadás Prímek, tökéletes számok, Fermat-teszt, pszeudoprímek

Számítástudomány

Széchenyi István Egyetem

3. előadás Prímek, tökéletes számok, Fermat-teszt, pszeudoprímek

Dr. Kallós Gábor

2014–2015 11



Tartalom

A prímek száma és elhelyezkedése

Eratoszthenész szitája Próbaosztásos algoritmus Tökéletes számok

A nagy prímszámtétel Reciprokösszegek

Mersenne-prímek

Fermat-teszt

Pszeudoprímek Euler tétele

Feladatok Történeti áttekintés

Irodalom

A GIMPS projekt

2



A prímek száma

Ha véges sok prím van/lenne: közzétehetnénk egy könyvet/listát, amiben az összeset felsoroljuk, és így bármely számról könnyen eldönthető lenne a prímtulajdonság Azonban már Euklidesz is tudta a következőt: Állítás: A prímek száma végtelen

Bizonyítás: Soroljuk fel őket, képezzük a szorzatukat (P), vegyük az eggyel nagyobb számot… Másik bizonyítás: Euler (lásd később: 1/n sorozat összege…)

Megjegyzések

Ez az igazolás sajnos nem használható a prímek előállítására Kapunk új prímet (P + 1 hoz be új prímfaktort), de általában nem a következőt, pl.: (2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13) + 1 = 30001 = 59 ⋅ 509

Kérdés: Van egyáltalán olyan eset, amikor a következő prímet kapjuk?

Feladatok

Az euklideszi állítás nyomán szerezzünk tapasztalatokat, hogy milyen új prímek jönnek be P + 1 „bevetésével” ill. faktorizációval! *Ki tudjuk így tölteni a „prímpalettát”? (Programmal célszerű vizsgálódni.) Változat: Részszorzatokat is felhasználhatunk!

Pl. (2 ⋅ 3) + 1, (2 ⋅ 5) + 1 stb.

Vizsgáljuk meg a prímek eloszlását! Hány prímet találunk n-ig? Mekkora az n. prím? (Maple: isprime és ithprime függvények) (*Látunk valami szabályosságot?)

3



A prímek száma

Egyszerű prímtesztelő VBA függvény

4




A prímszámok n növekedésével egyre ritkábban fordulnak elő, eloszlásuk azonban alapvetően szabálytalan Fontos kérdés: Milyen sűrűn helyezkednek el az egészek között? Erre (a nehéz) kérdésre sokáig keresték a választ, a 18. sz. végén megsejtett eredményt (Legendre, Gauss) végül Hadamard és de la Vallée-Poussin bizonyította (1899) Jelölje p(n) a prímek számát n-ig (valós függvényként is értelmezhető, p(x), π(x))

Jelöljük pn-nel az n. prímet

Tétel („nagy” prímszámtétel): π ( x) =1 A prímek száma n-ig aszimptotikusan egyenlő n/(ln n)-nel, azaz lim x →∞ x / ln x És: pn ≈ n ln n

x

2

dt

−A Tétel (változat 1.)*: π ( x) = ∫ ln t + Ο( xe

log x

)

x x 2! x n! x π ( x) = + + + ... + + ... ln x (ln x) 2 (ln x)3 (ln x) n +1

Ebből parciális integrálással: Tétel (változat 2.)*: x 1 + 1  < π ( x) < x 1 + 3  ln x  2 ln x  ln x  2 ln x  ha x > 58 és 3 1   ha n > 19 n ln n + ln ln n −  < p < n ln n + ln ln n −  2 2   Szemléletes jelentés: (nagyon) sok prím van n

Ez jó akkor, ha véletlenül akarunk igen nagy prímet találni (pl. RSA algoritmus)

5




A nagy prímszámtétel eredménye azért „zseniális”, mert a formula maga egyszerű, és mégis meglepően pontos

Látható, hogy a különbség a két függvény között nagy, de a hányados ráközelít 1-re (az ábrán: logaritmikus skálák)

Feladatok

Ellenőrizzük saját programmal a közölt adatokat! Készítsünk %-os statisztikát is a prímekről! (Maple: pi(x) függvény) *Készítsünk szép ábrát a két függvényről!

6




Fontos alkalmazás: Mekkora eséllyel lesz egy véletlenül választott nagy szám prím?

Pl. 2 jegyre: 1/ln102 = 1/(2 ln10) ≈ 1/4,6 100 jegyre: 1/ln10100 = 1/(100 ln10) ≈ 1/230 (Persze az esélyeink könnyen javíthatók: kizárjuk a 2-vel, 3-mal és 5-tel osztható számokat)

Továbbá:

A prímek között nagyon nagy távolság is lehet (példa: n! után)

Ugyanakkor ismertek igen nagy ikerprímek is

De: n és 2n között mindig van prím (Bertrand, Csebisev) Sejtés: Végtelen sok ikerprím van

(Tudjuk: a természetes számok és a négyzetszámok is végtelen sokan vannak, de …) A poz. egészek reciprokösszege végtelen, a négyzetszámoké ellenben véges (és az 2 összeg 2-nél kisebb, *pontosan: π ) 6

Feladat: Igazoljuk ezeket az állításokat!

Tétel (Euler): A prímszámok reciprokösszege végtelen

Feladatok

Azaz: A prímszámok sűrűbben helyezkednek el, mint a négyzetszámok Becsüljük meg a poz. egészek köbeinek reciprokösszegét! Számoltassuk ki az eredményt Maple-ben (vagy Matlabban)! *Értelmezzük!

7




A számítások Maple-ben és Matlabban (Symbolic Math Toolbox)

8



Eratoszthenész szitája

Cél: Meg kell találnunk az összes prímet n-ig Algoritmus (vázlat): lista (inicializálás), karikázás, törlés Állítás: Elég csak n -ig elmenni, mert akkor már csak prímek maradnak a listán

Egyszerűsítés pl.: 2 többszöröseit már eleve nem is írjuk fel Feladat: Írjunk programot a feladat megoldására! (*Szép ábra!)

Komoly probléma: nagyobb n-ekre igen nagy memóriaigényű az eljárás (!)

Nagy előny (más eljárásban még felhasználjuk): nincs az eljárásban osztás (!), és lényegében nincs benne szorzás

Továbbá: n prímtulajdonságának igazolásához kb. n ciklust kell végrehajtani

9



Eratoszthenész szitája

Egyszerű megvalósítás Maple-ben

10



Próbaosztásos algoritmus

Cél: Le kell választanunk egy n számból a nem túl nagy prímosztókat

Példa

Ha n maga nem túl nagy, akkor ez teljes felbontást jelent, különben részleges felbontást Tfh. a számunk max. egymillió (25 millió) Ha nem prím, akkor n ≤ 1000 -ig lesz prímosztója (5000-ig) Szükségünk van tehát egy listára, amely 1000-ig (5000-ig) tartalmazza a prímeket, és ezekkel osztunk

Egyszerűsítési lehetőség

168 ilyen van (669) – ez könnyen tárolható

Ha találunk valódi osztót, elosztjuk vele a n-t, és folytatjuk az eljárást (amíg szükséges, azaz a felbontatlan rész még nagyobb n -nél) Nem tároljuk el a prímeket, csak a 2-vel és 3-mal osztható számokat zárjuk ki a vizsgálatból 1000-ig ez 334 osztást jelent a 168 helyett (5000-ig: 1668 a 669 helyett)

Ha egy nagy összetett szám esetében 5000-ig (néhány tízezerig) nem találunk prímosztót, akkor már nem érdemes tovább ezzel a módszerrel keresni

Átlagosan kicsi az esély arra, hogy éppen csak kicsivel nagyobb legyen az első prímosztó

(Nagyobb számok esetén a prímosztók vsz. eloszlását lásd később, ill. Knuth)

11




12



Próbaosztásos algoritmus Egy egyszerű megvalósítás

Nézzük meg az ifactor függvényt az easy opcióval!

13




A Matlab S. M. T. factor függvénye

14




Egy egyszerű megvalósítás – Excel

15



Erathoszthenész szitája és próbaosztásos algoritmus További feladatok Állítsuk elő egy saját (próbaosztásos) programunkkal a prímeket 104-ig/105-ig!

Elemezzük a megtalált prímeket! Hányat találunk köztük, amelyek 4k + 1 alakúak, és hányat, amelyek 4k – 1 alakúak? Milyen következtetésre jutunk ebből? (Állítás a): Végtelen sok 4k + 1 alakú prím van. Állítás b): Végtelen sok 4k – 1 alakú prím van.) *Találunk/észreveszünk bármilyen mintázatot/szabályosságot az előállított prímek eloszlásában?

Használjuk fel a próbaosztásos programunkat egy-egy véletlenszerűen választott 8, 10 12 és 14-jegyű szám felbontására, ill. prímtulajdonságának igazolására! Próbaosztásos programunkkal bontsuk fel 100 darab egymás utáni 10-jegyű számot! Készítsünk listát a faktorokról!

Hány prímet találunk a listában? (Megfelel ez az elvárt értéknek?) Hány teljes négyzetet találunk a listában? (*Megfelel ez az elvárt értéknek?) Mekkora számot tudunk teljesen faktorizálni „általában” a próbaosztásos algoritmussal? (Általában: pl. legalább 80% az esély) *Milyen a megtalált a prímosztók méretének az eloszlása? Hány n-nek van n3/4-nél, n1/2-nél, n1/3-nál nagyobb prímfaktora? *Minden n-nél vegyük a legnagyobb prímosztót (n_p_max). Írjuk le az ln(n_p_max)/ln(n) eloszlását, átlagát, szórását! [Általános eredmény (Knuth): egy n szám legnagyobb prímfaktora átlagosan n0,63]

16



Tökéletes számok

Az előzőekben megismert két (ókori) algoritmus nagy számokra lassú és nem hatékony

Definíció: Egy pozitív egész számot tökéletesnek nevezünk, ha egyenlő a valódi osztói összegével Az első néhány tökéletes szám: 6=1+2+3 28 = 1 + 2 + 4 + 7 + 14 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064 …

A gyorsításhoz mélyebb számelméleti ismereteket kell szereznünk

Feladat: Ellenőrizzük az utolsó két egyenlőséget! (Maple: divisors függvény a numtheory csomagban) *Próbáljuk megkeresni a következő tökéletes számot!

Fontos kérdések

Végtelen sok tökéletes szám van? (Sejtés: igen) Van-e páratlan tökéletes szám? (Sejtés: nincs) Van-e egyszerű lehetőség a (páros) tökéletes számok generálására? (Igen) A páros tökéletes számok vajon mindig 6-ra vagy 8-ra végződnek? (Igen) 17



Tökéletes számok

Az első négy tökéletes szám felbontása: 6 = 2 ⋅ 3; 28 = 22 ⋅ 7 = 4 ⋅ 7 496 = 24 ⋅ 31 = 16 ⋅ 31 8128 = 26 ⋅ 127 = 64 ⋅ 127 Definíció: Legyen M(n) = 2n – 1. Mersenne-prímeknek nevezzük azokat az M(n) számokat, amelyek prímek.

Így az első négy Mersenne-prím: 3, 7, 31, 127

Állítás: Ha M(n) Mersenne-prím, akkor m = 2n – 1 ⋅ M(n) = 2n – 1 ⋅ (2n – 1) tökéletes szám Feladatok

Állítsunk elő néhány Mersenne-számot, és nézzük meg, hogy prímek-e! (Maple: mersenne fv., numtheory csomag) Mi romlik el abban az esetben az osztóknál (a tökéletes szám képletben), ha a Mersenne-szám nem prím?

18



Tökéletes számok

Állítás (eml.): Ha M(n) Mersenne-prím, akkor m = 2n – 1 ⋅ M(n) = 2n – 1 ⋅ (2n – 1) tökéletes szám

Így tehát minden Mersenne-prímhez tartozik egy páros tökéletes szám Ezen felül az is igaz, hogy nincs más páros tökéletes szám Állítás: Ha m páros tökéletes szám, akkor található olyan egész n, hogy m = 2n – 1 ⋅ (2n – 1), és 2n – 1 prím

Bizonyítás: Ha M(n) prím, akkor m valódi osztói a következők: 1, 2, 4, …, 2n – 1, M(n), 2 ⋅ M(n), 22 ⋅ M(n), …, 2n – 2 ⋅ M(n). A valódi osztók összege így (1 + 2 + 4 + … + 2n – 1) + (1 + 2 + 4 + … + 2n – 2) ⋅ M(n) = (2n – 1) + (2n – 1 – 1) ⋅ (2n – 1) = 2n – 1 ⋅ (2n – 1)

Bizonyítás: lásd Bressoud könyv

Tétel (következm.): A páros tökéletes számok pontosan azok a 2n – 1 ⋅ (2n – 1) alakú számok, ahol 2n – 1 (Mersenne-)prím Feladatok

Mű-tökéletes számnak nevezzük (csak „házilag”) azokat a számokat, amelyek valódi osztóinak összegére valamely egyszerű szabály teljesül (pl. valódi osztói összege = önmaga – 1 vagy – 2) Keressünk ilyen számokat! *Milyen alakúak a megtalált számok? (Észreveszünk valamilyen szabályszerűséget?) 19



Tökéletes számok, Mersenne-prímek

Kérdés: Mikor lesz M(n) prím? Állítás: Ha n összetett, akkor M(n) is összetett

Így a problémánk arra redukálódott, hogy a prím M(p)-ket megkeressük

Bizonyítás: Legyen n = a ⋅ b, ahol a és b egyaránt 1-nél nagyobb egészek. Ekkor M(n) = 2a ⋅ b – 1 = (2a )b – 1 = (2a – 1) ⋅ (1 + 2a + 22a + … + 2(b – 1) ⋅ a). Itt mindkét faktor nagyobb 1-nél. M(2) = 3, M(3) = 7, M(5) = 31, M(7) = 127 mind prímek De: M(11) = 2047 = 23 ⋅ 89 nem prím! M(13) = 8191, M(17) = 131 071, M(19) = 524 287 mind prímek Az ezutáni Mersenne-prímeket a következő p értékekre találjuk: 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423 (1332 jegyű szám)

Nagyon nagy Mersenne-számok prímtulajdonsága is hatékonyan igazolható a LucasLehmer teszt segítségével

20



Mersenne-prímek

A Lucas-Lehmer teszt

Példa: q = 3

(Egyelőre magyarázat nélkül) Ekkor m = 2q – 1 = 7 A teszt lefutása: (42 – 2) mod 7 vizsgálata, ez pedig 0 Így a 7 prím

Bináris számítógépeknek ez a teszt nagyon jól „fekszik”, mert a mod (2q – 1) számítások egyszerűen megvalósíthatók (lásd még: Knuth)

A modern kor legnagyobb ismert prímszámai szinte mindig Mersenne-prímek

21



Fermat észrevétele

Fermat az összetett M(p) Mersenne-számokat vizsgálta (ahol p prím), p = 23-ig Észrevette, hogy ha q | M(p), akkor q mod p = 1 is teljesül!

Bevezetjük a kongruenciát a ≡ b (mod m) jelentése: m | (a – b) vagy a mod m = b mod m

(a és b ugyanahhoz a maradékosztályhoz tartoznak modulo m, a legkisebb maradék a kitüntetett) Lehet: egyszerű feladat a maradékosztályokról, pl. mod 5

A kongruencia egyszerű tulajdonságai (áll.)

Feladat: Nézzük meg ezt M(11)-re és M(23)-ra! Nem prím p-re ez gyakran nem érvényes pl. M(4) = 15 = 3 ⋅ 5, M(6) = 63 = 3 ⋅ 3 ⋅ 7

Ha a ≡ x (mod m) és b ≡ y (mod m) akkor a + b ≡ x + y (mod m) és a ⋅ b ≡ x ⋅ y (mod m) Ha lnko(x, m) = 1 és a ⋅ x ≡ b ⋅ x (mod m) akkor a ≡ b (mod m)

Fermat észrevétele így: ha d | M(p) – azaz d prímek szorzata, amelyek osztják M(p)-t – akkor d ≡ 1 (mod p) Sőt, d = M(p) is lehet, így 2p – 1 ≡ 1 (mod p) És itt, ha p nem 2, hanem páratlan prím, akkor kapjuk: 2p – 1 ≡ 1 (mod p)

Ez Fermat (kis) tételének 1. változata (biz. később, egyelőre fogadjuk el) 22



Pszeudoprímek

Eml. páratlan prímekre: 2p – 1 ≡ 1 (mod p), azaz a prímekre nagyon speciális egyenlőség teljesül!

És a többi számra nem…

Példák (Fermat-teszt): 23 – 1 = 4 ≡ 1 (mod 3), 24 – 1 = 8 ≡ 0 (mod 4), 25 – 1 = 16 ≡ 1 (mod 5), 26 – 1 = 32 ≡ 2 (mod 6), 28 – 1 = 128 ≡ 0 (mod 8), 214 – 1 = 8192 ≡ 2 (mod 14)

Remény: Van egy igen jó eszközünk, amellyel megkülönböztethetjük a prímeket az összetett számoktól!

Feladat: Próbáljuk ki több más (kisebb) számra is!

A hatványozás számítógéppel nagyon gyorsan elvégezhető Sajnos vannak azonban olyan összetett számok, amelyek úgy viselkednek, mint a prímek: 2341 – 1 ≡ 1 (mod 341), ugyanakkor 341 = 11⋅31

Definíció: Ha n páratlan összetett szám, és ugyanakkor 2n – 1 ≡ 1 (mod n), akkor n-et pszeudoprímnek nevezzük Szerencsére a pszeudoprímek ritkák, így a Fermat-teszt a gyakorlatban elég magas megbízhatóságot nyújt

1000-ig csak három pszeudoprím van: 341, 561, 645 1000000-ig pedig 245 (a prímek száma 78498) 23



Pszeudoprímek

Fermat azt is észrevette, hogy nemcsak 2 lehet alap (Tétel, vált.): Ha p olyan prím, amire p§b, akkor: bp – 1 ≡ 1 (mod p) Hasonlóan (def.): Ha n ptlan összetett szám, amire lnko(n, b) = 1, és bn – 1 ≡ 1 (mod n), akkor n-et b-alapú pszeudoprímnek nevezzük Így erősíthetjük az előző tesztet: Ha pl. n átmegy a 2 alapú teszten, akkor megnézzük 3, 5, … alappal is

A 341 pl. így már „lebukik”

Sajnos vannak azonban olyan „durván pszeudoprím” összetett számok is, amelyek minden tesztet becsapnak, ha az alap relatív prím

Ezeket Carmichael-féle számoknak nevezzük A legkisebb az 561 = 3 ⋅ 11 ⋅ 17

Feladat: Próbáljuk ki, hogy az 561 átmegy a 2, 5, 7, 13 alapú teszteken!

A Carmichael-számok nagyon (extrém) ritkák

*Knuth: a Carmichael-számok mindig legalább 3 kül. prím szorzatából állnak (azaz -ig biztosan találunk osztót)

Persze nyilván a 3, 11 és 17 alapú teszten nem 25 milliárdig csak 2163 van belőlük 3

n

24



Pszeudoprímek Feladatok Írjunk programot a (2, 3, … alapú) pszeudoprímek meghatározására megadott határig! Keressünk a Fermat-teszt segítségével 20, 50, 100 és 200 jegyű valószínű prímeket! Írjunk programot a Carmichael-számok meghatározására megadott határig! Készítsünk statisztikákat:

Mennyi a pszeudoprímek aránya a prímekhez viszonyítva adott határig? Mennyi a Carmichaelszámok aránya a prímekhez és a pszeudoprímekhez viszonyítva adott határig?

Keressünk minél több 3⋅p⋅q és 5⋅p⋅q alakú Carmichael-számot! *Keressünk olyan (nem kicsi) Carmichael-számokat, amelyekre a próbaosztásos algoritmus nem tud könnyen osztót találni (nincs kicsi prímosztójuk)!

25



Euler tétele

Definíció (Euler-féle φ függvény): Jelölje φ(n) az n-hez relatív prím pozitív egészek számát n-ig

Tétel: Legyenek n és b pozitív, relatív prím egészek. Ekkor bφ(n) ≡ 1 (mod n).

Például: φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2 Ha n prím, akkor φ(n) = n – 1, azaz a kis Fermat tételt kapjuk Példa: 2φ(15) = 28 = 256 ≡ 1 (mod 15)

Bizonyítás: Legyen t = φ(n) és legyenek a1, a2, …, at azok az n-nél kisebb (különböző) poz. egészek, amelyek rel. prímek n-hez. A b ⋅ a1, b ⋅ a2, …, b ⋅ at mod n maradékokat jelöljük r1, r2, …, rt-vel. (Itt b ⋅ ai ≡ ri (mod n).) Ha i és j különböző, akkor ri és rj is különböző. (Ha nem így lenne, akkor b ⋅ ai ≡ b ⋅ aj (mod n)-ből lnko(b, n) = 1 miatt következne ai ≡ aj (mod n), de ez nem lehet.) Az is igaz, hogy lnko(ri, n) = 1, mert valódi osztójuk ai-t is osztaná (ez szintén nem lehet). Így r1, r2, …, rt pontosan φ(n) darab 0 és n közötti egész, amelyek rel. prímek n-hez. Eszerint ezek pontosan ugyanazok, mint a1, a2, …, at, csak esetleg más sorrendben. Így r1 ⋅ r2 ⋅ … ⋅ rt ≡ b ⋅ a1 ⋅ b ⋅ a2 ⋅ … ⋅ b ⋅ at (mod n) ≡ b ⋅ r1 ⋅ b ⋅ r2 ⋅ … ⋅ b ⋅ rt (mod n) ≡ bt ⋅ r1 ⋅ r2 ⋅ … ⋅ rt (mod n). Osztással: 1 ≡ bφ(n) (mod n).

Alkalmazás: RSA titkosítás 26



Fermat észrevétele, feladatok

Igazolások, amiket nem tanulunk (lásd Bressoud)

Ez alapján ügyes teszt adódik a Mersenne-számokra (Eml.: Ha q | M(p), akkor q mod p = 1 is teljesül) Példa: M(19) = 524 287, négyzetgyöke 724,07… Eddig kell nézni azon q prímeket, amelyekre q ≡ 1 (mod 19) Ezek: 191, 229, 419, 571, 647 Ezek egyike sem osztja M(19)-et, ezért M(19) prím Feladatok

A páros tökéletes számok utolsó jegye mindig 6 vagy 8 Fermat eredeti észrevétele

Nézzük meg ugyanezt M(17)-re és M(23)-ra! Próbáljunk egy „ismeretlen” nagyobb Mersenne-számot is megvizsgálni!

Feladatok

Határozzuk meg Euler-féle φ függvény értékeit sok n-re! Milyen mintát/szabályosságokat tapasztalunk? *Igaz, hogy φ(n) mindig páros, ha n > 2? (Bizonyítsuk) A biz.-hoz: Lemma 1.: Ha lnko(m, n) = 1, akkor φ(m ⋅ n) = φ(m) ⋅ φ(n) Lemma 2.: Ha p prím, akkor φ(pa) = pa – 1 ⋅ (p – 1) Tétel: Ha n = p1a1 ⋅ p2a2 ⋅ … ⋅ prar, akkor φ(n) = p1a1 – 1 ⋅ (p1 – 1) ⋅ p2a2 – 1 ⋅ (p2 – 1) ⋅ … ⋅ prar – 1 ⋅ (pr – 1) = = n ⋅ (1 – 1/p1) ⋅ (1 – 1/p2) ⋅ … ⋅ (1 – 1/pr) 27



Történeti áttekintés

Eratoszthenész

Kr. e. 3. században alkotó görög matematikus (Alexandria) Három nevezetes ókori probléma: a kör négyszögesítése, a szögharmadolás és a kockakettőzés (megoldások csak: Galois-elmélet, 1830-as évek) Elég pontosan kiszámította az egyenlítő hosszát!

Marin Mersenne (17. század eleje)

Prímlista: 2p – 1 prím, ha p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, a többi 257-nél kisebb értékre összetett (nem pontos! – első hiba: 1870 k., Lucas) Híres idézete (1644): „Ahhoz, hogy egy 15 vagy 20-jegyű számról eldöntsük, prím-e vagy sem, egy élet sem elég, akárhogy is használjuk minden tudásunkat.”

Fermat-prímek: 2 2 + 1 alakú prímek

Kapcsolat: szabályos sokszögek szerkeszthetősége (körosztás, nevezetes ókori probléma)

n

Fermat szerint minden n-re, de később kiderült, hogy nem (cáfolat: Euler, n = 5)

Ötszög: Hippaszosz (Kr. e. 5. sz.), ekkor ismert tehát 3 ⋅ 2n, 4 ⋅ 2n, 5 ⋅ 2n és ezek szorzatai is, tehát pl. a 15-szög Több évszázadon keresztül (csak): egyedi szerkesztések különböző sokszögekre Gauss (18. sz. vége): euklideszi szerkesztéssel a kör kerülete pontosan akkor osztható n egyenlő részre, ha n Fermat-féle prímszámok első hatványainak és a 2 hatványainak véges szorzata Megszerkeszthető tehát: 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20-szög (n = 20-ig) 28




Leonard Euler (18. század)

A kor matematikájának minden szeletében maradandót alkotott (trigonometria, analízis, differenciál és integrálszámítás, harmad- és negyedfokú egyenletek elmélete) Tiszteletére nevezték el az „e” számot

Mersenne-prímek

Az újkortól/a modern korszakban a legnagyobb ismert prímek szinte mindig Mersenne-prímek voltak

Napjainkban is így van: 2013. jan. 25-én találták meg a 48. ilyen prímet, ez egy 17.425.170 jegyű szám, értéke 257885161 – 1

Egy-két kivételt találunk, de azok is hasonló spec. alakú számok

Eml.: Ezeket a számokat a CA rendszerek tudják

Great internet Merssene prime search – GIMPS

29




30




Great internet Mersenne prime search

31



Ajánlott irodalom

David M. Bressoud: Factorization and Primality Testing, Springer, New York, 1989 Geddes, Czapor, Labahn: Algorithms for Computer Algebra (6th pr./ed.), Kluwer Acad. Press, Boston, 1999 Joachim Gathen, Jürgen Gerhard: Modern Computer Algebra (3rd ed.), Cambridge Univ. Press, 2013 Donald E. Knuth: A számítógép-programozás művészete 2. (2. kiadás), Műszaki Könyvkiadó, Budapest, 1994 Katona Gyula, Recski András, Szabó Csaba: A számítástudomány alapjai, Typotex Kiadó, Budapest, 2003 Sain Márton: Matematika-történeti ábécé, Tankönyvkiadó, Budapest, 1974 Maple User Manual, Maplesoft, 2013 Matlab Symbolic Math Toolbox User’s Guide, MathWorks, 2013 Fritz Reinhardt, Heinrich Soeder: dtv-Atlas zur Mathematik, Deutscher Taschenbuch Verlag, München, 1977 32

3. előadás Prímek, tökéletes számok, Fermat-teszt, pszeudoprímek

Recommend Documents