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

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

Определение

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

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

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

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

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

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

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

Эта операция является «дискретным аналогом» неопределённого интеграла; при этом, хотя исходная функция и была определена только на $\mathbb {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$. Более точно — см. формулу Дирихле.

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

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

Функция $\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$.

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

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

Функция Эйлера $\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$).

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

См. также

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

Литература

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