WikiSort.ru - Не сортированное

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

Арифметическая функция ${\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}$ ).

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