Арифметична функція

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Арифметична функціяфункція, визначена на множині натуральних чисел \N, що приймає значення в множині комплексних чисел \C.

Визначення[ред.ред. код]

Як випливає з визначення, арифметичною функцією називається будь-яка функція

f \colon \N \to \C

Назва арифметична функція пов'язана з тим, що в теорії чисел відомо багато функцій ~f(n) натурального аргументу ~n, які виражають ті або інші арифметичні властивості ~n. Тому, неформально кажучи, під арифметичною функцією розуміють функцію ~f(n), яка «виражає деяку арифметичну властивість» натурального числа ~n (див. приклади арифметичних функцій нижче).

Багато арифметичних функцій, що розглядаються в теорії чисел, насправді приймають цілочислові значення.

Операції і зв'язані поняття[ред.ред. код]

  • Сумою арифметичної функції f називають функцію F:[0,+\infty)\to \C, визначену як

F(x)=\sum_{n\le x} f(n).

Ця операція є «дискретним аналогом» невизначеного інтеграла; при цьому, хоча початкова функція і була визначена тільки на \N, її суму виявляється зручним вважати визначеною на всій додатній півосі (при цьому вона, природно, кусково-стала).

  • Згорткою Діріхле двох арифметичних функцій f і g називається арифметична функція h, визначена за правилом
\ 
h(n)=\sum_{d|n} f(d) g(n/d).
\ 
\Phi_f(s)=\sum_n f(n)n^{-s}.

При цьому згортці Діріхле двох арифметичних функцій відповідає добуток їх генератрис.

f\mapsto f', \quad f'(n)=f(n) \cdot \ln n,

є диференціюванням алгебри арифметичних функцій: відносно згортки воно задовольняє правилу Лейбніца

\ 
(f*g)' = f'*g + f*g'.

Перехід до генератриси, перетворює цю операцію на звичайне диференціювання.

Відомі арифметичні функції[ред.ред. код]

Кількість дільників[ред.ред. код]

Арифметична функція ~\tau \colon \mathbb{N} \to \mathbb{N} визначається як число додатнних дільників натурального числа ~n:


~\tau(n) = \sum_{d|n} 1

Якщо ~m і ~n взаємно прості, то кожен дільник добутку ~mn може бути єдиним чином поданий у вигляді добутку дільників ~m і ~n, і навпаки, кожне такий добуток є дільником ~mn. Звідси випливає, що функція ~\tau мультиплікативна:


~\tau(mn) = \tau(m)\tau(n)

Якщо ~n = \prod_{i=1}^{r} p_i^{s_i}розклад на прості множники натурального числа ~n, то зважаючи на мультиплікативність


~\tau(n) = \tau(p_1^{s_1})\tau(p_2^{s_2}) \ldots \tau(p_r^{s_r})

Але додатними дільниками числа p_i^{s_i} є ~s_i+1 чисел 1, p_i, \ldots, p_i^{s_i}.

Відповідно


~\tau(n) = (s_1+1) (s_2+1) \ldots (s_r+1)

Сума дільників[ред.ред. код]

Функція \sigma \colon \mathbb{N} \to \mathbb{N} визначається як сума дільників натурального числа ~n:


~\sigma (n) = \sum_{d|n} d

Узагальнюючи функції ~\tau(n) і ~\sigma(n) для довільного, взагалі кажучи комплексного ~k можна визначити ~\sigma_k(n) — суму k-их степенів додатних дільників натурального числа ~n:


~\sigma_k (n) = \sum_{d|n} d^k

Використовуючи нотацію Айверсона можна записати


~\sigma_k(n) = \sum_{d} d^k[\,d|n\,]

Функція ~\sigma_k мультиплікативна:


m \perp n \Rightarrow ~\sigma_k (mn) = \sigma_k (m) \sigma_k (n)

Якщо ~n = \prod_{i=1}^{r} p_i^{s_i} — розклад на прості дільники натурального числа ~n, то


~\sigma_k(n) = \prod_{i=1}^r  \frac {p_i^{(s_i+1)k}-1} {p_i - 1}

Функція Ейлера[ред.ред. код]

Докладніше: Функція Ейлера

Функція Ейлера \varphi(n), визначається як кількість додатних цілих чисел, що не є більшими за ~n, і є взаємно простими з ~n.

Користуючись нотацією Айверсона можна записати:


\varphi(n) = \sum_{1 \leq k \leq n} [k \perp n]

Функція Ейлера мультиплікативна:


m \perp n \Rightarrow ~\varphi (mn) = \varphi (m) \varphi (n)

У явному вигляді значення функції Ейлера виражається формулою:


\varphi (n) = n \left(1 - \frac{1}{p_1} \right) \left(1 - \frac{1}{p_2} \right) \dots \left(1 - \frac{1}{p_r} \right)

де p_1, p_2, \ldots, p_r — різні прості дільники ~n.

Функція Мебіуса[ред.ред. код]

Докладніше: Функція Мебіуса

Функцію Мебіуса ~\mu(n) можна визначити як арифметичну функцію, що задовольняє наступній властивості:


\sum_{d | n} \mu(d) = 
\begin{cases}
1,&n=1\\
0,&n>1
\end{cases}

Тобто сума значень функції Мебіуса по всіх дільниках цілого додатного числа ~n рівна нулю, якщо ~n>1, і рівна ~1, якщо ~n=1.

Можна показати, що цьому рівнянню задовольняє лише одна функція, і її можна явно задати наступною формулою:


\mu(n) = 
\begin{cases}
(-1)^r, & n = p_1 p_2 \ldots p_r \\
0,      & p^2 | n \\
1,      & n=1
\end{cases}

Тут p_i — різні прості числа p — просте число. Інакше кажучи, функція Мебіуса \mu(n) рівна 0, якщо n не вільно від квадратів (тобто ділиться на квадрат простого числа), і рівна ~\pm 1 інакше (плюс або мінус вибирається залежно від парності числа простих дільників ~n).

Функція Мебіуса є мультиплікативною функцією.

Див. також[ред.ред. код]

Література[ред.ред. код]

  • Чандрасекхаран К. Арифметические функции, пер. с англ., — М.: «Мир», 1975;
  • Чандрасекхаран К. Введение в аналитическую теорию чисел. — М.: «Мир», 1974. — 188 с.