Eötvös Loránd Tudományegyetem Természettudományi Kar
A tökéletes számok és társaik BSc szakdolgozat
Írta:
Orthmayr Flóra
Matematika BSc, matematikai elemz® szakirány
Témavezet®:
Dr. Freud Róbert
, egyetemi docens
Algebra és Számelmélet Tanszék
Budapest, 2012
Tartalomjegyzék
1. Bevezetés 2. Az osztóösszeg-függvény 3. A tökéletesség keresése
2 3 7
3.1.
Az ókori görögök
. . . . . . . . . . . . . . . . . . . . . . . . .
3.2.
Mersenne és levelez®társai
. . . . . . . . . . . . . . . . . . . .
10
3.3.
A Mersenne-lista kés®bbi vizsgálata . . . . . . . . . . . . . . .
15
3.4.
A számítógépek kora
19
. . . . . . . . . . . . . . . . . . . . . . .
4. És társaik?
7
22
4.1.
Barátságos számok
. . . . . . . . . . . . . . . . . . . . . . . .
4.2.
Többszörösen tökéletes számok
4.3.
Szupertökéletes és kvázitökéletes számok
. . . . . . . . . . . .
26
4.4.
Érinthetetlen számok . . . . . . . . . . . . . . . . . . . . . . .
28
4.5.
Osztóösszeg-sorozatok
29
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
Irodalomjegyzék
22 24
31
1
1.
Bevezetés
Szakdolgozatom témája a tökéletes, barátságos és egyéb, osztóösszegükkel kapcsolatos tulajdonságaik miatt különleges számok jellegzetességei, és megismerésük több mint kétezer éves története mell®zve a misztikus kitér®ket a barátságos számok talizmánként való hasznosításáról, vagy a tökéletesség olyan alátámasztásait, mint hogy Isten hat nap alatt teremtette a világot, és a Hold huszonnyolc nap alatt kerüli meg a Földet. Bár többen is kijelentették, hogy a tökéletes számok kevés elméleti jelent®séggel bírnak [1], és csupán érdekesek anélkül, hogy hasznosak volnának [2], mégis számos nagy matematikus vizsgálta ®ket az ókortól napjainkig, és dolgozott ki új módszereket, máshol is hasznos tételeket munkája során. A dolgozatban párhuzamosan fejtettem ki a témakör matematikai és történeti részét, ott tárgyalva az egyes tulajdonságokat, ahol a felismerésük sorra került a történetben, amelyet különböz® magyar és angol nyelv¶ források alapján állítottam össze. El®ször a tökéletes, majd a barátságos számok megismerésének történetét követtem, aztán sorra vettem néhány társukat, a többszörösen tökéletes, szupertökéletes és kvázitökéletes számokat, valamint az osztóösszeg-sorozatokat, az érinthetetlen és a szociális számokat. Az állítások bizonyítását önállóan (vagy némi útmutatás alapján) készítettem el, egyetlen nehezebb tétel kivételével, amelyhez a tankönyvben szerepl® bizonyítást dolgoztam fel. Az osztóösszeg-sorozatok viselkedésének szemléltetésére készítettem egy számítógépes programot is, amely a dolgozat mellékletét képezi.
2
2.
Az osztóösszeg-függvény
Azok a számok, amelyekr®l a továbbiakban szó lesz, mind abból a szempontból különlegesek, hogy osztóik összege adott viszonyban áll magával a számmal vagy más számokkal, tehát de niálásukhoz és alapvet® tulajdonságaik megismeréséhez is ismernünk kell az osztók összegzését megkönnyít® szabályokat és az osztóösszeg-függvény néhány alapvet® tulajdonságát.
2.1. De níció. σ(n)
jelöli az
n
pozitív osztóinak összegét.
Egyes de nícióknál azonban érdemes inkább a valódi osztók összegét használni:
2.2. De níció. s(n)
jelöli az
n
pozitív osztóinak összegét az
(a továbbiakban ezeket valódi osztóknak nevezzük):
n
kivételével
s(n) = σ(n) − n.
σ(n)-t nevezzük osztóösszeg-függvénynek, de az s(n) külön
Alapvet®en a
megnevezése híján az osztóösszeg kifejezés szerepelhet a valódi osztók összegével kapcsolatban is (például az aliquot parts problems, aliquot sequences,
aliquot cycles kifejezések mint osztóösszeg-problémák, osztóösszeg-sorozatok, osztóösszeg-körök fordításában).
2.3. De níció.
Az
f
számelméleti függvény (pozitív egészeken értelmezett
komplex érték¶ függvény) multiplikatív, ha bármely
f (ab) = f (a)f (b) teljesül minden
2.4. Tétel. (a, b) = 1
a, b
A
f
teljesen multiplikatív, ha
osztóösszeg-függvény
σ(ab) = σ(a)σ(b)
Ha
1 = b0 , b1 , . . . , bm ,
a
esetén
f (ab) = f (a)f (b)
esetén.
σ(n)
esetén
Bizonyítás.
teljesül. Az
(a, b) = 1
osztóját megszorozzuk
b
ab
vagyis
bármely
teljesül.
összes osztója:
akkor
multiplikatív,
1 = a0 , a1 , . . . , an
és
b
összes osztója:
összes osztóját úgy kapjuk meg, hogy
minden osztójával:
a
minden
a0 b0 = 1, a0 b1 , . . . , an bm−1 , an bm .
Így megkaptuk az összes osztót, de vannak-e a listán ismétlések? Azt szeretnénk belátni, hogy ha
(a, b) = 1, akkor a listán ab minden osztója csak egyszer 3
ai = pα1 1 · · · pαr r
szerepel. Legyen a
b
szám egyik osztója, ahol a
fel, hogy
a
az
pk
és
szám egyik osztója és
qk
számok különböz® prímek. Tegyük
ai bj = pα1 1 · · · pαr r q1β1 · · · qsβs = ah bl ,
egy osztója. A
pk
lehet osztója
ahol
ah
számok egyike sem lehet osztója
ai -vel.
lenne egynél nagyobb közös osztója
ah -nak,
bl = bj
tehát
és
ab
összegének szorzataként kapunk) az
az
a
egy osztója és
bl -nek,
Ugyanígy a
ai = ah ,
különböz®ek, tehát összegük (amelyet az
bj = q1β1 · · · qsβs
qk
vagyis az
hiszen akkor
bl
a
b
b-nek
számok egyike sem
ai b j
szorzatok mind
ai számok összegének és a bi számok
összes osztójának összegével egyenl®.
2.5. Tétel.
Ha az
n
σ(n) =
Bizonyítás.
A
kanonikus alakja
n = pα1 1 · · · pαr r ,
akkor
r r Y Y pαi i +1 − 1 (1 + pi + p2i + · · · + pαi i ) = . p − 1 i i=1 i=1
σ(ab) = σ(a)σ(b)
esetén is ugyanígy igaz (σ(abc)
állítás nyilvánvalóan több tagú szorzat
= σ(a)σ(bc) = σ(a)(σ(b)σ(c))
stb.), ha a
tényez®k páronként relatív prímek, tehát különböz® prímek hatványainak szorzatára mindenképp. Így
σ(n) =
αi osztója 1, pi , . . . , pi , vagyis az
Qr
i=1
σ(pαi i ).
A
pαi i
prímhatvány összes
1 kezd®tagú, pi hányadosú mértani sorozat els®
αi + 1 tagja, amelyeket a mértani sorozatokra vonatkozó képlettel összegezve α +1
pi i −1 -et kapjuk. pi −1
A továbbiakban néhány, a
σ(n)
lehetséges értékeire vonatkozó állítás kö-
vetkezik, amelyek hasznosak lehetnek a kés®bbi bizonyítások során.
2.6. Állítás. σ(n) Bizonyítás.Q
akkor és csak akkor páratlan, ha
Legyen
σ(n) =
r i=1 (1
n
+ pi + p2i + . . . + pαi i )
pi = 2 esetén bármilyen αi
kitev®re. Ha
vagy
n = t2 .
n = pα1 1 · · · pαr r .
kanonikus alakja
ha a szorzat minden tényez®je páratlan.
n = 2t2
akkor és csak akkor lesz páratlan,
1 + pi + p2i + . . . + pαi i
páratlan lesz
pi 6= 2, akkor az összeg minden tagja
páratlan, tehát páratlan sok tag esetén lesz az összeg is páratlan, így kell, hogy legyen
n
minden
pi 6= 2
αi
páros
prímtényez®jére. Egy szám négyzetszám,
4
ha minden prímtényez®je páros kitev®n szerepel. Tehát akkor lesz páratlan, ha
2.7. Állítás. σ(n) k
2 −1
prím (vagyis
n = 2t
2
vagy
n=t
2
.
σ(n)
akkor és csak
akkor és csak akkor kett®hatvány, ha
n
egy Mersenne-
alakú prímszám) vagy különböz® Mersenne-prímek szor-
zata.
Bizonyítás.
Nyilvánvaló, hogy
σ(n) kett®hatvány, ha n Mersenne-prím vagy
különböz® Mersenne-prímek szorzata, hiszen ekkor tényez®
k
(1 + (2 − 1))
Tegyük fel, hogy
és
képletében minden
alakú. Lássuk be, hogy egyébként nem az!
σ(n) kett®hatvány és (1+p+p2 +. . .+pα ) az egyik tényez®
a képletében, vagyis a Ekkor
σ(n)
2
p
prím
α
(1 + p + p + . . . + p )
α
kitev®vel szerepel
n
kanonikus alakjában.
is kett®hatvány, tehát biztosan páros, így
p 6= 2
α páratlan. Ekkor 2k = (1+p+p2 +. . .+pα ) = (1+p)(1+p2 +p4 +. . .+pα−1 ).
Mivel a bal oldal kett®hatvány, ezért a jobb oldalon is mindkét tényez®nek kett®hatványnak kell lennie, tehát Tegyük fel, hogy az
2
p
Mersenne-prím.
4
1 + p + p + . . . + pα−1
kett®hatvány páros sok szám
összege, ekkor a fentihez hasonlóan felbontható:
(1 + p2 + p4 + . . . + pα−1 ) = (1 + p2 )(1 + p4 + p8 + . . . + pα−3 ). Mivel a bal oldal kett®hatvány, ezért a jobb oldalon is mindkét tényez®nek kett®hatványnak kell lennie, tehát vel négyzetszám nem lehet
l = 1 ⇒ p = 1, zik, hogy az
tehát
p
4k − 1
2l = 1 + p2 ⇒ 2l − 1 = p2 .
Mi-
alakú, ez csak akkor teljesülhetne, ha
prímszámra ellentmondást kaptunk. Ebb®l követke-
1+p2 +p4 +. . .+pα−1 kett®hatvány páratlan sok szám összege, és
mivel páratlan sok páratlan szám összegeként mindenképp páratlan, csak lehet, vagyis
1
α = 1. Ezzel beláttuk, hogy n csak különböz® Mersenne-prímek
szorzata lehet.
2.8. Állítás.
A
σ(n) függvény értékkészletéb®l végtelen sok természetes szám
kimarad.
5
Bizonyítás.
Lássuk be, hogy a
szám kimarad! Tetsz®leges
N
σ(n)
értékkészletéb®l végtelen sok páratlan
számnál kisebb páratlan
kell a következ® feltételeknek:
n < N
és
n = s2
σ(n) esetén teljesülnie
vagy
n = 2t2 ,
ahol
t
és
s
pozitív egész szám.
2t2 < N ⇔ t2 < q
mint
N . 2
s2 < N ⇔ s <
N 2
⇔t<
√ N ⇒s
q
N 2
⇒t
lehetséges értékeinek száma kevesebb
√ lehetséges értékeinek száma kevesebb mint
A fenti kett® összege fels® korlátot ad az és ezáltal a az
N.
n lehetséges értékeinek számára,
σ(n) N -nél kisebb páratlan értékeinek számára is. Ezt az összeget
N -nél kisebb páratlan számok mennyiségéb®l kivonva a σ(n) függvény ér-
tékkészletéb®l kimaradó páratlan számok mennyiségére alsó korlátot kapunk:
q √ b N2 c − ( N + N2 ),
ez pedig tart a végtelenhez, ha
mivel a gyökös kifejezések elhanyagolhatóan kisebbek.
6
N
tart a végtelenhez,
3.
A tökéletesség keresése
3.1.
Az ókori görögök
A tökéletes számok de níciója és a páros tökéletes számok el®állítására vonatkozó tétel el®ször Euklidésznél szerepel. Az Elemek en belül önálló egységet alkot a három számelméleti témájú könyv (a hetedik, a nyolcadik és a kilencedik), amelyek nem építenek a korábbi könyvek eredményeire, és nem szükségesek a következ®khöz. Ennek az egységnek a koronája a de níciók és a tételek között is az utolsó a tökéletes számok elmélete. Az Elemek de níciója szerint (VII. 23.): Egy szám tökéletes, ha egyenl® az osztói összegével. [3] Az osztó itt (a VII. 3. de níció alapján) a számnál kisebb (pozitív) osztókat, vagyis a valódi osztókat jelenti, tehát:
3.1. De níció. szám az az
n,
Az
n pozitív egész tökéletes szám, ha σ(n) = 2n. (Tökéletes
amelyre
s(n) = n.)
A három számelméleti könyvön belül is külön egység a IX. könyv 21-34. tétele, az elemi állításokból felépül® páros és páratlan elmélete, mely a tökéletes számokra vonatkozó 36. tétellel együtt önálló rendszert alkot bár a 36. tételnek az Elemek ben szerepl® bizonyítása épít a másik két számelméleti könyv tételeire is, O. Becker megmutatta, hogy a bizonyításhoz elég csupán a 21-34. tételek használata is.[4] A tökéletes számok gondolatát egyébként is szokás a pithagoreusoknak tulajdonítani, és egyes feltételezések szerint az els®sorban már ismert eredményeket rendszerez® és pontosító Elemek ezen részét Euklidész különösebb változtatás nélkül emelte át egy korai pithagoreus tankönyvb®l. A páros tökéletes számok konstruálásáról szóló tétel Euklidész megfogalmazásában (IX. 36.): Ha az egységt®l kezdve kétszeres arányban képzünk egy mértani sorozatot, amíg a sorösszeg prím nem lesz, és az összeggel megszorozzuk az utolsó tagot, akkor a szorzat tökéletes szám lesz. [3] Modern változatban:
7
3.2. Tétel. p
2 −1
Egy n páros szám tökéletes, ha
n = 2p−1 (2p − 1)
alakú, ahol
prím.
Bizonyítás.
Ha
2p − 1
prím, akkor
n = 2p−1 (2p − 1)
osztóinak összege:
σ(n) = σ(2p−1 ) · (1 + 2p − 1) = (1 + 2 + . . . + 2p−1 ) · 2p = = (2p − 1) · 2p = 22p − 2p = 2 · 2p−1 (2p − 1) = 2n, tehát
n
tökéletes szám.
Nikomakhosz (i. sz. 100 körül) három csoportra osztotta a páros számokat: hiányos, tökéletes és b®velked® számokra. Hiányos egy szám, ha nagyobb, mint a nála kisebb pozitív osztóinak összege és b®velked®, ha kisebb.
3.3. De níció. ked®, ha
Az
n
pozitív egész hiányos szám, ha
σ(n) < 2n,
és b®vel-
σ(n) > 2n.
Nikomakhosz példákat is említett mindhárom csoportra, ® írta le az ókori görögök által is ismert els® négy tökéletes számot: 6, 28, 496, 8128. Ezek alapján megfogalmazta azt a (téves, de hosszú évszázadokon keresztül számos nagy matematikus által megismételt) állítást is, hogy a tökéletes számok felváltva végz®dnek 6-ra és 8-ra. Iamblikhosztól (i. sz. 300 körül) származik az akkor ismert négy tökéletes szám egy másik, Nikomakhosz által is megállapított tulajdonságának szintén téves, de hosszan igaznak vélt általánosítása, miszerint a tíz minden egymást követ® két hatványa közé pontosan egy tökéletes szám esik.
3.4. Állítás. Bizonyítás.
Minden prímhatvány hiányos szám. Lássuk be, hogy
tetsz®leges prímszám,
σ(pα ) =
α
σ(n) < 2n
minden
n = pα
esetén, ahol
p
tetsz®leges pozitív egész. Az alábbiak ekvivalensek:
pα+1 − 1 < 2pα ⇔ pα+1 − 1 < 2pα+1 − 2pα ⇔ −1 < pα+1 − 2pα . p−1
pα+1 − 2pα = (p − 2)pα
biztosan nagyobb egy negatív számnál, mivel
0 ≤ (p−2) és 0 < pα , tehát az utolsó egyenl®tlenség igaz, így a vele ekvivalens els® egyenl®tlenség is igaz, ezzel az állítást beláttuk.
8
3.5. Állítás. akkor
n
Ha egy
n páratlan számnak csak két különböz® prímosztója van,
hiányos szám.
Bizonyítás.
Legyenek
p, q
páratlan prímek,
n = pα q β .
Azt szeretnénk be-
látni, hogy
pα+1 − 1 q β+1 − 1 · < 2pα q β , p−1 q−1 Mivel
p− p1α
q
vagyis
1 pα
p−1
·
q−
1 qβ
< 2.
q−1
p p , tehát a fentiek helyett igazolhatjuk az er®sebb · q <2 p−1 p−1 q−1 p növelésével szigorúan csökken® sorozatot alkot. Mivel p és p−1
<
p−1
p
állítást.
p−
különböz® páratlan prímek, a legkisebb lehetséges értékeik
p p−1
·
q q−1
≤
3 2
3.6. Állítás. Bizonyítás. minden Ha osztói
k
a
·
5 4
=
15 8
< 2,
ezzel az állítást beláttuk.
3
és
5,
tehát
Egy b®velked® szám minden többszöröse is b®velked®. Lássuk be, hogy ha
σ(a) > 2a,
akkor
σ(ka) > 2ka
is teljesül
pozitív egész számra.
minden osztóját megszorozzuk
k -val,
akkor a kapott számok mind
ka-nak és mind különböz®ek, viszont (a triviális k = 1 eset kivételével)
biztosan hiányzik közülük az beláttuk.
1,
tehát:
σ(ka) > kσ(a) > 2ka,
ezzel az állítást
Ezen állítások alapján látható az is, hogy végtelen sok hiányos és végtelen sok b®velked® szám létezik, de ennél több is igaz:
3.7. Állítás.
Minden
k ≥ 3
egész számra végtelen sok olyan páratlan b®-
velked® szám és végtelen sok olyan páratlan hiányos szám létezik, amelynek pontosan
k
különböz® prímosztója van.
Bizonyítás.
1. Mivel egy b®velked® szám minden többszöröse b®velked®, az
állítás els® feléhez elég találnunk egyetlen olyan b®velked® számot, amelynek három különböz® prímosztója van:
33 · 5 · 7 = 945
ilyen, mert
σ(945) = 1920.
Ezt a számot (vagy bármely más olyan b®velked® számot, amelynek három különböz® prímosztója van) olyan prímek hatványaival szorozva, amelyek
9
már szerepelnek a felbontásában, végtelen sok b®velked® számot kapunk
k = 3-ra,
tetsz®leges
c
darab ezekt®l és egymástól különböz® prímmel (il-
letve hatványaikkal) szorozva pedig végtelen sok b®velked® számot kapunk
k = 3 + c-re. 2. Egy minden prímtényez®jét csak egyszeresen tartalmazó hiányos számra
2p1 p2 . . . pk > (p1 + 1)(p2 + 1) . . . (pk + 1). Ennek elégséges feltétele, ha a szám minden
pi
prímosztójára teljesül, hogy:
√ √ 1 k k . 2pi > pi + 1 ⇔ pi ( 2 − 1) > 1 ⇔ pi > √ k 2−1 Ez egy alsó korlátot ad a prímtényez®kre, tehát mindig lesz végtelen sok prím, amely megfelel ennek a feltételnek, és szorzata mindig hiányos szám lesz.
3.2.
k
darab különböz® ilyen prím
Mersenne és levelez®társai
Az 1630-as évekt®l kezdve élénkült fel a számok osztóival kapcsolatos problémák vizsgálata, a tökéletes, barátságos és többszörösen tökéletes számok keresése Fermat, Mersenne, Frénicle és Descartes levelezésében. Marin Mersenne francia minorita szerzetes a korabeli tudományos élet koordinátora és információs központja volt: csaknem az összes jelent®s nyugat-európai tudóssal aktívan levelezett, értesítette ®ket egymás eredményeir®l, kérdéseivel ígéretes problémák vizsgálatára biztatta ®ket. Mersenne el®ször 1636-ban írt Fermat-nak, aki már korábban is foglalkozott az osztókkal kapcsolatos számelméleti problémákkal, és nagyon nehéznek nyilvánította ®ket, ugyanakkor kijelentette, hogy van általános módszere a megoldásukra. Erre válaszul hívta ki Frénicle 1640-ben (Mersenne-en keresztül) egy 20 vagy 21 jegy¶ tökéletes szám megtalálására. Fermat a tökéletes számok keresésének módszereként három tételt közölt Mersenne-nel 1640 júniusában írt levelében: I. Ha
n
nem prím, akkor
2n − 1
nem prím.
10
II. Ha
n
III. Ha
prím, akkor
n
prím, és
p
2n − 2
2n-nek.
többszöröse
prímosztója
n
2 − 1-nek,
akkor
p−1
többszöröse
n-
nek [1], majd Frénicle-nek írta meg októberben ezek általánosítását mint az osztóösszeg-problémák alaptételét (la proposition fondamentale des parties ali-
quotes ): Bármely
p
1, a, a2
prímre és bármely
hogy osszon valamely
stb. mértani sorozatra
an −1-et, amelyre n osztja p−1-et; ekkor ha N
többszöröse a legkisebb ilyen
n-nek,
akkor
p
osztja
N
a − 1-et
p
kell,
bármely
is. [1]
Vizsgáljuk meg Fermat ezen állításait! I. triviális: ha
n = km
összetett szám, akkor
2km − 1-b®l (2k − 1) ≥ 3
kiemelhet®. II. a kis Fermat-tétel mekre
2n − 2
az
n
a = 2-re
(kiegészítve azzal, hogy páratlan
Ha
p
prím, akkor bármely
a
egész
ap ≡ a (mod p).
számra
Bizonyítás.
Bizonyítás
igaz bármilyen
k
prí-
prímen kívül még kett®vel is osztható):
3.8. Tétel. (A "kis" Fermat-tétel) p
n
p
szerinti teljes indukcióval:
prímre. Tegyük fel, hogy
p-vel
osztható
a
minden
0
1p = 1 ≡ 1 (mod p)
np ≡ n (mod p)
is teljesül. Mivel
esetén, ezért a binomiális tétel és az
indukciós feltevés alapján
p p−1 p (n + 1) = n + n +...+ n + 1 ≡ np + 1 ≡ n + 1 1 n−1 p
p
tehát ha az állítás igaz
n-re,
akkor
(n + 1)-re
is.
(mod p),
III. és általánosítása az alaptételben a kis Fermat-tétel másik alakját írja le, kiegészülve a legkisebb ilyen
n-re
vonatkozó állítással, ami a rend
fogalmának és egyik tulajdonságának felel meg. Modern megfogalmazásban:
3.9. De níció. ha
Az
n
a ≡ 1 (mod p),
rendjét
op (a)-val
3.10. Állítás. a
n pozitív egészt az a rendjének nevezzük modulo p (prím), de bármely
k
pozitív egészre
jelöljük.
N
≡ 1 (mod p) ⇔ op (a)|N . 11
ak 6≡ 1 (mod p).
Az
a
Frénicle kihívásában a valódi feladat annak eldöntése volt, hogy
237 − 1
prímszám, vagy sem: nem az, ahogy Fermat helyesen megállapította, mikor azt válaszolta, hogy nincs 20 vagy 21 jegy¶ tökéletes szám. Ugyanis III. szerint ha
p prímosztója 237 − 1-nek, akkor 37|p − 1, tehát 237 − 1 prímosztóit 37k + 1
alakban kell keresni, ahol
k
páros. A második ilyen, prímszámot adó
megkapjuk a szám felbontását:
k -ra
237 − 1 = 223 · 616318177.
Descartes 1638-ban azt írta Mersenne-nek, bizonyítani tudja, hogy minden páros tökéletes szám euklideszi típusú, de a bizonyítást nem közölte. (A tökéletes számokra vonatkozó tétel megfordításának els® ismert bizonyítása Eulert®l származik.)
3.11. Tétel. 2p − 1
ahol
Ha egy n páros szám tökéletes, akkor
alakú,
prím.
Bizonyítás. n szám és
n = 2p−1 (2p − 1)
k ≥ 1.
páros szám, tehát Ekkor
2k
és
t
n = 2k · t
alakban írható, ahol
t
páratlan
relatív prímek, tehát
σ(n) = σ(2k ) · σ(t) = (2k+1 − 1) · σ(t). Ugyanakkor Vonjunk ki
σ(n) = 2n, mivel n tökéletes szám, tehát 2k+1 ·t = (2k+1 −1)·σ(t).
t-t
az egyenlet mindkét oldalán!
(2k+1 − 1)t = (2k+1 − 1) · σ(t) − t ⇔ t = (2k+1 − 1)(σ(t) − t). Mivel rajta
(2k+1 − 1) ≥ 3, kívül
az
ezek szerint
egyetlen
(σ(t) − t) + t = σ(t)).
másik
Tehát
t-nek
(σ(t) − t) 6= t osztó
csak
σ(t)−t = 1, az egynél nagyobb osztó pedig 2 (2k+1 − 1)
prím.
maga
a
t
t-nek.
lehet
összesen két osztója van, vagyis
k+1
ahol
valódi osztója
k
Ekkor
(hiszen
t
prím és
k+1
−1 = t. Így n = 2 (2
−1),
Descartes ugyanebben a levelében azt is kijelentette, hogy ha létezik páratlan tökéletes szám (úgy vélte, létezik), az ahol
ps2
formájú kell, hogy legyen,
p prím. Frénicle 1657-ben ugyanezt a megállapítást azzal a kiegészítéssel
közölte, hogy a
p
prím
4k + 1
alakú kell, hogy legyen.
12
3.12. Állítás. 2
n = s p,
ahol
Ha létezik egy páratlan
p
4k + 1
egy
n
tökéletes szám, akkor szükségképpen
n ≡ 1 (mod 12)
alakú prím, és
vagy
n ≡ 9
(mod 36).
Bizonyítás. σ(n)
Ha
n
páratlan tökéletes szám, akkor minden osztója páratlan,
n
pedig mint a páratlan
kétszerese kett®vel osztható, de néggyel már
nem, vagyis a képletében pontosan egy páros tényez® szerepel, tehát Tegyük fel, hogy
. . . + pα )
p = 4k − 1. Ekkor a páros számú tagból álló (1 + p + p2 +
összeg tagjai felváltva
4k + 1
és
legyen néggyel osztható,
p
4k − 1
σ(n)
néggyel osztható. Mivel feltétel, hogy
4k + 1
képletében egyetlen tényez® se
4k − 1
nem lehet
alakúak, tehát az összegük
alakú, tehát
p
szükségképpen
alakú prímszám.
Tehát ha létezik páratlan tökéletes szám, az mindenképpen
p = 4k + 1
prím. Mivel páratlan négyzetszám,
(mod 4).
Vizsgáljuk meg
n-t
p 6= 3
prím, tehát ha
3 | n,
ha
n
n = s2 p.
n = s2 p, ahol
s2 ≡ 1 (mod 4),
tehát
n≡1
a hárommal oszthatóság szempontjából! akkor
3 | s 2 ⇒ 3 | s ⇒ 9 | s 2 ⇒ 9 | n.
Tehát
osztható hárommal, akkor osztható kilenccel is, tehát ebben az esetben
n ≡ 9 (mod 36). Ha hogy
3 - n ⇒ 3 - s,
akkor
s2 ≡ 1 (mod 3),
mivel négyzetszám. Tegyük fel,
p ≡ −1 (mod 3). Ekkor a páros számú tagból álló (1 + p + p2 + . . . + pα )
összeg tagjai felváltva
3k + 1
és
3k − 1
osztható. Ez ellentmond annak, hogy alakú, így
n ≡ 1 (mod 3),
alakúak, tehát az összegük hárommal
3 - n,
tehát
tehát ebben az esetben
p
szükségképpen
3k + 1
n ≡ 1 (mod 12).
A páratlan tökéletes számok létezésének kérdése egyébként máig megválaszolatlan: nem ismerünk egyet sem, de azt sem sikerült bizonyítani, hogy ne léteznének, csupán egyre szigorúbb feltételeket, amelyeknek meg kell felelniük, ha mégis léteznek. Egy páratlan tökéletes szám biztosan nagyobb, mint
10300 , legalább 75 prím szorzata, amelyek közül legalább 9 különböz®; a
legnagyobb prímosztója
108
fölötti és még a harmadik legnagyobb is nagyobb
100-nál.[5] Mersenne 1644-ben megjelent Cogitata Physico-Mathematica cím¶ köny-
13
vének el®szavában bizonyítás nélkül kijelentette, hogy
p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257;
2p − 1
más 257-nél kisebb
p
prím, ha
értékekre vi-
szont összetett. A tökéletes számok keresésének történetében már korábban is sokan közöltek megalapozatlan vagy hibásan alátámasztott listákat arról, hogy mely
p értékekre lesz a 2p − 1 szám prím: Mersenne Peter Bungus b® fél
évszázaddal korábbi munkájára hivatkozik, mikor megállapítja, hogy a Bungus által felsorolt 28 (valójában csak 24) tökéletes számból csak 8 tökéletes (p
= 2, 3, 5, 7, 13, 17, 19, 31),
(p
= 67, 127, 257)
és ezeken kívül csak 3 további tökéletes szám
ismert.
Peter Bungus táblázata, amely (nem els®ként és nem is utolsóként) azt a hibás feltételezést követte, hogy ratlan
n
2n−1 (2n − 1)
tökéletes szám lesz minden pá-
esetén, az els® huszonnégy ilyen számot tartalmazta. Ennél megala-
pozottabb listák is születtek már Mersenne el®tt: Cataldi még a tizenhetedik század elején kijelentette, hogy
2n −1 prím n = 2, 3, 5, 7, 13, 17, 19, 23, 29, 31, 37
esetén, és az összes lehetséges prímosztó végigpróbálásával állítását bizonyította is az
n ≤ 19
számokra, és ugyanígy (nem els®ként) azt is, hogy
211 − 1
összetett szám; azonban négy bizonyítás nélküli feltételezéséb®l három tévedés. Cataldi megállapította, hogy az ötödik és a hatodik tökéletes szám is hatra végz®dik, és bebizonyította, hogy ha nem is felváltva, de minden euklideszi tökéletes szám hatra vagy nyolcra végz®dik.
3.13. Állítás.
Minden páros tökéletes szám utolsó számjegye 6 vagy 8 (a
tízes számrendszerben).
Bizonyítás.
A páros tökéletes számok
n = 2p−1 (2p −1) alakúak, ahol (2p −1)
prím. Az utolsó számjegyekkel mint tízes maradékokkal számolhatunk. Az els® tényez® kett®hatvány, tehát nemnulla páros számra végz®dik, a második tényez® pedig eggyel kevesebb az els® kétszeresénél, tehát a lehetséges végz®dések a következ®képpen alakulnak:
2 · (2 · 2 − 1) ≡ 2 · 3 ≡ 6
(mod 10)
4 · (4 · 2 − 1) ≡ 4 · 7 ≡ 8
(mod 10)
14
6 · (6 · 2 − 1) ≡ 6 · 1 ≡ 6 (8 · 2 − 1) ≡ 5 (mod 10),
(mod 10)
de prímszám nem végz®dhet ötre, ahogy ket-
t®hatvány nem végz®dhet nullára, tehát a fenti három az összes lehetséges variáció páros tökéletes számok utolsó számjegyére.
Bár Mersenne csak négy elemmel b®vítette az akkori hiteles listát (a négyb®l kett® valóban prímet ad, a másik kett® azonban nem), de ezek közül három 15 számjegynél nagyobb, ráadásul ugyanilyen nagyságrend¶ számok sokaságáról állította határozottan (és az esetek többségében helyesen), hogy mind összetett pedig ® maga jelentette ki néhány mondattal kés®bb, hogy egy 15 vagy 20 jegy¶ szám prím voltának megállapítására a világ minden ideje sem volna elég!
3.3.
A Mersenne-lista kés®bbi vizsgálata
Ebben a részben két bizonyításhoz is szükségünk lesz a Legendre-szimbólum de níciójára és néhány tulajdonságára.
3.14. De níció.
Legyen
p > 2
prím és
(a, p) = 1.
Az
a
számot aszerint
nevezzük kvadratikus maradéknak vagy kvadratikus nemmaradéknak modulo
p,
hogy az
x2 ≡ a (mod p)
3.15. De níció. zük:
a
( ap ) Legendre-szimbólumot a következ®képpen értelmez-
1 a = −1 p
3.16. Tétel. p−1 2
Az
≡
( ap )
Legyen
kongruencia megoldható-e, vagy sem.
, ha
a
kvadratikus maradék modulo
, ha
a
kvadratikus nemmaradék modulo
p > 2
prím és
(a, p) = 1.
p, p.
Bármely ilyen
a
esetén
p > 2
és
q > 2
(mod p).
3.17. Tétel. (Kvadratikus reciprocitási tétel)
Legyen
két különböz® prím. Ekkor
p −( q ) q = ( p ) p q
, ha
p ≡ q ≡ −1
egyébként.
15
(mod 4);
3.18. Tétel.
p > 2 prím. 1 2 = −1 p
Legyen
, ha
p ≡ ±1
(mod 8);
, ha
p ≡ ±3
(mod 8).
Több mint száz évig senkinek sem sikerült bizonyítania vagy cáfolnia a Mersenne-féle lista bármely új állítását:
231 − 1
prím voltát Euler iga-
zolta 1772-ben, miután végigpróbálta az összes lehetséges (8 · 31 · n + 1 vagy
8·31·n+63 alakú) prímosztót 46339-ig (a legnagyobb páratlan számig, amely még kisebb, mint a vizsgált szám gyöke).
3.19. Állítás. q ≡ 1 (mod p)
Bizonyítás. Mivel
p
p
Legyenek és
és
q
páratlan
prímek.
A feltétel szerint
akkor
q|2p − 1, vagyis 2p ≡ 1 (mod q), tehát oq (2)|p.
prímszám, ez csak úgy teljesülhet, ha szóval
oq (2) = p
osztója
oq (2) = p.
A fentiekben láttuk, hogy A 3.16 tétel szerint éppen akkor, ha
2
p|q − 1.
q−1 2
Mivel
q
prím,
q − 1-nek:
ap = q − 1 ⇒ ap + 1 = q ⇒ q ≡ 1
1 = ( 2q )
q|Mp ,
q ≡ ±1 (mod 8).
2q−1 ≡ 1 (mod q),
p| q−1 . 2
Ha
Mivel
(mod p).
(p, 2) = 1,
≡ ( 2q ) (mod q).
ez azt is jelenti, hogy
A 3.18 tétel szerint pedig
q ≡ ±1 (mod 8).
Újabb évszázadnak kellett eltelnie a következ® bizonyítás és az els® hiba felfedezéséig: 1876-ban É. Lucas a részben az ® nevét visel® teszt korai változatát használva igazolta, hogy
2127 − 1
prím (mégpedig máig a legnagyobb,
amit számológépek használata nélkül találtak meg), de
267 − 1 összetett. Ké-
s®bb Mersenne további négy tévedésére derült fény: I. M. Pervusin 1883-ban kiderítette, hogy
261 − 1 viszont prím, majd R. E. Powers fedezett fel még két
hiányosságot a listán:
289 − 1
és
2107 − 1
szintén prímek. Végül 1922-ben M.
Kraitchik találta meg az utolsó hibát, mikor igazolta, hogy
2257 − 1 összetett
szám, de csak 1947-re (összesen háromszáz év elteltével) igazolódott teljesen, hogy ez az öt volt az összes hiba Mersenne listáján. Lucas módszerét D. H. Lehmer 1930 körül egyszer¶sítette a ma ismert teszt formájára:
16
3.20. Tétel. (LucasLehmer-teszt) és
ai+1 =
a2i
− 2,
Bizonyítás. a
és
b
i ≥ 1.
ha
Ekkor
Mp
Legyen
p>2
prím, továbbá
pontosan akkor prím, ha
A bizonyításban felhasználjuk, hogy az
a+
√
3b
a1 = 4
Mp |ap−1 . számok (ahol
egészek) a szokásos m¶veletekre gy¶r¶t alkotnak (ezt nevezzük
nak), amelyben a
H -beli
H-
oszthatóság, rendfogalom és kongruencia szabályai
ugyanúgy érvényesülnek, mint az egész számoknál. A bizonyításhoz szükségünk lesz a következ® lemmára: Tetsz®leges
q>3
prím esetén
(a +
√
√ 3b)q ≡ a + ( 3q ) 3b (mod q).
Ezt a következ®képpen igazolhatjuk: a binomiális tétel alapján
√ q q−1 √ q−1 q q−1 √ q q (a + 3b) = a + 3b + . . . + a a · 3 2 bq−1 + 3 2 3bq , 1 q−1 q ahol a számok mind oszthatók q -val, a kis Fermat-tétel (3.8) szerint k aq ≡ a (mod q) (mod q),
bq ≡ b (mod q),
és
végül a 3.16 tétel szerint
3
q−1 2
≡ ( 3q )
és ezeket beírva a fenti alakba valóban a lemma állítását kapjuk
vissza. 1. A feltétel átalakítása
√
√ k−1 + (2 − 3)2 (Ez teljes indukcióval könnyen iga√ 1 √ zolható: k = 1-re a1 = (2 + 3) + (2 − 3)1 = 4 igaz. Tegyük fel, hogy √ n−1 √ n−1 k = n-re an = (2 + 3)2 + (2 − 3)2 teljesül. Ennek felhasználásával √ √ n n n−1 k = n + 1-re an+1 = a2n − 2 = (2 + 3)2 + (2 − 3)2 + 2(4 − 3)2 − 2 = √ n √ n = (2 + 3)2 + (2 − 3)2 is igaznak bizonyul.) Eszerint ak = (2 +
ap−1 = (2 +
√
k−1
3)2
p−2
3)2
+ (2 −
√
p−2
3)2
= (2 −
√
3)2
p−2
((2 +
√
p−2
3)2·2
+ 1).
√ √ √ (2 + 3)(2 − 3) = 1 miatt a 2 ± 3 számok minden egész kitev®s √ 2p−2 hatványa, így (2 − 3) is egység H -ban, az alábbiak ekvivalensek: Mivel
Mp |(2 −
√
p−2
3)2
((2 +
√ 2·2p−2 √ p−1 3) + 1) ⇔ Mp |(2 + 3)2 + 1,
vagyis a tételben szerepl® feltétel: 2.
(2 +
√
p−1
3)2
Mp |ap−1 ⇔ (2 +
≡ −1 (mod Mp ) ⇒ Mp 17
√ 2p−1 3) ≡ −1 (mod Mp ).
prím igazolása
q √ 2p is teljesül, és ezt négyzetre emelve azt kapjuk, hogy (2 + 3) ≡ 1 (mod q). √ p Eszerint tehát oq (2+ 3)|2 , viszont a négyzetre emelés el®tti állapot alapján √ √ oq (2+ 3) nem osztja a 2p egyetlen másik osztóját sem, tehát oq (2+ 3) = 2p . Legyen
q > 3 az Mp
( 3q ) = 1.
Tegyük fel, hogy
(2 + Ebb®l
√
√
3)q ≡ (2 −
√
3)(2 +
√ 3) = 1
(mod q).
Ekkor
√ √ √ √ √ q+1 3) = (2 + 3)(2 + 3)q ≡ (2 + 3)(2 − 3) = 1
q + 1 ≥ 2p
p
következik, amit
p
2 − 1 ≤ q ≤ 2 − 1, 3.
3)(2 +
következik, ami viszont ellentmond a kiindulási feltételnek,
( 3q ) = −1.
Tehát
(2 +
√
Ekkor
q ≤ Mp = 2p − 1.
miszerint
Ebb®l
3)q−1 = (2 −
q − 1 ≥ 2p
egy prímosztója. Ekkor a fenti kongruencia modulo
Mp
prím
vagyis
⇒ (2 +
q ≤ Mp -vel
q = Mp ,
tehát
Mp
(mod q).
összevetve azt kapjuk, hogy
prím.
√ 2p−1 3) ≡ −1 (mod Mp )
igazolása
Ehhez a részhez szükségünk lesz a következ® két állításra:
Mp = 2p − 1,
tehát
p>2
esetén
2 tétel alapján következik, hogy ( ) Mp
Mp ≡ 1 (mod 3) ( M3p ) =
és
Mp ≡ −1 (mod 8),
ebb®l pedig a 3.18
= 1.
Mp ≡ −1 (mod 4)
miatt a 3.17 tétel szerint
−( M3p )
= −( 13 ) = −1. √ 2 √ Tekintsük most az (1+ 3) = 2(2+ 3) egyenl®séget, és emeljük mindkét √ p √ p−1 p−1 p−1 oldalát a (2 )-edik hatványra: (1 + 3)2 = 22 (2 + 3)2 . √ 2p √ √ p A bal oldalon (1 + 3) = (1 + 3)(1 + 3)2 −1 lett. A feltétel szerint
Mp = 2p − 1
prím, tehát
√ 3 √ 3 = 1 − 3 (mod Mp ), Mp √ √ ≡ (1 + 3)(1 − 3) = −2 (mod Mp ).
√ (1 + 3)Mp ≡ 1 + (1 +
√
3)2
p
A jobb oldal els® tényez®je
2p−1
2
2p−1 −1
=2·2
=2·2
2p −2 2
≡2· 18
2 Mp
=2
(mod Mp ).
A fentiek alapján az eredeti egyenletb®l adódik, és ezt a kongruenciát
p−1
2
nálásával éppen azt kapjuk, hogy
3.4.
−2 ≡ 2(2 + p
√
p−1
3)2
(mod Mp )
2 ≡ 1 (mod Mp ) √ 2p−1 (2 + 3) ≡ −1 (mod Mp ). -nel szorozva és
felhasz-
A számítógépek kora
Az óriásprímek (és els®sorban a tökéletes számokat is meghatározó Mersenneprímek, amelyek 1952 óta csak egyszer engedték át a legnagyobb címet más alakú prímeknek) keresése és találása új lendületet vett a számítógépes korszak kezdetével: 1952-ben Raphael Robinson egy éven belül öt új legnagyobb ismert Mersenne-prímet fedezett fel a SWAC (Standards Western Automatic Computer) számítógépre írt programjával, és azóta minden évtizedben legalább négy újat találtak: 1996 óta mindegyiket a GIMPS projekt résztvev®i. A GIMPS, vagyis a Nagy internetes Mersenne-prím keresés (Great Internet Mersenne Prime Search) elindítója George Woltman programozó, aki 1995 végén nekilátott a keresés akkori állapotát rögzít® különböz® adatbázisok egyesítésének, majd létrehozta a GIMPS weboldalát, ahol közzétette az így elkészült adatbázist és ingyenesen letölthet® számítógépes programját, amelynek használatával bárki csatlakozhat a közös kereséshez. A projekt elve a sok kicsi sokra megy: a különböz®, akár átlagos vagy gyenge személyi számítógépek együttese gyorsabb munkára képes a szuperszámítógépeknél. A kezdeti id®kben Woltman személyesen regisztrálta az e-mailben beküldött eredményeket, amelyek 1996 novemberében már több mint 700 tesztel®t®l érkeztek. Ez a korszak 1997 végén a PrimeNet szerver létrehozásával zárult le, Scott Kurowskinak köszönhet®en. A résztvev® számítógépeken a tesztelést végz® prime95 program az 1998-tól elérhet® 15-ös verziójától kezdve emberi beavatkozás nélkül kommunikál a PrimeNet központi adatbázisával, továbbítja az elért eredményeket és kapja meg a következ® feladatokat. Ezeket a szerver az adott számítógép teljesítményének megfelel®en osztja ki: a leggyorsabbak tesztelhetik a korábban még nem vizsgált Mersenne-számokat, a
19
gyengébbek az els® teszt alapján összetettnek nyilvánítottakat ellen®rzik újra, a leglassabb gépek pedig el®készít® munkával, próbafaktorizációkkal foglalkoznak. A GIMPS programja ugyanis számos ismert feltételt és algoritmust használ fel a feladat (a Mersenne-számok prím vagy összetett voltának megállapítása) minél hatékonyabb elvégzésére:
I.
El®ször elkészíti a lehetséges
p
prímek listáját, amelyekre
Mp = 2p − 1
prím volta vizsgálandó.
II.
A lehetséges
nálja a kis (<
q
prímosztók körét sz¶kíti a 3.19 állítás szerint, és elimi-
40000)
prímekkel osztható számokat az eratoszthenészi szita
(a feltételek alapján módosított) módszerével.
III.
A megmaradt
q
osztók közül a kisebbekre (a vizsgált számtól függ®
korlátig) a következ® algoritmus segítségével vizsgálja meg, hogy e
p
2 − 1-nek:
alakítsuk át
p-t
bináris alakra,
a
q
kezd®értéke legyen
osztója-
1,
majd
ismételjük a következ® lépéseket: 1.
a := a2 ;
2. vegyük el
p
ez 1, akkor 3.
a
bináris alakjának (balról) els® számjegyét, és amennyiben
a := 2a;
új értéke legyen az
ismételjük 1-2-3-at, amíg
p
a ≡ 2 (mod q),
tehát ha
a-nak q -val
való osztási maradéka;
p-nek
még maradt elvehet® számjegye. A végén
a = 1,
akkor
2p − 1 ≡ 0 (mod q),
vagyis
Mp
nem
prím.
IV.
Prímosztókat keres a John Pollard-féle
(p−1)-módszer segítségével. A
kis Fermat-tételen (3.8) alapuló módszer akkor tudja megtalálni egy
N
szám
q prímosztóját, ha q−1-nek csak kis prímosztói vannak (konkrétan mindegyik kisebb egy adott
B1
korlátnál). Mivel a Mersenne-számokhoz
alakú prímosztókat keresünk, a módszer kicsit módosítható:
k
prímosztóinak kell
és legyen
e2
B1 e3
B1-nél
q megtalálásához
alatt lenniük. Tegyük fel, hogy ez a feltétel teljesül,
E = 2 · 3 · · · b,
zatban minden
q = 2kp + 1
ahol
kisebb
r
b ≤ B1
a legnagyobb ilyen prím, és a szor-
prím olyan
20
er
kitev®n szerepel, hogy
rer
a
B1-hez. Ez az E szám (nagyon nagy valószín¶séggel: ha k √ c felbontásában nem szerepel B1-nél nagyobb prím c vagy nagyobb kitev®vel) legközelebb legyen
többszöröse
k -nak, mivel minden prímhatvány osztójának többszöröse, tehát
2kp|2Ep. A kis Fermat-tétel miatt 32Ep ≡ 1 (mod q), tehát 32Ep − 1 többszöröse
q -nak,
közös osztó
de
Mp -nek
Mp
általában nem, és ekkor a
(32Ep − 1, Mp )
legnagyobb
egy valódi osztóját fogja adni.
A módszer második lépcs®je akkor találja meg a ez az egy prímosztója van
B1
és
B2
F = 3
B1 ≤ z ≤ B2
5-tel
1-gyel
prímosztót, ha
k -nak
korlátok között, az összes többi
alatt. Az els® lépcs® eredménye legyen számot, amely
q
vagy
többi nyilván nem lehet prímosztó). Ezen
2Ep
B1
. Vegyünk minden olyan
kongruens modulo
6
(hiszen a
z kitev®kkel olyan (F z −1) számokat
kapunk, amelyek egyike az els® lépcs®ben használt elv alapján (valószín¶leg) többszöröse lesz és
Mp
V.
q -nak.
Ezeket modulo
legnagyobb közös osztója
Mp
Mp
összeszorozzuk, és a kapott szám
valódi osztója lesz.
Ha a fenti módszerek egyikével sem talált osztót
Mp -hez, akkor elvégzi
a Lucas-Lehmer tesztet (3.20). Ebben a nagyon nagy számok hatékony négyzetre emeléséhez a program gyors Fourier-transzformációt alkalmazó algoritmust használ, az ehhez szükséges komplex számsorozatok bináris ábrázolása azonban nem lesz teljesen pontos, így kerekítési hibák kerülhetnek a számításokba. Ezek többségét az algoritmus még a folyamat során kisz¶ri, de nem mindet, ezért szükséges az els® teszt igazolására a már említett ellen®rz® tesztelés (az összetettnek nyilvánított Mersenne-számok esetén) nagyjából két évvel az els® után, az els®dleges tesztelést végz®knél lassabb gépeken.[6]
21
4.
És társaik?
4.1.
Barátságos számok
Iamblikhosz személyesen Pithagorasznak tulajdonítja a barátságos számpárok felfedezését, aki a történet szerint a Mi egy barát? kérdésre azt válaszolta: Másik én.
4.1. De níció.
Az
σ(a) = σ(b) = a + b
4.2. Állítás.
a 6= b
pozitív egészek barátságos számpárt alkotnak, ha
(vagyis
s(a) = b
és
s(b) = a).
Egy barátságos számpár egyik tagja b®velked®, a másik pedig
hiányos szám.
Bizonyítás.
Legyen
a
és
b
barátságos számpár:
σ(a) = σ(b) = a + b.
Ekkor a következ®k ekvivalensek:
σ(a) > 2a ⇔ a + b > 2a ⇔ b > a ⇔ 2b > a + b ⇔ 2b > σ(b), tehát ha az egyik b®velked®, akkor a másik hiányos, és viszont, hiszen és
b
a
szerepe itt felcserélhet®. Ha egyik sem hiányos vagy b®velked®, akkor
mindkett® tökéletes, de ekkor
σ(a) = σ(b) = 2a = 2b,
vagyis
a = b,
hi-
szen a tökéletes számok önmagukkal barátságosak, tehát ez már nem egy barátságos számpár.
4.3. Állítás. Bizonyítás. egész), akkor
Barátságos számpár egyik tagja sem lehet kett®hatvány. Legyen
a
és
k+1
σ(a) = 2
b
egy barátságos számpár. Ha
− 1,
és
a + b = σ(a) = σ(b)
a = 2k
(ahol
k>1
alapján
b = 2k+1 − 1 − 2k = 2k − 1. Mivel
b és σ(b) is páratlan szám, ezért a 2.6 állítás szerint b = t2
páratlan szám.
2
t ≡ 1 (mod 4) jutottunk.
b = 2k − 1 ≡ −1 (mod 4),
alakú, ahol
t
míg egy páratlan szám négyzetére
teljesül, tehát a kett® nem lehet egyenl®, így ellentmondásra
22
Az ókori görögökt®l nem maradt ránk a barátságos számokkal kapcsolatos tétel, az általuk ismert egyetlen barátságos számpár a 220 és a 284 volt. Szábit ibn Kurra kilencedik századi arab tudós volt az els®, aki a barátságos számok (egy nem túl gyakori típusának) megtalálására vonatkozó szabályt közölt:
4.4. Tétel. pn−1 , pn
és
Legyen
qn
n > 1-re pn = 3 · 2n − 1, qn = 9 · 22n−1 − 1.
prímszámok, akkor
n
a = 2 · pn−1 · pn
és
n
b = 2 · qn
Ekkor ha
barátságos
számpárt alkotnak.
Bizonyítás.
Mivel
pn
és
pn−1
páratlan prímek,
σ(a) = σ(2n )σ(pn−1 )σ(pn ) =
= (2n+1 −1)(9·22n−1 ), és hasonlóan σ(b) = σ(2n )σ(qn ) = (2n+1 −1)(9·22n−1 ). Másfel®l
a + b = 2n (3 · 2n − 1)(3 · 2n−1 − 1) + 2n (9 · 22n−1 − 1) = = 9 · 23n−1 − 3 · 22n − 3 · 22n−1 + 2n + 9 · 23n−1 − 2n = = 2(9 · 23n−1 ) − 3(22n + 22n−1 ) = 9 · 23n − 3 · 22n−1 (2 + 1) = = 9 · 23n − 9(22n−1 ) = (2n+1 − 1)(9 · 22n−1 ), tehát
σ(a) = σ(b) = a + b,
vagyis
a
és
b
barátságos számpárt alkotnak.
Fermat és Descartes egymástól függetlenül újra felfedezték ugyanezt a szabályt, és ennek segítségével találta meg 1636-ban Fermat a letve 1638-ban Descartes a
17296 és 18416, il-
9363584 és 9437056 párt. Bár a barátságos számok
története kapcsán néhány könyv csak nem említi és van, amelyik konkrétan tagadja[2], hogy az arabok ismertek volna egynél több barátságos számpárt, más források szerint viszont a Fermat-féle párt Ibn al-Banna és Kamál al-Dín al-Fáriszi is megtalálta már a tizennegyedik században, a Descartes-féle párt pedig Muhammad Baqir Yazdi fedezte fel el®ször a tizenhatodik században.[7] Euler kés®bb általánosította a fenti tételt, és több módszert is kidolgozott barátságos számpárok keresésére abból a tényb®l kiindulva, hogy az ismert párok egy közös osztó és további, hozzá relatív prím különböz® prímek szorzataként álltak el®, megkülönböztetve az eseteket aszerint, hogy a közös osztón túl kett®-egy, kett®-kett®, kett®-több vagy több-több prím szerepelt-e a szorzatban. 1747-ben egy 30 párból álló listát tett közzé, amelyet kés®bb
23
64 elem¶re b®vített (ebb®l kett® hibás volt, egyet pedig félrenyomtattak). A módszeresen dolgozó matematikusok által mindaddig meg nem talált második legkisebb barátságos számpárt (1184 és
1210) a 16 éves Niccolò Paganini
fedezte fel 1866-ban. L. E. Dickson barátságos számhármasoknak nevezte az olyan számokat, amelyek közül bármely kett® valódi osztóinak az összege egyenl® a harmadik számmal, és megadott két különböz® számokból álló ilyen számhármast, valamint nyolc olyat, amelyben a három számból kett® azonos.
4.2.
Többszörösen tökéletes számok
4.5. De níció.
Azokat az
n
számokat, amelyekre
σ(n) = kn,
többszörösen
(k -szorosan) tökéletes számoknak nevezzük.
A
k -szorosan tökéletes számokat szokás Pk -val jelölni, P2
(1) számokat jelenti. Az akkor egyedüliként ismert P3
tehát a tökéletes
= 120-on
túl további
többszörösen tökéletes számok és rájuk vonatkozó szabályok megtalálását mint kihívást el®ször Marin Mersenne említette 1631-ben Descartes-nak írt levelében, de hét éven át nem kapott rá választ. Eközben Fermat megtalálta
(2) a másodikat (P3
(4) André Jumeau a harmadikat (P3 = 523776), (4) = 1476304896). az ® kihívására válaszul pedig Descartes a negyediket (P3
= 672),
Nem sokkal kés®bb Descartes közzétett hat
P4 -et
és egy
P5 -öt
is, majd 1638.
november 15-én megírta Mersenne-nek az általa megállapított szabályokat, amelyek a többszörösen tökéletes számok megtalálását segíthetik közülük a második és a harmadik alkalmazásával talált rá az említett hat akkor már ismert négy
4.6. Állítás. P I. Ha
n
II. Ha akkor
45n
III. Ha
13-mal,
egy
n
k
egy
n
akkor
tökéletes számokra teljesülnek a következ®k:
amely nem osztható
P3 ,
az
alapján:
k -szorosan
P3 ,
egy
P3
P4 -re
3-mal,
akkor
3n
egy
P4 .
amely osztható
3-mal,
de nem osztható
5-tel
amely osztható
3-mal,
de nem osztható
7-tel, 9-cel
és
9-cel,
P4 . egy
P3 ,
3 · 7 · 13n
egy
P4 . 24
és
IV. Ha
n
29 -nel,
osztható
kével sem, akkor
31n
és
de nem osztható a
16 · 43 · 127n
210 , 31, 43, 127
számok egyi-
aránya megegyezik az osztóik összegének
arányával. V. Ha
n
nem osztható
Bizonyítás. I. Mivel
és
3n
egy
n
σ(3n) = 4 · 3n,
ezért
akkor
n
egy
P3k .
3n
tehát
valóban
P4 .
osztható hárommal, de nem osztható kilenccel, ezért
szorzatként való felírásában szerepel az
σ(n) = 3n-t
P4k ,
A fenti szabályok mind nagyon egyszer¶en beláthatók:
(3, n) = 1,
II. Mivel
3-mal
megkapjuk
σ(45n) = σ( n3 )σ(3 · 45) = III. Ugyanígy ez a szám is egy
σ( n3 )-t, 3n 4
(1 + 3) = 4
tényez®, ezzel elosztva
amely már relatív prím a kilenchez, így
· 40 · 6 = 180n = 4 · 45n,
σ(3 · 7 · 13n) =
σ(n)
3n 4
tehát
45n
valóban
P4 .
· 13 · 8 · 14 = 1092n = 4 · (3 · 7 · 13n), tehát
P4 .
IV. Ugyanígy
σ(n) · (214 − 1) · 44 · 128 = − 1) σ(n) = · (3 · 43 · 127) · (22 · 11) · 27 = 3 · 11 · 31 σ(n) 1 = · 43 · 127 · 29 = · 43 · 127 · 16 · 32 · σ(n), 31 31
σ(16 · 43 · 127n) =
tehát
σ(31n) σ(16·43·127n)
V. Eszerint
=
(210
32·σ(n) 1 ·43·127·16·32·σ(n) 31
=
31 . 16·43·127
σ(3n) = σ(3)σ(n) = 4 · 3kn ⇒ σ(n) = 3kn,
vagyis
n
egy
P3k .
Mersenne a megtaláló neve nélkül közölte
(5)
P3
-öt, majd Fermat 1643-ban
az általa megtalált négyszeresen, ötszörösen és hatszorosan tökéletes számok mellett közölte
(6)
P3
-ot is, ezzel megtalálta az utolsó háromszorosan tökéletes
számot. Jelenleg összesen 5303 többszörösen tökéletes számot ismerünk (az eggyel mint egyedüli és valószín¶leg
P1 -gyel
2 6= k < 7-re
és a
47
tökéletes számmal együtt)
már minden
Pk -t
megtaláltak. Az 1 kivételével
nem ismerünk páratlan többszörösen tökéletes számot.[8]
25
k = 11-ig,
4.3.
Szupertökéletes és kvázitökéletes számok
4.7. De níció.
n
Az
pozitív
egészt
szupertökéletesnek
nevezzük,
ha
σ(σ(n)) = 2n.
4.8. Állítás. n = 2p−1
n
Egy
alakú, ahol
páros szám akkor és csak akkor szupertökéletes, ha
2p − 1
prím. (Tehát a páros szupertökéletes számok
is ugyanannyian vannak, mint a Mersenne-prímek.)
Bizonyítás.
1. Egyértelm¶en látszik, hogy minden ilyen
n = 2p−1 ⇒ σ(n) = 2p − 1,
ami
a
feltétel
n
szupertökéletes:
szerint
prím,
tehát
σ(2p − 1) = 2p = 2 · 2p−1 ⇒ σ(σ(2p−1 )) = 2 · 2p−1 . n = 2k t
2. Legyen
pozitív egész. Ekkor
szupertökéletes szám, ahol
σ(n) = (2k+1 − 1)σ(t),
σ(σ(n)) = σ((2k+1 − 1)σ(t)) = 2k+1 t. (2
k+1
− 1) 6= σ(t),
t
páratlan szám és
n
és mivel
Összegezzük
k
szupertökéletes,
σ(n)
ismert osztóit!
mivel ellenkez® esetben a szorzatuk egy páratlan szám
négyzete, ennek osztóösszege pedig szintén páratlan szám lenne. Tegyük fel, hogy
σ(t) > 1.
Ekkor
σ(σ(n)) ≥ 1 + (2k+1 − 1) + σ(t) + (2k+1 − 1)σ(t) ≥ ≥ 2k+1 + (t + 1) + (2k+1 t + 2k+1 − t − 1) = 2k+1 t + 2k+2 > 2k+1 t, vagyis ellentmondásra jutottunk. Ebb®l következik, hogy teljesül, tehát
n = 2k .
Ekkor
σ(2k+1 − 1) = 2k+1 ,
vagyis
σ(t) = 1 ⇒ t = 1
2k+1 − 1
prímszám.
4.9. Állítás. Bizonyítás. zetszám, ha páratlan
Egy páratlan szupertökéletes szám szükségképpen négyzetszám.
A 2.6 állítás szerint egy páratlan
n
akkor és csak akkor négy-
σ(n) páratlan. Az állítás igazolásához tehát elég belátnunk, hogy
n-re σ(σ(n)) = 2n
csak akkor teljesül, ha
gyük fel, hogy nem az, vagyis pertökéletes, ezért
σ(n) = 2k t,
ahol
k
σ(n)
páratlan. Most te-
pozitív egész. Mivel
σ(σ(n)) = σ(2k t) = (2k+1 − 1)σ(t) = 2n.
szu-
Az utolsó egyen-
l®ség mindkét oldalát elosztjuk kett®vel, felhasználva, hogy mivel
26
n
2k+1 − 1
páratlan, a jobb oldal viszont páros, ezért Így azt kapjuk, hogy
2k+1 − 1 ≥ 3,
így
k+1
(2
− 1)z = n.
(2k+1 − 1)
és
z
σ(t) = 2z
hiszen
k
2 σ(t) > 2 t
minden
z
pozitív egész).
Mivel feltettük, hogy
egyaránt valódi osztója
(2k+1 − 1)z + z = 2k+1 z = 2k σ(t) ≤ σ(n) = 2k t, k
(ahol
t > 1-re,
tehát a
k>0
k > 0,
ezért
n-nek,
tehát
ez pedig ellentmondás, kiinduló feltevés hamis,
ezzel az állítást beláttuk.
Nem tudjuk, létezik-e egyáltalán páratlan szupertökéletes szám.
4.10. De níció.
Az
n pozitív egészt kvázitökéletesnek nevezzük, ha egyenl® σ(n) = 2n + 1.
a nem triviális osztóinak összegével, vagyis
Nem tudjuk, hogy létezik-e ilyen tulajdonságú legalább hét különböz® prímosztója van, és
4.11. Állítás.
n
szám, de ha igen, akkor
n > 1035 .
Ha létezik kvázitökéletes szám, az szükségképpen egy páratlan
szám négyzete.
Bizonyítás.
A 2.6 állítás szerint
tehát azt kell belátnunk, hogy ha tesség alapján
σ(n)
csak
n = 2α t2
esetén lehet páratlan,
σ(n) = 2n + 1, akkor α = 0. A kvázitökéle-
σ(2α t2 ) = σ(t2 )(2α+1 −1) = 2α+1 t2 +1 = 2α+1 t2 −t2 +(t2 +1), ez
pedig átrendezés után ekvivalens azzal, hogy
(σ(t2 )−t2 )(2α+1 −1) = t2 +1. Ha
α = 0, akkor 2α+1 −1 = 1, egyébként 2α+1 −1 ≡ −1 (mod 4). Tegyük fel, hogy p = 4k − 1
prímosztója
tétel (3.8) miatt
t2 + 1-nek,
tp−1 ≡ 1 (mod p),
(mod p). Mivel p = 4k − 1, ezért ekb®l
vagyis
p−1 2
t2 ≡ −1 (mod p).
ugyanakkor
tp−1 = (t2 )
A kis Fermatp−1 2
≡ (−1)
p−1 2
= 2k − 1 páratlan szám, tehát az el®z®-
1 ≡ −1 (mod p) következne, ami nem teljesülhet semmilyen p = 4k −1
számra. Emiatt
α 6= 0
t2 + 1-nek
egyáltalán nem lehet
4k − 1
esetben ellentmondásra jutottunk. Ezért
kvázitökéletes szám csak
2
n=t
alakú lehet, ahol
alakú osztója, vagyis
α = 0 t
kell legyen, tehát a
páratlan szám.
A fenti de nícióhoz hasonlóan kvázibarátságos (vagy eljegyzett) számpárnak nevezik a
σ(m) = σ(n) = m + n + 1
mint például a
48
és a
75.
tulajdonságú
m 6= n
számpárokat,
Minden ismert kvázibarátságos számpár tagjai
ellenkez® paritásúak.
27
4.4.
Érinthetetlen számok
4.12. De níció.
Azokat az
n számokat, amelyekre az s(x) = n függvénynek
nincs megoldása, érinthetetlennek (untouchable ) nevezzük. Erd®s Pál bebizonyította, hogy végtelen sok érinthetetlen szám van, vagyis a
σ(x)-hez
hasonlóan (ld. 2.8 állítás) az
s(x)
értékkészletéb®l is végtelen sok
szám kimarad. Az
5
az egyetlen olyan érinthetetlennek ismert szám, amely páratlan. Hogy az
5
Az els® tíz érinthetetlen szám:
2, 5, 52, 88, 96, 120, 124, 146, 162, 178.
érinthetetlen szám, könnyen látható, hiszen nem bontható prímek és szorzataik összegére:
2
4=1+3=2+2
(ha
4
1
és különböz®
osztója lenne, akkor
is, ugyanaz az osztó kétszer viszont nem szerepelhet). Az a sejtés, hogy egyáltalán nem is létezik másik páratlan érinthetet-
len szám. Ez az állítás (hétnél nagyobb számokra) következne abból, ha feltesszük, hogy minden hatnál nagyobb páros szám el®áll két különböz® prímszám összegeként (ez a páros Goldbach-sejtésnek, miszerint minden páros szám el®áll két prímszám összegeként, egy er®sebb változata). Ekkor ugyanis bármely és
2k + 1 > 7
páratlan számra van olyan
s(pq) = 1 + p + q = 2k + 1,
vagyis
pq
p, q
prím, hogy
megoldása lesz az
p + q = 2k
s(x) = 2k + 1
függvénynek. Ezzel kizártuk a hétnél nagyobb páratlan számokat, a többit pedig egyszer¶en ellen®rizhetjük:
7 = 1+2+4 = s(8); 5-r®l láttuk, hogy értinthetetlen;
3 = 1 + 2 = s(4). n = 1
esetben nemcsak hogy létezik megoldása az
nek, de könnyen beláthatjuk, hogy csak megoldása: egyértelm¶, hogy
s(p) = 1
n = 1
minden
végtelen sok megoldás létezik; bármely
n > 1
p
s(x) = n
függvény-
esetén létezik végtelen sok prímszámra, tehát
n = 1-re
szám esetén viszont
(n − 1)
csak véges sok módon bontható a megoldást egyértelm¶en meghatározó nem triviális osztók összegére. Természetesen nemcsak a
n = 1-re
létezik több megoldás,
n = 8-ra
például
7 = 0+7 = 1+6 = 2+5 = 3+4 felbontási lehet®ségek közül pontosan kett®
ad prímeket (és egy sem különböz® prímek vagy prímhatványok összegét): a
28
7
és a
2 + 5,
így az
s(x) = 8
két megoldása
49
és
10.
Ez a tény teszi lehe-
t®vé a következ® pontban tárgyalt osztóösszeg-sorozatok közt a különböz®en kezd®d®, de azonos elemet tartalmazó (és így onnantól ugyanúgy folytatódó) sorozatok, így többek közt a nem tisztán periodikus osztóösszeg-sorozatok létezését.
4.5.
Osztóösszeg-sorozatok
4.13. De níció.
Az
a0 = n, ak = s(ak−1 ) (k = 1, 2, ...)
sorozatot az
n
osztóösszeg-sorozatának (aliquot sequence ) nevezzük.
Ez a sorozat háromféleképp viselkedhet:
1)
A sorozat véget ér, ha valamely
ak+2 = 1, ak+3 = 0-ra
2)
A sorozat
ak+t = ak .
t
ak -ra ak+1 = s(ak )
pedig az osztóösszeg-függvény már nem értelmezhet®.
k0 ,
hogy
Ekkor
t=1
szerint periodikus, ha van olyan
A sorozat tisztán periodikus, ha
kéletes szám,
prímszám, ekkor
k0 = 0.
∀k ≥ k0 : esetén
n
tö-
t = 2 esetén n és s(n) barátságos számpárt alkotnak. t > 2 ese-
tén a tisztán periodikus osztóösszeg-sorozatot
t-edrend¶
osztóösszeg-körnek
(aliquot cycle ), tagjait szociális számoknak (sociable numbers ) nevezzük. Az els® két ilyen
t = 28),
t>2
osztóösszeg-kört P. Poulet tette közzé 1918-ban (t
=5
és
majd ötven évvel kés®bb H. Cohen b®vítette a listát kilenc negyed-
rend¶ körrel. Ugyanekkor közölte a sejtést, hogy a negyedrend¶ osztóösszegkörök száma végtelen. A jelenleg ismert 217 kör közül 206 negyedrend¶ (a továbbiak:
3)
t = 5 : 1; t = 6 : 5; t = 8 : 3; t = 9 : 1; t = 28 : 1).[9]
A sorozat nem korlátos. Megoldatlan probléma, hogy létezik-e nem
korlátos osztóösszeg-sorozat: Catalan és Dickson sejtése szerint nincs, kés®bbi megállapítások arra utalnak, hogy valószín¶bb, hogy van. A legkisebb
n,
amelyhez még nem találták meg a sorozat végét (tehát akár végtelen is lehet), a
276
osztóösszeg-sorozatának már több mint 1700 eleme ismert, közülük
az utolsók 180 számjegy¶ek.[10]
29
Az osztóösszeg-sorozatok viselkedésének szemléltetésére készítettem egy egyszer¶ C++ programot, amelynek programkódja a dolgozat mellékletét képezi. A program a felhasználó által megadott
n
számot egyszer¶ osztással
bontja prímtényez®kre ([11] Prímfelbontás c. fejezetében leírt A algoritmus alapján), majd ennek alapján kiszámítja a
σ(n)
osztóösszeget, azonosítja a
többszörösen tökéletes számokat, megadja az osztóösszeg-sorozat els® néhány elemét, és amennyiben ennyi elem alapján lehetséges, beazonosítja a sorozat viselkedését is. Itt a következ® variációk lehetségesek:
0)
Az osztóösszeg-sorozatot nem sikerül a fenti kategóriák valamelyikébe
besorolni, ha a számítás valamilyen korlát miatt leáll, miel®tt a sorozatban ismétl®d® elem vagy prímszám következne. (A program által adott válasz ekkor This aliquot sequence does not terminate under
., illetve We
cannot determine the behaviour of this aliquot sequence from the rst elements.) Az elemszámra vonatkozó
k
korlátot a felhasználó határozhatja
meg a program futtatásának kezdetén. A vizsgálható számok nagyságára vonatkozó
1)
b
korlát els®sorban a forrásfájlból beolvasott prímlistától függ.
A program
1-ig folytatja a prímszámot tartalmazó osztóösszeg-sorozatok
kiírását. (This aliquot sequence terminates in 1 after elements.)
2)
Periodikus sorozatok elemeit az els® periódus végéig adja meg, meg-
különböztetve tökéletes ( is a perfect number.), barátságos ( and
<m> are members of an amicable pair.) és szociális számokat ( is a member of an aliquot cycle of elements.), valamint a nem tisztán periodikus sorozatokat. ( This aliquot sequence is periodic of period , but
not purely periodic.)
3)
A nem korlátos osztóösszeg-sorozatok, amennyiben léteznek, termé-
szetesen a 0. választ váltják ki.
30
Irodalomjegyzék
Hivatkozások [1] WEIL, André: Number Theory. An approach through history from Ham-
murapi to Legendre. BostonBaselStuttgart: Birkhäuser, 1984. [2] ORE, Oystein: Number Theory and its History. New YorkToronto London: McGraw-Hill Book Comp., 1948. [3] EUKLIDÉSZ: Elemek. Budapest: Gondolat, 1983. [4] WAERDEN, B. L. van der: Science Awakening. Groningen: P. Noordho, 1954. [5] Odd
Perfect
Number
Search.
http://oddperfect.org/against.html
(A
A letöltés
hozzáférés
módja:
ideje:
novem-
2012.
ber 30.) [6] Mathematics and Research Strategy GIMPS. A hozzáférés módja: http://www.mersenne.org/various/math.php (A letöltés ideje: 2012. november 20.) [7] COSTELLO, Patrick J.: New Amicable Pairs of Type (2,2) and Type (3,2). Mathematics of Computation, vol. 72 (2003), no. 241, pp. 489497. [8] The
Multiply
Perfect
Numbers
Page.
A
hozzáférés
módja:
http://wwwhomes.uni-bielefeld.de/achim/mpn.html (A letöltés ideje: 2012. november 12.) [9] A List of Aliquot Cycles of Length Greater Than 2 (by David Moews). A hozzáférés módja: http://djm.cc/sociable.txt (A letöltés ideje: 2012. november 7.) [10] Factordb adatbázis. A hozzáférés módja: http://factordb.com (A használat ideje: 2012. november 7.)
31
[11] KNUTH, Donald E.: A számítógép-programozás m¶vészete. 2. köt.: Sze-
minumerikus algoritmusok. Budapest: M¶szaki Könyvkiadó, 1994.
Felhasznált irodalom nyomtatott források [12] BEILER, Albert H.: Recreations in the Theory of Numbers. The Queen
of Mathematics Entertains. New York: Dover Pub., 1966. [13] COHEN, Henri: On Amicable and Sociable Numbers. Mathematics of
Computation, vol. 24 (1970), no. 110, pp. 423429. [14] DICKSON, L. E.: History of the Theory of Numbers. Vol. 1: Divisibility
and Primality. New York: Chelsea Pub. Comp., 1952. [15] EVES, Howard W.: An Introduction to the History of Mathematics. Philadelphia: Saunders College Pub., 1990. [16] FREUD Róbert, GYARMATI Edit: Számelmélet. Budapest: Nemzeti Tankönyvkiadó, 2006. [17] GUY, Richard K.: Unsolved Problems in Intuitive Mathematics. Vol. 1:
Unsolved Problems in Number Theory. New YorkBerlinParis: Springer Verlag, 1994. [18] HEALTH, Thomas, Sir: A History of Greek Mathematics. Vol. 1: From
Thales to Euclid. New York: Dover Pub., 1981. [19] KATZ, Victor J.: A History of Mathematics. An introduction. Reading: Addison-Wesley, 1998. [20] SHANKS, Daniel: Solved and Unsolved Problems in Number Theory. New York: Chelsea Pub. Comp., 1978. [21] SIERPISKI, Wacªaw: Elementary Theory of Numbers. Warszawa: Pa«stwowe Wydawnictwo Naukowe, 1964.
32
[22] SIMMONS, George F.: Calculus Gems. Brief Lives and Memorable Ma-
thematics. New YorkTorontoLondon: McGraw-Hill Book Comp., 1992.
Felhasznált irodalom internetes források [23] Chapter
XIX
Mathematica
by
of
the
Preface
Marin
Mersenne.
of
Cogitata
A
Physico-
hozzáférés
http://primes.utm.edu/mersenne/LukeMirror/lit/lit_069s.htm
módja: (A
letöltés ideje: 2012. október 23.) [24] How
GIMPS
Works
GIMPS.
A
hozzáférés
módja:
http://www.mersenne.org/various/works.php (A letöltés ideje: 2012. november 27.) [25] Mersenne Primes: History, Theorems and Lists. A hozzáférés módja: http://primes.utm.edu/mersenne/index.html (A letöltés ideje: 2012. október 23.) [26] P-1
Factorization
Method
Mersennewiki.
A
hozzáférés
módja:
http://mersennewiki.org/index.php/P-1 (A letöltés ideje: 2012. november 20.) [27] Perfect, Amicable and Sociable Numbers (by David Moews). A hozzáférés módja: http://djm.cc/amicable.html (A letöltés ideje: 2012. november 7.) [28] The Mersenne Newsletter, issue #13 (February 2, 1998) A hozzáférés módja: http://www.mersenne.org/newsletters/news13.txt (A letöltés ideje: 2012. október 23.)
33
