Арифметическая функция | это... Что такое Арифметическая функция? (original) (raw)

Арифметическая функция — функция, определенная на множестве натуральных чисел \mathbb{N}, и принимающая значения во множестве комплексных чисел \mathbb{C}.

Содержание

Определение

Как следует из определения, арифметической функцией называется любая функция

f \colon \mathbb{N} \to \mathbb{C}

Название арифметическая функция связано с тем, что в теории чисел известно много функций ~f(n) натурального аргумента ~n, которые выражают те или иные арифметические свойства ~n. Поэтому, неформально говоря, под арифметической функцией понимают функцию ~f(n), которая «выражает некоторое арифметическое свойство» натурального числа ~n (см. примеры арифметических функций ниже).

Многие арифметические функции, рассматриваемые в теории чисел, в действительности являются целозначными.

Операции и связанные понятия

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

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

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)

Число делителей большого целого числа n растёт в среднем как \ln n[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}

Сумма делителей числа n растёт в среднем как линейная функция cn, где постоянная c найдена Эйлером и есть c=\zeta(2)=\pi^2/6[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).

Функция Мёбиуса является мультипликативной функцией. Важное значение функции Мёбиуса в теории чисел связано с формулой обращения Мёбиуса.

Примечания

  1. ↑ 1 2 В. И Арнольд Динамика, статистика и проективная геометрия полей Галуа. — М.: МЦНМО, 2005. — С. 70. — 72 с.

См. также

Литература