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

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

Определение


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

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



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



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

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



  h(n)=\{sum\_\{dn\} f(d) g(n/d).

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



  \{Phi\_f(s)=\{sum\_n f(n) n\^\{-s\}. При этом свёртке Дирихле двух арифметических функций соответствует произведение их производящих функций.

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


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


  (f*g)' = f'*g + f*g'. Переход к производящей функции превращает эту операцию в обычное дифференцирование.

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


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


 Арифметическая функция τ:NN определяется как число положительных делителей натурального числа n:
τ(n)=d|n1
 Если m и n взаимно просты, то каждый делитель произведения mn может быть единственным образом представлен в виде произведения делителей m и n, и обратно, каждое такое произведение является делителем mn. Отсюда следует, что функция τ мультипликативна:
τ(mn)=τ(m)τ(n)
 Если n=i=1rpisi — каноническое разложение натурального n, то в силу мультипликативности
τ(n)=τ(p1s1)τ(p2s2)τ(prsr)
 Так как положительными делителями числа pisi являются si+1 чисел 1,pi,,pisi, то
τ(n)=(s1+1)(s2+1)(sr+1)
 Число делителей большого целого числа n растёт в среднем как lnn. Более точно — см. формулу Дирихле.

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


 Функция σ:NN определяется как сумма делителей натурального числа n:
σ(n)=d|nd
 Обобщая функции τ(n) и σ(n) для произвольного, вообще говоря комплексного k, можно определить σk(n) — сумму k-х степеней положительных делителей натурального числа n:
σk(n)=d|ndk
 Используя нотацию Айверсона, можно записать
σk(n)=ddk[d|n]
 Функция σk мультипликативна:
mnσk(mn)=σk(m)σk(n)
 Если n=i=1rpisi — каноническое разложение натурального n, то
σk(n)=i=1rpi(si+1)k1pik1
 Сумма делителей числа n растёт в среднем как линейная функция cn, где постоянная c найдена Эйлером и есть c=ζ(2)=π2/6.

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


 Функция Эйлера φ(n), или тотиента, определяется как количество положительных целых чисел, не превосходящих n, которые взаимно просты с n.
 Пользуясь нотацией Айверсона, можно записать:
φ(n)=1kn[kn]
 Функция Эйлера мультипликативна:
mnφ(mn)=φ(m)φ(n)
 В явном виде значение функции Эйлера выражается формулой:
φ(n)=n(11p1)(11p2)(11pr)
 где p1,p2,,pr — различные простые делители n.

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


 Функцию Мёбиуса μ(n) можно определить как арифметическую функцию, которая удовлетворяет следующему соотношению:
d|nμ(d)={1,n=10,n>1
 То есть сумма значений функции Мёбиуса по всем делителям целого положительного числа n равна нулю, если n>1, и равна 1, если n=1.
 Можно показать, что этому уравнению удовлетворяет лишь одна функция, и её можно явно задать следующей формулой:
μ(n)={(1)r,n=p1p2pr0,p2|n1,n=1
 Здесь pi — различные простые числа, p — простое число. Иначе говоря, функция Мёбиуса μ(n) равна 0, если n не свободно от квадратов (то есть делится на квадрат простого числа), и равна ±1 в противном случае (плюс или минус выбирается в зависимости от четности числа простых делителей n).
 Функция Мёбиуса является мультипликативной функцией. Важное значение функции Мёбиуса в теории чисел связано с формулой обращения Мёбиуса.