Processing math: 100%

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

Арифметическая функция — функция, определенная на множественатуральных чисел 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\_\{d\textbarn\} 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=ri=1psii — каноническое разложениенатурального n, то в силу мультипликативности
τ(n)=τ(ps11)τ(ps22)τ(psrr)
 Так как положительными делителями числа psii являются si+1чисел 1,pi,,psii, то
τ(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=ri=1psii — каноническое разложениенатурального n, то
σk(n)=ri=1p(si+1)ki1pki1
 Сумма делителей числа 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).
 Функция Мёбиуса является мультипликативной функцией. Важное значениефункции Мёбиуса в теории чисел связано с формулой обращения Мёбиуса.