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

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

Определение

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

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

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

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

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

• Суммой арифметической функции ${\displaystyle f}$ называют функцию ${\displaystyle F:[0,+\infty )\to \mathbb {C} }$, определённую как

${\displaystyle F(x)=\sum _{n\leq x}f(n).}$

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

• Свёрткой Дирихле двух арифметических функций f и g называется арифметическая функция h, определённая по правилу

${\displaystyle h(n)=\sum _{d|n}f(d)g(n/d).}$

• Арифметической функции f можно сопоставить её «производящую функцию» — ряд Дирихле

${\displaystyle \Phi _{f}(s)=\sum _{n}f(n)n^{-s}.}$

При этом свёртке Дирихле двух арифметических функций соответствует произведение их производящих функций.

• Поточечное умножение на логарифм,

${\displaystyle f\mapsto f',\quad f'(n)=f(n)\cdot \ln n,}$

является дифференцированием алгебры арифметических функций: относительно свёртки оно удовлетворяет правилу Лейбница,

${\displaystyle (f*g)'=f'*g+f*g'.}$

Переход к производящей функции превращает эту операцию в обычное дифференцирование.

Известные арифметические функции

Число делителей

Арифметическая функция ${\displaystyle \tau \colon \mathbb {N} \to \mathbb {N} }$ определяется как число натуральных делителей натурального числа ${\displaystyle n}$:

${\displaystyle \tau (n)=\sum _{d|n}1}$

Если ${\displaystyle m}$ и ${\displaystyle n}$ взаимно просты, то каждый делитель произведения ${\displaystyle mn}$ может быть единственным образом представлен в виде произведения делителей ${\displaystyle m}$ и делителей ${\displaystyle n}$, и обратно, каждое такое произведение является делителем ${\displaystyle mn}$. Отсюда следует, что функция ${\displaystyle \tau }$ мультипликативна:

${\displaystyle \tau (mn)=\tau (m)\tau (n)}$

Если ${\displaystyle n=\prod _{i=1}^{r}p_{i}^{s_{i}}}$ — каноническое разложение натурального ${\displaystyle n}$, то в силу мультипликативности

${\displaystyle \tau (n)=\tau (p_{1}^{s_{1}})\tau (p_{2}^{s_{2}})\ldots \tau (p_{r}^{s_{r}})}$

Так как положительными делителями числа ${\displaystyle p_{i}^{s_{i}}}$ являются ${\displaystyle s_{i}+1}$ чисел ${\displaystyle 1,p_{i},\ldots ,p_{i}^{s_{i}}}$, то

${\displaystyle \tau (n)=(s_{1}+1)(s_{2}+1)\ldots (s_{r}+1)}$

Число делителей большого целого числа n растёт в среднем как ${\displaystyle \ln n}$^[1]. Более точно — см. формулу Дирихле.

Сумма делителей

Основная статья: Функция делителей

Функция ${\displaystyle \sigma \colon \mathbb {N} \to \mathbb {N} }$ определяется как сумма делителей натурального числа ${\displaystyle n}$:

${\displaystyle \sigma (n)=\sum _{d|n}d}$

Обобщая функции ${\displaystyle \tau (n)}$ и ${\displaystyle \sigma (n)}$ для произвольного, вообще говоря комплексного ${\displaystyle k}$, можно определить ${\displaystyle \sigma _{k}(n)}$ — сумму ${\displaystyle k}$-х степеней положительных делителей натурального числа ${\displaystyle n}$:

${\displaystyle \sigma _{k}(n)=\sum _{d|n}d^{k}}$

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

${\displaystyle \sigma _{k}(n)=\sum _{d}d^{k}[\,d|n\,]}$

Функция ${\displaystyle \sigma _{k}}$ мультипликативна:

${\displaystyle m\perp n\Rightarrow ~\sigma _{k}(mn)=\sigma _{k}(m)\sigma _{k}(n)}$

Если ${\displaystyle n=\prod _{i=1}^{r}p_{i}^{s_{i}}}$ — каноническое разложение натурального ${\displaystyle n}$, то

${\displaystyle \sigma _{k}(n)=\prod _{i=1}^{r}{\frac {p_{i}^{(s_{i}+1)k}-1}{p_{i}^{k}-1}}}$

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

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

Основная статья: Функция Эйлера

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

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

${\displaystyle \varphi (n)=\sum _{1\leq k\leq n}[k\perp n]}$

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

${\displaystyle m\perp n\Rightarrow ~\varphi (mn)=\varphi (m)\varphi (n)}$

В явном виде значение функции Эйлера выражается формулой:

${\displaystyle \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)}$

где ${\displaystyle p_{1},p_{2},\ldots ,p_{r}}$ — различные простые делители ${\displaystyle n}$.

Функция Мёбиуса

Основная статья: Функция Мёбиуса

Функцию Мёбиуса ${\displaystyle \mu (n)}$ можно определить как арифметическую функцию, которая удовлетворяет следующему соотношению:

${\displaystyle \sum _{d|n}\mu (d)={\begin{cases}1,&n=1\\0,&n>1\end{cases}}}$

То есть сумма значений функции Мёбиуса по всем делителям целого положительного числа ${\displaystyle n}$ равна нулю, если ${\displaystyle n>1}$, и равна ${\displaystyle 1}$, если ${\displaystyle n=1}$.

Можно показать, что этому уравнению удовлетворяет лишь одна функция, и её можно явно задать следующей формулой:

${\displaystyle \mu (n)={\begin{cases}(-1)^{r},&n=p_{1}p_{2}\ldots p_{r}\\0,&p^{2}|n\\1,&n=1\end{cases}}}$

Здесь ${\displaystyle p_{i}}$ — различные простые числа, ${\displaystyle p}$ — простое число. Иначе говоря, функция Мёбиуса ${\displaystyle \mu (n)}$ равна ${\displaystyle 0}$, если ${\displaystyle n}$ не свободно от квадратов (то есть делится на квадрат простого числа), и равна ${\displaystyle \pm 1}$ в противном случае (плюс или минус выбирается в зависимости от четности числа простых делителей ${\displaystyle n}$).

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

Примечания

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

См. также

• Мультипликативная функция

Литература

• Виноградов И. М. Основы теории чисел. — М.—Л.: ГИТТЛ, 1952. — 180 с.
• Нестеренко Ю. В. Теория чисел: учебник для студ. высш. учеб. заведений. — М.: Издательский центр «Академия», 2008. — 272 с. — ISBN 978-5-7695-4646-4.
• Чандрасекхаран К. Введение в аналитическую теорию чисел = Introduction to Analytic Number Theory. — М.: «Мир», 1974. — 188 с.