Osztószám-függvény

Osztószámok kis számokra:^[4]

Különleges (elfajult) esetet képez d(0) = |N| = ℵ₀, 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.

Ha α>0 természetes szám és p∈N prímszám, akkor

${\displaystyle d\left(p^{\alpha }\right)\ =\ {\alpha +1}}$ .

Ennek speciális eseteként

${\displaystyle d(p)\ =\ d\left(p^{1}\right)\ =\ 1+1\ =\ 2}$ .

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=p⁰, p=p¹, p², …, p^α, ez pedig tényleg a p kitevőjénél eggyel több osztó.

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) ${\displaystyle n\ =\ p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}...p_{g}^{\alpha _{g}}\ =\ \prod _{i=1}^{g}p_{i}^{\alpha _{i}}}$ (α₁, …, α_g, g ∈N⁺ és p₁, …, p_g prímszámok)†; akkor érvényes:

${\displaystyle d(n)=}$

${\displaystyle =\left(\alpha _{1}+1\right)\left(\alpha _{2}+1\right)...\left(\alpha _{g}+1\right)=}$

${\displaystyle =\prod _{i=1}^{g}\left(\alpha _{i}+1\right)}$ .

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 = 2²3¹5³ esetére):^[5]

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ő:

1. 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 ${\displaystyle m\ =\ p_{1}^{\beta _{1}}p_{2}^{\beta _{2}}...p_{g}^{\beta _{g}}{\mbox{, ahol}}\ \forall i\in \left\{1,2,...,g\right\}:0\leq \beta _{i}\leq \alpha _{i}}$ . Az m osztó megadása azzal ekvivalens, hogy minden oszlopból kiválasztunk egy cellát, azt, amelyben a β_j kitevő áll.
2. 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)…(α_g+1). QED.

(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:

${\displaystyle \forall a,b\in \mathbb {Z} :\ \left(\ \ \left(a,b\right)=1\ \Rightarrow \ d(ab)=d(a)\cdot d(b)\ \right)}$

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.

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).

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.

1 = min(R(d(n)))

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.

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).

Lejeune Dirichlet 1838-ban igazolta a d(n) függvény értékeinek összegére, hogy

${\displaystyle \sum _{n=1}^{x}d(n)=x\log x+(2\gamma -1)x+O({\sqrt {x}})}$ .

ahol γ az Euler-Mascheroni-állandó. Az, hogy itt a hibatag ${\displaystyle O({\sqrt {x}})}$ -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 ${\displaystyle {\sqrt[{3}]{x}}\log x}$ -re csökkenthető. G. A. Kolesnik 1982-ben megmutatta, hogy a hiba ${\displaystyle O(x^{\theta }(\log x)^{\epsilon })}$ minden ${\displaystyle \epsilon >0}$ -ra, ahol ${\displaystyle \theta =35/108}$ . Másrészt G. H. Hardy és A. E. Ingham megmutatta, hogy a hiba nem ${\displaystyle o(x^{1/4})}$ .

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 ${\displaystyle d(n)<d(n-1)+h,d(n+1)+h}$ .^[6]

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):

${\displaystyle \sigma _{r}(n)\ :=\ \sum _{\begin{matrix}{d|n}\\{1\leq d\leq n}\end{matrix}}d^{\,r}}$

A d(n) = σ₀(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.

• 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

• 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?. Egyetemi oktatói előadásjegyzet (PDF); Pécs, 2008 április.
• Mathworld: Divisor function

• 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.