´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) Sz´ amelm´ eleti fu enyek ¨ ggv´ • Sz´ amelm´ eleti fu enyek ´ ert´ ekeire vonatkoz´ o becsl´ esek ¨ ggv´ P P A τ (n) = es φ(n) (Euler-f¨ uggv´eny) nevezetes sz´ amelm´eleti f¨ uggv´enyek d|n 1, σ(n) = d|n d ´ ´ert´ekeit vizsg´alva l´athatjuk, hogy a felvett ´ert´ekek nagyon szab´ alytalanul” v´altoznak. A τ f¨ uggv´eny ” eset´en p´eld´aul τ (p) = 2 minden p pr´ımre ´es τ minden a ≥ 1 eg´esz ´ert´eket felvesz, m´egpedig v´egtelen sokszor, mert τ (pa−1 ) = a minden p pr´ımre. Ugyanakkor nyilv´ an 2 ≤ τ (n) ≤ n, enn´el jobb a k¨ ovetkez˝ o becsl´es: √ 1. Feladat. Igazoljuk, hogy 2 ≤ τ (n) ≤ 2 n minden n ≥ 2-re. K´erd´es, hogy τ (n) f¨ uggv´eny n-t˝ol f¨ ugg˝ oen milyen nagy” ´ert´ekeket vehet fel? ” A σ ´es φ f¨ uggv´enyekre σ(n) ≥ n + 1, φ(n) ≤ n − 1 minden n ≥ 2-re ´es az egyenl˝ os´egek akkor ´es csak akkor igazak, ha n pr´ım. K´erd´es, hogy σ(n) ´es φ(n) n-t˝ ol f¨ ugg˝ oen milyen nagy” illetve milyen ” kicsi” ´ert´ekeket vehet fel? ” 2. T´ etel. L´eteznek olyan C1 ´es C2 pozit´ıv ´alland´ ok, hogy minden n ≥ 2-re a) σ(n) < C1 n log n, b) φ(n) > C2 logn n . V´alaszthat´o C1 = 1 + 1/ log 2 ≈ 2, 442695, C2 = log 2/2 ≈ 0, 346573. Bizony´ıt´ as. Minden n ≥ 2 eset´en σ(n) =
X
d=
Xn d|n
d|n
d
=n
X1
≤n
d
d|n
n X 1 < n(1 + log n) ≤ C1 n log n, k k=1
ha C1 ≥ 1 + 1/ log n minden n ≥ 2-re, azaz ha C1 ≥ 1 + 1/ log 2 ´es r Y φ(n) Y 1 1 1 1 log 2 (1 − ) ≥ (1 − = )= ≥ ≥ , n p k+1 r+1 2r 2 log n k=1
p|n
ahol r az n k¨ ul¨onb¨oz˝o pr´ımoszt´oinak a sz´ama, ´es haszn´ aljuk, hogy n ≥ 2r , log n ≥ r log 2. 3. Megjegyz´ es. Az el˝obbiek alapj´an: σ(n) =0 n→∞ n1+ε lim
´es
φ(n) =∞ n→∞ n1−ε lim
minden ε > 0 eset´en. ´Igy az is igaz, hogy limn→∞ φ(n) = ∞. N´ezz¨ uk most a τ f¨ uggv´enyt. A limn→∞ τ (n) nem l´etezik, ugyanakkor igazolhat´ o, hogy 4. T´ etel. Minden ε > 0 eset´en lim
n→∞
τ (n) = 0. nε
Sok esetben a vizsg´alt f sz´amelm´eleti f¨ uggv´enyre vonatkoz´ o n
1X f (n) n k=1
sz´amtani k¨oz´epar´anyos j´ol k¨ozel´ıthet˝o elemi f¨ uggv´enyekkel. A τ f¨ uggv´enyre p´eld´ aul igaz a k¨ ovetkez˝ o: 5. T´ etel. i) L´etezik olyan C3 > 0 val´os sz´ am, hogy ¯ n ¯ ¯1 X ¯ ¯ ¯ τ (k) − log n¯ < C3 ¯ ¯n ¯ k=1
1
´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) minden n ≥ 2 eset´en (v´alaszthat´o C3 = 1), ii) n 1 X lim τ (k) = 1, n→∞ n log n
n
1X τ (k) ∼ log n. n
azaz
k=1
k=1
Bizony´ıt´ as. i) S(n) :=
n X
n X X
τ (k) =
k=1
1=
n/d n X X
1=
d=1 j=1
k=1 d|n
n h i X n d=1
d
,
mert r¨ogz´ıtett d eset´en k = jd, ahol 1 ≤ j ≤ n/d. Elhagyva az eg´eszr´eszt, ´ X1 1 1 X ³n S(n) > −1 = − 1 > log n − 1, n n d d
n
X1 1 S(n) ≤ < 1 + log n n d
´es
d=1
ahonnan
n
n
d=1
d=1
n
1X −1 < τ (k) − log n < 1. n k=1
ii) Azonnali i) alapj´an. 6. Megjegyz´ es. A felhaszn´alt
n X
τ (k) =
n · ¸ X n j=1
k=1
j
azonoss´ agnak egy m´as, ´erdekes levezet´ese a
k¨ ovetkez˝o. Tekints¨ uk az A = (aij ) n × n t´ıpus´ u m´ atrixot, ahol aij = 1, ha j | i ´es aij = 0, ha j - i. Pl. n = 6-ra az A m´atrix a k¨ovetkez˝o : 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 A= 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 1 Sz´amoljuk ¨ ossze, hogy h´any 1-es van a m´ atrixban! ama PnSorok szerint: az i-edik sorban annyi 1-es van, ah´anyszor j | i, azaz τ (i), ´ıgy az 1-esek sz´ τ (i). i=1 Oszlopok szerint: a j-edik oszlopban annyi 1-es van, ah´anyszor j | i, azaz ah´any t¨ obbsz¨ or¨ ose van j-nek ´es ez a sz´am [n/j], mert a t¨obbsz¨ or¨ os¨ ok ezek: Pn j, 2j, ..., kj, ahol kj ≤ n < (k + 1)j, innen k ≤ n/j < k + 1, azazP k = [n/j]. ´Igy az 1-esek sz´ a ma j=1 [n/j]. P K¨ovetkezik, hogy ni=1 τ (i) = nj=1 [n/j]. 7. Azt mondjuk, hogy az f f¨ uggv´eny ´atlag´ert´eke vagy k¨ oz´ep´ert´eke a g f¨ uggv´eny, ha n
n
k=1
k=1
1X 1X f (k) ∼ g(k), n n azaz lim
n→∞
n X
f (k)/
k=1
n X
g(k) = 1.
k=1
A τ (n) f¨ uggv´eny ´atlag´ert´eke az el˝oz˝o t´etel szerint log n. 2
´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) 8. Megjegyz´ es. Az (x, y) koordin´atarendszer els˝ o negyed´eben tekints¨ uk az xy = k egyenl˝ ooldal´ u hiperbol´at. Ezen annyi r´ a cspont van, ah´ a nyf´ e lek´ e ppen k = ab k´ e tt´ e nyez˝ o s szorzatk´ e nt ´ ırhat´ o , azaz P τ (k). ´Igy S(n) = nk=1 τ (k) egyenl˝o az xy = k ≤ n hiperbol´akon l´ev˝ o r´ acspontok sz´ am´ aval, azaz a tengelyek ´es az xy = n hiperbola k¨oz¨otti r´acspontok sz´ am´ aval. Igazolhat´o, hogy 9. T´ etel.
n 1 X π2 , σ(k) = n→∞ n2 12
n
azaz
lim
k=1
1 lim n→∞ n2
n X k=1
1X π2 n, σ(k) ∼ n 12 k=1 n
3 φ(k) = 2 , π
azaz
1X 3 φ(k) ∼ 2 n. n π k=1
10. Feladat. Igazoljuk, hogy minden n ≥ 1-re a) σ(n) + φ(n) ≥ 2n, b) Cn2 < σ(n)φ(n) ≤ n2 , alkalmas C > 0 ´ alland´ oval. 11. Feladat. Igazoljuk, hogy: a) limn→∞ σ(n!) n! = ∞, φ(n!) b) limn→∞ n! = 0. • A M¨ obius-fu eny (r´eszletesebben l´ asd Algebra ´es sz´amelm´elet II. jegyzet, 3.7. szakasz) ¨ ggv´ M¨obius-f¨ uggv´enynek nevezz¨ uk a 1, ha n = 1, µ(n) = 0, ha l´etezik p pr´ım, amelyre p2 | n, (−1)r , ha n = p1 p2 ...pr , pi 6= pj k´eplettel defini´ alt f¨ uggv´enyt. P´eld´aul, µ(30) = µ(2 · 3 · 5) = (−1)3 = −1, µ(12) = µ(22 · 3) = 0, µ(14) = µ(2 · 7) = (−1)2 = 1. Megjegyezz¨ uk, hogy |µ(n)| = (µ(n))2 = 1 akkor ´es csak akkor, ha n n´egyzetmentes, azaz n k¨ ul¨onb¨oz˝o pr´ımek szorzata. 12. T´ etel. i) µ multiplikat´ıv f¨ uggv´eny. ii) A M¨obius-f¨ uggv´eny ¨osszegz´esi f¨ uggv´enye X d|n
( µ(d) =
1, ha n = 1, 0, ha n > 1.
13. T´ etel. (M¨obius-f´ele megford´ıt´asi k´eplet) Ha f ´es g sz´ amelm´eleti f¨ uggv´enyek, akkor egyen´ert´ek˝ uek a k¨ovetkez˝ o ´ a ll´ ıt´ a sok: P 1) g(n) = Pd|n f (d) minden n ≥ 1 eset´en, 2) f (n) = d|n µ(d)g(n/d) minden n ≥ 1 eset´en. • Sz´ amelm´ eleti fu enyek konvol´ uci´ oszorz´ asa (r´eszletesebben l´ asd Algebra ´es sz´ amelm´elet ¨ ggv´ II. jegyzet, 3.8. szakasz) Az f ´es g f¨ uggv´enyek konvol´ uci´oszorzata (Dirichlet-szorzata) az f ∗ g f¨ uggv´eny, ahol X X (f ∗ g)(n) = f (d)g(n/d) = f (d)g(e), n ≥ 1, de=n
d|n
az ¨osszegz´es itt n pozit´ıv d oszt´oira vonatkozik, illetve mindazokra a (d, e) rendezett sz´amp´ arokra, amelyekre de = n. 3
´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) Legyen E(n) = n, U (n) = 1,
( δ(n) =
1, ha n = 1, 0, ha n > 1.
´Igy a kor´abbiakban vizsg´alt f¨ uggv´enyekre: σ = U ∗ E,
τ = U ∗ U,
µ ∗ U = δ,
φ = µ ∗ E.
Jel¨olje F a sz´amelm´eleti f¨ uggv´enyek halmaz´ at. 14. T´ etel. (A konvol´ uci´o tulajdons´agai) Ha f, g, h tetsz˝ oleges sz´ amelm´eleti f¨ uggv´enyek (f, g, h ∈ F), akkor 1) f ∗ g = g ∗ f (kommutativit´as), 2) (f ∗ g) ∗ h = f ∗ (g ∗ h) (asszociativit´ as), 3) f ∗ δ = f (δ egys´egelem), 4) f ∗ (g + h) = f ∗ g + f ∗ h (a konvol´ uci´ o disztribut´ıv az ¨ osszead´ asra n´ezve), 5) f ∗ g ≡ 0⇔f ≡ 0 vagy g ≡ 0, 6) adott f ∈ F eset´en akkor ´es csak akkor l´etezik g ∈ F u ´gy, hogy f ∗ g = δ, ha f (1) 6= 0, ´es ha l´etezik ilyen g, akkor az egy´ertelm˝ u, azaz (F, +, ∗) kommutat´ıv, egys´egelemes, z´erusoszt´ omentes gy˝ ur˝ u (integrit´ astartom´ any) ´es egy adott f ∈ F elemnek akkor ´es csak akkor l´etezik inverze, ha f (1) 6= 0. 15. Megjegyz´ es. (F, +, ·) kommutat´ıv, egys´egelemes gy˝ ur˝ u, de itt vannak z´erusoszt´ ok. A konvol´ uci´o val´odi f¨ uggv´eny-m˝ uvelet, (f ∗ g)(n) kisz´ am´ıt´ as´ ahoz nem elegend˝ o f (n) ´es g(n) ismerete. Legyen F1 = {f ∈ F : f (1) 6= 0} ´es legyen MF a nem azonosan nulla multiplikat´ıv f¨ uggv´enyek halmaza. Akkor 16. T´ etel. Az (F1 , ∗) strukt´ ura kommutat´ıv csoport ´es (MF, ∗) ennek r´eszcsoportja. 17. Megjegyz´ es. A µ ∗ U = δ ¨osszef¨ ugg´es alapj´ an k¨ ovetkezik, hogy a kiss´e furcsa” µ f¨ uggv´eny a ” sz´ep” U f¨ uggv´eny konvol´ uci´oinverze, ´es ennek alapj´an u ´j, ´atl´ athat´ obb bizony´ıt´ as adhat´ o a M¨ obius-f´ele ” megford´ıt´asi k´epletre: X f (d)⇔g = f ∗ U ⇔g ∗ µ = (f ∗ U ) ∗ µ g(n) = d|n
⇔g ∗ µ = f ∗ (U ∗ µ)⇔g ∗ µ = f ∗ δ⇔g ∗ µ = f ⇔f (n) =
X
µ(d)g(n/d).
d|n
• Tov´ abbi feladatok 18. Hat´arozzuk meg a τ (n), σ(n) ´es φ(n) ´ert´ekeket, ahol n = 12, n = 24, n = 120, illetve n = p2 q 3 , p 6= q pr´ımek. 19.. Legyenek f ´es g multiplikat´ıv f¨ uggv´enyek. Vizsg´ aljuk, hogy multiplikat´ıv-e az f g szorzatf¨ uggv´eny ´es az f + g ¨osszegf¨ uggv´eny. 20. Lehet-e pr´ımsz´am vagy pr´ımhatv´any t¨ ok´eletes sz´ am? 21. Igazoljuk, hogy n akkor ´es csak akkor t¨ ok´eletes sz´ am, ha n oszt´ oi reciprokainak az o ¨sszege 2. 22. Igazoljuk, hogy ha n p´aros t¨ok´eletes sz´ am, akkor n utols´ o sz´ amjegye (10-es sz´ amrendszerben) 6 vagy 8. 23. Igazoljuk, hogy minden m, n ≥ 1 eset´en τ (mn) ≤ τ (m)τ (n). Mikor ´all fenn az egyenl˝ os´eg? 24. Igazoljuk, hogy minden n ≥ 1-re φ(n2 ) = nφ(n).
4
´ th La ´ szlo ´ , Fejezetek az elemi sz´ Dr. To amelm´eletb˝ ol ´es az algebr´ ab´ ol (PTE TTK, 2010) 25. Igazoljuk, hogy minden n ≥ 1 eset´en φ(n) =
X
dµ(n/d) = n
d|n
X µ(d) d|n
d
.
Megold´ as. Alkalmazzuk a M¨obius-f´ele megford´ıt´ asi k´epletet az f (n) = φ(n), g(n) = n esetben. M´ask´epp: A M¨obius-f¨ uggv´eny tulajdons´ aga szerint X
φ(n) =
1=
X
X
µ(d) =
1≤k≤n d|(k,n)
1≤k≤n, (k,n)=1
n X X
µ(d) =
X
k=1 d|k, d|n
µ(d)
n/d X `=1
d|n
1=
X d|n
n µ(d) , d
ahol k = d`. 26. Legyenek f ´es g addit´ıv f¨ uggv´enyek. Vizsg´ aljuk, hogy addit´ıv-e az f + g ¨ osszeg, az f − g k¨ ul¨onbs´eg ´es az f g szorzatf¨ uggv´eny. 27. Igazoljuk, hogy 2ω(n) ≤ τ (n) ≤ 2Ω(n) minden n ≥ 1-re. 28. Igazoljuk, hogy minden n ≥ 1-re a)
X
µ(d)σ(n/d) = n,
b)
c)
d|n
µ(d)τ (n/d) = 1,
σ(d) = n
d|n
d|n
X
X
d)
X d|n
5
τ 2 (d)µ(n/d) =
X τ (d) d|n
X d|n
d
,
µ2 (d)τ (n/d).
