Osztószám-függvény
A számelmélet magyar szakirodalmában általában d(n)-nel jelölt osztószám-függvény a pozitív természetes számok halmazán értelmezett számelméleti függvény, melynek értéke az argumentum (pozitív) osztóinak száma (az osztók közé 1-et és magát a független változóként vett számot is beleértve). Képlete tehát
- .
Például a 6 osztói: 1,2,3,6; ezért 6-nak négy osztója van, s így d(6) = 4; míg a 12 osztói: 1, 2, 3, 4, 6, 12; ezért 12-nek hat darab osztója van, s így d(12) = 6.
A d(n) jelölést G. H. Hardy és E. M. Wright vezették be 1979-ben.[1] A külföldi szakirodalomban másféle jelölések is előfordulnak, például σ0(n) (szigma-null-jelölés ld. általánosítások), ν(n) (nü-jelölés, Ore, 1988[2]), illetve τ(n) (tau-jelölés).[3]
Értékei kis számokra
[szerkesztés]Osztószámok kis számokra:[4]
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
d(n) | 1 | 2 | 2 | 3 | 2 | 4 | 2 | 4 | 3 | 4 | 2 | 6 | 2 | 4 | 4 | 5 | 2 | 6 | 2 | 6 |
n | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
d(n) | 4 | 4 | 2 | 8 | 3 | 4 | 4 | 6 | 2 | 8 | 2 | 6 | 4 | 4 | 4 | 9 | 2 | 4 | 4 | 8 |
n | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
d(n) | 2 | 8 | 2 | 6 | 6 | 4 | 2 | 10 | 3 | 6 | 4 | 6 | 2 | 8 | 4 | 8 | 4 | 4 | 2 | 12 |
n | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
d(n) | 2 | 4 | 6 | 7 | 4 | 8 | 2 | 6 | 4 | 8 | 2 | 12 | 2 | 4 | 6 | 6 | 4 | 8 | 2 | 10 |
n | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
d(n) | 5 | 4 | 2 | 12 | 4 | 4 | 4 | 8 | 2 | 12 | 4 | 6 | 4 | 4 | 4 | 12 | 2 | 6 | 6 | 9 |
Különleges (elfajult) esetet képez d(0) = |N| = ℵ0, hiszen 0-nak minden természetes szám az osztója; ezért 0-ra a d(n) függvényt nem lehet a természetes számok körében maradva értelmezni. Érvényes viszont d(1) = 1, hiszen 1-nek és csakis az egynek van egyetlen osztója (önmaga). A prímszám definíciójából adódóan d(p) = 2 csakkor, ha p prím.
Tulajdonságok
[szerkesztés]Algebrai-számelméleti tulajdonságok
[szerkesztés]Értékei prímhatványokra
[szerkesztés]Ha α>0 természetes szám és p∈N prímszám, akkor
- .
Ennek speciális eseteként
- .
Amint fentebb mondtuk, a második egyenlőség a prímszám definíciójának is egyszerű következménye (hiszen egy p prímnek pontosan két osztója van). Az első egyenlőség a számelmélet alaptételéből következik, ugyanis pα osztói pontosan a pβ alakú számok, ahol 0≤β≤α és β∈N; vagyis 1=p0, p=p1, p2, …, pα, ez pedig tényleg a p kitevőjénél eggyel több osztó.
Kanonikus kiszámítási mód
[szerkesztés]A multiplikativitást és az előző tulajdonságot felhasználva, az argumentum kanonikus alakja ismeretében a d(n) függvényt kiszámító képlet adható. Eszerint ha az n>1 természetes szám prímtényezőkre bontása (kanonikus alakja) (α1, …, αg, g ∈N+ és p1, …, pg prímszámok)†; akkor érvényes:
- .
Tehát azt mondhatjuk, egy szám osztóinak száma épp a kanonikus felbontásában előforduló kitevők eggyel való megnövelésével kapott számok szorzata.
Ez a tétel a multiplikativitásra való hivatkozás nélkül, elemi úton is bizonyítható (szintén a számelmélet alaptételére mint központi alapelvre hivatkozva). Tekintsük az alábbi táblázatot (mellékeltünk egy példát az n = 1500 = 223153 esetére):[5]
prímtényezők → ↓ kanonikus kitevő |
p1 | p2 | … | pn |
– | 0 | 0 | … | 0 |
– | 1 | 1 | … | 1 |
– | … | |||
– | α1 | α2 | … | αg |
1500 223153 |
2 | 3 | 5 |
– | 0 | 0 | 0 |
– | 1 | 1 | 1 |
– | 2 | – | 2 |
– | – | – | 3 |
Legyen a táblázatnak annyi oszlopa, ahány (különböző) prímtényezője van n-nek (tehát g darab), a j-edik oszlop fejlécébe írjuk be a j-edik prímtényezőt (j 1 és g közé esik), majd minden oszlop celláiba írjuk rendre a 0,1,2,3,.. számokat egész addig, míg el nem érjük az illető oszlop fejlécében lévő prímtényezőnek az n kanonikus alakjában szereplő kitevőjét (tehát a j-edik oszlopnak αj db. számozott cellája lesz). Minden 1-nél nagyobb természetes számnak van prímfelbontása, és így minden 1-nél nagyobb természetes számhoz egy-egyértelműen tartozik egy ilyen táblázat. A bizonyítás a következő:
- Egy-egyértelműség a táblázatok és az n osztói között: A SzAT egy ismert következménye, hogy n egy m osztójának kanonikus alakja épp . Az m osztó megadása azzal ekvivalens, hogy minden oszlopból kiválasztunk egy cellát, azt, amelyben a βj kitevő áll.
- Az oszlopokban álló elemek számát össze kell szorozni: Minden oszlopban αj+1 db. elem áll (0-tól αj-ig), tehát a j-edik oszlopból αj+1-féleképp választhatunk kitevőt. A következő oszlopból hasonlóképp, és a választások egymástól függetlenek (akármelyik kitevőt választottuk az egyik oszlopban, egy másik oszlopban tetszőleges, ott szereplő kitevőt választva is az n egy osztóját kapjuk), így az összes választási lehetőség száma úgy adódik, hogy az oszloponkénti választási lehetőségek számát, azaz az αj+1-eket összeszorozzuk (ez szigorúbban j-re vonatkozó teljes indukcióval is bizonyítható). Vagyis megkaptuk, hogy az összes osztó száma (α1+1)(α2+1)…(αg+1). QED.
Multiplikativitás
[szerkesztés](Gyengén) multiplikatív, azaz relatív prím számok szorzatán felvett értéke a számokon felvett értékének szorzata. Formálisan:
Például:
- a=4, és σ(4) = 3;
- b=15, és d(15) = 4;
(lásd az Értékei kis számokra c. táblázatot)
A két szám szorzata: 4·15 = 60, valamint d(60) = |{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}| = 12, ami pontosan 3·4.
Ez a tulajdonság a SzAT egyszerű következménye. A SzAT egyik következménye szerint relatív prím számok szorzatának osztói a tényezők osztói szorzatai. Ha A jelöli az a osztói halmazát, B meg a b osztóiét, C meg az ab osztóiét, akkor d(ab) = |C|, de c mivel minden eleme egy-egyértelműen előáll egy A-beli meg egy B-beli elem szorzataként, azaz egy A-beli x és egy B beli y elem párosa, (x,y)∈A×B, egyértelműen megfelel egy C-beli elemnek, ezért ezek száma ugyanaz, mint A×B elemeinek száma, ami viszont épp |A|×|B| (két halmaz direkt szorzatának számossága a tényezők direkt szorzata); így |A|=d(a) és |B|=d(b) miatt d(ab) = |C| = |A×B| = |A|·|B| = d(a)d(b). QED.
Analitikus tulajdonságok
[szerkesztés]Az osztószám-függvény növekedése szabálytalan (nem monoton, nem csak az argumentum nagyságától függ, hanem annak multiplikatív szerkezetével (prímfelbontás) is erős kapcsolatban áll).
Korlátosság: alulról korlátos
[szerkesztés]A d(n) függvény triviálisan alulról korlátos, hiszen értéke bármely nemnegatív argumentumra nemnegatív, és értékkészletének van legkisebb eleme, az 1, melyet az n = 1 helyen vesz fel.
Mivel a minimum, ha létezik, mindig alsó korlát, mégpedig a legnagyobb,m így az osztószám függvény legnagyobb alsó korlátja, avagy alsó határa (infimuma) 1: inf(R(d(n))) = 1.
Ugyanakkor e függvény nem felülről korlátos, ld. lentebb.
Értékkészlet
[szerkesztés]Sőt, valójában minden 0-nál nagyobb értéket felvesz, méghozzá minden 1-nél nagyobb értéket végtelen sokszor (tetszőleges p prímre és α≥1 természetes számra d(pα-1) = α miatt).
Értékei összege
[szerkesztés]Lejeune Dirichlet 1838-ban igazolta a d(n) függvény értékeinek összegére, hogy
- .
ahol γ az Euler-Mascheroni-állandó. Az, hogy itt a hibatag -ről mennyire csökkenthető, a számelmélet egyik nevezetes problémája, a Dirichlet-féle osztóprobléma. G. Voronoj 1903-ban megmutatta, hogy a hibatag -re csökkenthető. G. A. Kolesnik 1982-ben megmutatta, hogy a hiba minden -ra, ahol . Másrészt G. H. Hardy és A. E. Ingham megmutatta, hogy a hiba nem .
Számelméleti eredmények
[szerkesztés]A d(n) függvény minden 1-nél nagyobb egész értéket végtelen sokszor felvesz (ld. fentebb). Igen elemi úton bizonyítható (ld. még osztópárok), hogy értéke csakis a négyzetszámokra páratlan. Rövid, a szimultán kongruenciarendszerekre vonatkozó tételeket és a Dirichlet-tételt használó bizonyítás adható arra, hogy grafikonja „tetszőlegesen mély völgyeket/magas csúcsokat” tartalmaz szomszédos argumentumokra is, azaz tetszőleges h∈R+ pozitív valós számhoz létezik olyan n>1 természetes szám, hogy igaz .[6]
Általánosítások
[szerkesztés]Leggyakrabban előforduló általánosítása az osztóhatványösszeg-függvény, mely a független változó osztói r-edik hatványainak összege (r valós szám):
A d(n) = σ0(n) függvény ennek speciális esete r=0-ra.
Lehetséges más konkrét algebrai struktúrákban, például kommutatív grupoidokban, félcsoportokban vagy – a legérdekesebb esetként – gyűrűkben is rákérdezni egy adott (x) elemet „osztó” más (y) elemek (az x=dy egyenlet megoldásai, ahol y és d ismeretlenek) számára.
Hivatkozások
[szerkesztés]Kapcsolódó szócikkek
[szerkesztés]- Tökéletes számok, hiányos számok, bővelkedő számok, multiperfekt számok, majdnem tökéletes számok, kvázitökéletes számok, osztóösszeg-függvény
Jegyzetek
[szerkesztés]- ↑ Hardy, G. H. and Wright, E. M.: An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Oxford University Press, pp. 354-355, 1979. ISBN 0-19-853171-0 (újabb kiadás). Ld. 239. old.
- ↑ Øystein Ore: Number Theory and Its History. New York: Dover, 1988. Ld. 86. old.
- ↑ Burton, D. M.: Elementary Number Theory, 4. kiad.; Boston, MA: Allyn and Bacon, 1989. Ld. 128. old.
- ↑ Forrás: N. J. A. Sloane [1]
- ↑ Az általános esetet illusztráló táblázat annyiban torz, hogy nem jeleníthető meg rajta az egyes kanonikus kitevők különbözősége – hogy konkrét n-re egy-egy oszlopnak különböző számú megszámozott cellái lehetnek.
- ↑ Ld. Gyarmati-Turán: Számelmélet; 6. f., T.6.13.; 187. old.
Irodalom
[szerkesztés]- Gyarmati Edit – Turán Pál: Számelmélet. Egyetemi jegyzet. Nemzeti tankönyvkiadó, Bp., 1997.
- Tóth László: Hány osztója van egy számnak? Archiválva 2015. november 6-i dátummal a Wayback Machine-ben. Egyetemi oktatói előadásjegyzet (PDF); Pécs, 2008 április.
- Mathworld: Divisor function
További információk
[szerkesztés]- N. J. A. Sloane: d(n) értékei ha 1≤n≤10 000
- On-line Encyclopedia of Integer Series bejegyzsé; OEIS A000005 katalógusszám.