1 Aritmetické funkcie

Ak f: ℕ → ℂ je multiplikatívna, tak g: ℕ → ℂ definovaná ako g(n) = ∑_{m|n} f(m) je multiplikatívna. Pre n = p_{1}^{α_{1}} + … + f(p_{k}^{α_{k}})) platí f(n) = (1 + f(p_{1}) + … + f(p_{1}^{α_{1}})) … (1 + f(p_{k}) + … + f(p_{k}^{α_{k}})).

1.1 Möbiova funkcia

μ: ℕ → ℂ je definovaná ako μ(n) = \begin{cases}1, & ak n = 1 \\ (−1)^{r}, & ak n = p_{1} … p_{r} \\ 0, & inak. \end{cases}

μ je multiplikatívna funkcia. Číslo n je bez štvorcov μ(n) = ±1.

∑_{m|n} μ(m) = \begin{cases}1, & ak n = 1, \\ 0, & ak n > 1. \end{cases}

∑_{m=1}^{∞} \frac{μ(m)}{m^{2}} = \frac{6}{π^{2}}

Möbius inversion formula: Ak g(n) = ∑_{m|n} f(m) pre ľubovoľné n, tak

f(n) = ∑_{m|n} μ(m)g (\frac{n}{m}) = ∑_{m|n} μ (\frac{n}{m}) g(m).

Ak f(n) = ∑_{m|n} μ (\frac{n}{m}) g(m), tak g(n) = ∑_{m|n} f(m).

f(n) = ∑_{d|n} μ (\frac{d}{n}) g(d) ⇔ g(n) = ∑_{d|n} f(d)

G(x) = ∑_{n=1}^{[x]}F (\frac{x}{n}) ⇔ F (x) = ∑_{n=1}^{[x]}μ(n)G (\frac{x}{n})

g(x) = ∑_{n=1}^{∞}f(nx) ⇔ f(x) = ∑_{n=1}^{∞}μ(n)g(nx)

Posledná rovnosť platí, len ak tie rady konvergujú.

1.2 Eulerova funkcia

∑_{m|n} φ(m) = n

φ(n) = ∑_{m|n} μ(m)\frac{n}{m} = n ∑_{m|n} \frac{μ(m)}{m}

φ(n) = n ∏_{j=1}^{r} (1 − \frac{1}{p_{j}} )

\frac{6}{π^{2}} < \frac{σ(n)φ(n)}{n^{2}} < 1

φ(1) + φ(2) + … + φ(n) = \frac{3n^{2}}{π^{2}} + O(n logn)

1.3 Ďalšie funkcie

Pre každé δ > 0 je d(n) = O(n^{δ}). lim sup \frac{log d(n) log log n}{log n} = log2 θ(x) = ∑_{p≤x} logp ⇒ θ(x) > Ax d(1) + d(2) + … + d(n) = n logn + (2γ − 1)n + O(\sqrt{n}) σ(n) = O(n^{1+δ} ) pre δ > 0 σ(1) + σ(2) + … + σ(n) = \frac{π^{2}}{12} n^{2} + O(n logn) σ(n) = O(m logn) Ak n je zložené, tak σ(n) > n + \sqrt{n}

2 Užitočné vzorce

1 + \frac{1}{2} + … + \frac{1}{n} − logn = γ + O (\frac{1}{n})

π(n) = \frac{n}{log n} + \frac{n}{log^{2} n} + \frac{2!n^{3}}{log^{3} n} + \frac{3!n}{log^{4} n} + O (\frac{n}{log^{5} n})

n-té prvočíslo: p(n) = n logn + n loglogn − n + \frac{n log log n}{log n} + O (\frac{n}{log n})

n! = \sqrt{2πn}(\frac{n}{e})^{n} (1 + \frac{1}{12n} + \frac{1}{288n^{2}} − \frac{139}{51840n^{3}} + O (\frac{1}{n^{4}} ))

Literatúra

[1] W.Chen: Distribution of prime numbers, http://www.maths.mq.edu.au/˜ wchen

[2] M.Kolibiar, A.Legéň, T.Šalát, Š.Znám: Algebra a príbuzné disciplíny.

[3] D.E.Knuth: Concrete Mathematics.