Osztószám-függvény

A Wikipédiából, a szabad lexikonból.

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

$\mathbb{N}^{+} \rightarrow \mathbb{N}; \ d(n) \ := \ | \{k \in \mathbb{N} \ | \ k|n \} | \ = \ \sum_{ d|n } d^{0}$

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, pl. σ₀(n) (ld. általánosítások), ν(n) (Ore, 1988 ^[2]), illetve τ(n) ^[3].

A d(n) függvény grafikonja (n=250-ig)

Tartalomjegyzék

1 Értékei kis számokra
2 Tulajdonságok
- 2.1 Algebrai-számelméleti tulajdonságok
- 2.2 Analitikus tulajdonságok
3 Számelméleti eredmények
4 Általánosítások
5 Hivatkozások

[szerkesztés] Értékei kis számokra

`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

^[4]

Különleges (elfajult) esetet 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.

[szerkesztés] Tulajdonságok

[szerkesztés] Algebrai-számelméleti tulajdonságok

[szerkesztés] Értékei prímhatványokra

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

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

Ennek speciális eseteként

$d(p) \ = \ d(p^{1}) \ = \ 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ó.

[szerkesztés] Kanonikus kiszámítási mód

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

d (n)

=

=

$\left( \alpha_{1}+1 \right) \left( \alpha_{2}+1 \right) ... \left( \alpha_{g}+1 \right)$

=

=

$\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ám ok 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]:

prímtényezők → ↓ kanonikus kitevő	p₁	p₂	...	p_n
-	0	0	...	0
-	1	1	...	1
-	...
-	α₁	α₂	...	α_g

1500 2²3¹5³	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 db.), 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 $m \ = \ p_{1}^{\beta_{1}} p_{2}^{\beta_{2}} ... p_{g}^{\beta_{g}} \mbox{, ahol} \ \forall i \in \left\{ 1,2,...,g \right\} : 0 \le \beta_{i} \le \alpha_{i}$ . Az m osztó megadása azzal ekvivalens, hogy minden oszlopból kiválasztunk egy cellát, azt, amelyben a &beta_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)...(α_g+1). QED.

[szerkesztés] Multiplikativitá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:

$\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.

[szerkesztés] Analitikus tulajdonságok

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

[szerkesztés] Korlátosság: alulról korlátos

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.

[szerkesztés] Értékkészlet

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

[szerkesztés] Értékei összege

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

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

ahol γ az Euler-konstans. Az, hogy itt a hibatag $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. A. Kolesnik 1982-ben megmutatta, hogy a hiba $O (x θ (log x) ε)$ minden $ε > 0$ -ra, ahol $θ = 35 / 108$ . Másrészt G. H. Hardy és A. E. Ingham megmutatta, hogy a hiba nem $o (x 1 / 4)$ .

[szerkesztés] Számelméleti eredmények

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

[szerkesztés] Általánosítások

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

$\sigma_{r}(n) \ := \ \sum_{ \begin{matrix}\mbox{ }_{d|n} \\ \mbox{ }_{1 \le d \le 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, pl. 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.

[szerkesztés] Hivatkozások

[szerkesztés] Lásd még

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

[szerkesztés] Jegyzetek

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

[szerkesztés] Irodalom

Gyarmati Edit – Turán Pál: Számelmélet. Egyetemi jegyzet. Nemzeti tankönyvkiadó, Bp., 1997.
Mathworld: Divisor function

[szerkesztés] Külső hivatkozások

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.

A lap eredeti címe "http://hu.wikipedia.org../../../o/s/z/Oszt%C3%B3sz%C3%A1m-f%C3%BCggv%C3%A9ny.html"

Kategóriák: Számelmélet | Függvények