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

Статья на основе материалов из Википедии

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

Определение

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

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

Название арифметическая функция связано с тем, что в теории чисел известно много функций `f(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).
  • Арифметической функции f можно сопоставить её «производящую функцию» — ряд Дирихле
: \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^k - 1}

Сумма делителей числа n растёт в среднем как линейная функция cn, где постоянная c найдена Эйлером и есть `c=\zeta(2)=\pi^2/6` [1].

Функция Эйлера

Главная статья: Функция Эйлера
Функция Эйлера `\varphi(n)` , или тотиента, определяется как количество положительных целых чисел, не превосходящих `n` , которые взаимно просты с `n` .

Пользуясь нотацией Айверсона, можно записать:

\varphi(n) = \sum_{1 \leq k \leq n} \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. В. И Арнольд Динамика, статистика и проективная геометрия полей Галуа — М. : МЦНМО, 2005 — 72 — 70

См. также

Литература