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

Эта статья в список формат, но может читаться лучше как проза. Вы можете помочь преобразование этой статьи, при необходимости. Помощь при редактировании доступен. (Июль 2020)

В теория чисел, арифметика, арифметический, или же теоретико-числовая функция^[1][2] для большинства авторов^[3][4][5] любой функция ж(п), доменом которого является положительные целые числа и чей диапазон подмножество из сложные числа. Харди и Райт включают в свое определение требование, чтобы арифметическая функция «выражала некоторое арифметическое свойство п".^[6]

Примером арифметической функции является делительная функция чье значение в положительном целом числе п равно количеству делителей п.

Существует более широкий класс теоретико-числовых функций, которые не соответствуют приведенному выше определению, например, функции подсчета простых чисел. В этой статье есть ссылки на функции обоих классов.

Многие из функций, упомянутых в этой статье, имеют расширения в виде серий, включающих эти суммы; посмотреть статью Сумма Рамануджана Например.

Мультипликативные и аддитивные функции

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

• полностью аддитивный если а(млн) = а(м) + а(п) для всех натуральных чисел м и п;
• полностью мультипликативный если а(млн) = а(м)а(п) для всех натуральных чисел м и п;

Два целых числа м и п называются совмещать если их наибольший общий делитель равно 1, то есть если нет простое число что разделяет их обоих.

Тогда арифметическая функция а является

• добавка если а(млн) = а(м) + а(п) для всех взаимно простых натуральных чисел м и п;
• мультипликативный если а(млн) = а(м)а(п) для всех взаимно простых натуральных чисел м и п.

Обозначение

${displaystyle sum _ {p} f (p)}$ и ${displaystyle prod _ {p} f (p)}$ означают, что сумма или произведение больше простые числа:

${displaystyle sum _ {p} f (p) = f (2) + f (3) + f (5) + cdots}$

${displaystyle prod _ {p} f (p) = f (2) f (3) f (5) cdots.}$

По аналогии, ${displaystyle sum _ {p ^ {k}} f (p ^ {k})}$ и ${displaystyle prod _ {p ^ {k}} f (p ^ {k})}$ означают, что сумма или произведение больше основные силы со строго положительным показателем (так k = 0 не входит):

${displaystyle sum _ {p ^ {k}} f (p ^ {k}) = sum _ {p} sum _ {k> 0} f (p ^ {k}) = f (2) + f (3) + f (4) + f (5) + f (7) + f (8) + f (9) + cdots}$

${displaystyle sum _ {dmid n} f (d)}$ и ${displaystyle prod _ {dmid n} f (d)}$ означают, что сумма или произведение больше всех положительных делителей п, в том числе 1 и п. Например, если п = 12,

${Displaystyle prod _ {dmid 12} е (д) = е (1) е (2) е (3) е (4) е (6) е (12). }$

Обозначения можно комбинировать: ${displaystyle sum _ {pmid n} f (p)}$ и ${displaystyle prod _ {pmid n} f (p)}$ означают, что сумма или произведение больше всех простых делителей числа п. Например, если п = 18,

${displaystyle sum _ {pmid 18} f (p) = f (2) + f (3),}$

и аналогично ${displaystyle sum _ {p ^ {k} mid n} f (p ^ {k})}$ и ${displaystyle prod _ {p ^ {k} mid n} f (p ^ {k})}$ означают, что сумма или произведение превышает все простые степени, делящие п. Например, если п = 24,

${displaystyle prod _ {p ^ {k} mid 24} f (p ^ {k}) = f (2) f (3) f (4) f (8). }$

Ω (п), ω(п), ν_п(п) - разложение на простые степени

В основная теорема арифметики утверждает, что любое положительное целое число п можно однозначно представить как произведение степеней простых чисел: ${displaystyle n = p_ {1} ^ {a_ {1}} cdots p_ {k} ^ {a_ {k}}}$ куда п₁ < п₂ < ... < п_k простые числа и а_j положительные целые числа. (1 дается пустым произведением.)

Часто удобно записывать это как бесконечное произведение по всем простым числам, где все числа, кроме конечного, имеют нулевой показатель степени. Определить п-адическая оценка ν_п(п) быть показателем наивысшей степени простого п что разделяет п. То есть, если п один из п_я тогда ν_п(п) = а_я, в противном случае - ноль. потом

${displaystyle n = prod _ {p} p ^ {u _ {p} (n)}.}$

С точки зрения вышеизложенного основные функции омега ω и Ω определяются формулами

ω(п) = k,

Ω (п) = а₁ + а₂ + ... + а_k.

Чтобы избежать повторения, по возможности формулы для функций, перечисленных в этой статье, даются в терминах п и соответствующие п_я, а_я, ω и Ω.

Мультипликативные функции

σ_k(п), τ (п), d(п) - суммы делителей

σ_k(п) это сумма k-ые степени положительных делителей п, в том числе 1 и п, куда k - комплексное число.

σ₁(п), сумма (положительных) делителей п, обычно обозначается σ (п).

Поскольку положительное число в нулевой степени равно единице, σ₀(п) следовательно, количество (положительных) делителей числа п; обычно обозначается d(п) или же τ (п) (для немецкого Teiler = делители).

${displaystyle sigma _ {k} (n) = prod _ {i = 1} ^ {omega (n)} {frac {p_ {i} ^ {(a_ {i} +1) k} -1} {p_ { i} ^ {k} -1}} = prod _ {i = 1} ^ {omega (n)} left (1 + p_ {i} ^ {k} + p_ {i} ^ {2k} + cdots + p_ {i} ^ {a_ {i} k} ight).}$

Параметр k = 0 во втором произведении дает

${displaystyle au (n) = d (n) = (1 + a_ {1}) (1 + a_ {2}) cdots (1 + a_ {omega (n)}).}$

φ (п) - функция Эйлера

φ (п), функция Эйлера, - это количество натуральных чисел, не превышающих п которые взаимно просты с п.

${displaystyle varphi (n) = nprod _ {pmid n} left (1- {frac {1} {p}} ight) = nleft ({frac {p_ {1} -1} {p_ {1}}} ight) left ({frac {p_ {2} -1} {p_ {2}}} ight) cdots left ({frac {p_ {omega (n)} - 1} {p_ {omega (n)}}} ight). }$

J_k(п) - Жорданова totient функция

J_k(п), тоциент-функция Жордана, - количество k-наборы натуральных чисел все меньше или равны п которые образуют взаимно простое (k + 1) -комплект вместе с п. Это обобщение теории Эйлера, φ (п) = J₁(п).

${displaystyle J_ {k} (n) = n ^ {k} prod _ {pmid n} left (1- {frac {1} {p ^ {k}}} ight) = n ^ {k} left ({frac {p_ {1} ^ {k} -1} {p_ {1} ^ {k}}} ight) left ({frac {p_ {2} ^ {k} -1} {p_ {2} ^ {k}) }} ight) cdots left ({frac {p_ {omega (n)} ^ {k} -1} {p_ {omega (n)} ^ {k}}} ight).}$

μ (п) - функция Мёбиуса

μ (п), функция Мёбиуса, важна из-за Инверсия Мёбиуса формула. Видеть Свертка Дирихле, ниже.

${displaystyle mu (n) = {egin {case} (- 1) ^ {omega (n)} = (- 1) ^ {Omega (n)} & {ext {if}}; omega (n) = Omega ( n) 0 & {ext {if}}; omega (n) eq Omega (n) .end {case}}}$

Отсюда следует, что μ (1) = 1. (поскольку Ω (1) = ω (1) = 0.)

τ (п) - функция тау Рамануджана

τ (п), тау-функция Рамануджана, определяется своим производящая функция личность:

${displaystyle sum _ {ngeq 1} au (n) q ^ {n} = qprod _ {ngeq 1} (1-q ^ {n}) ^ {24}.}$

Хотя трудно сказать, какое именно «арифметическое свойство п"это" выражает ",^[7] (τ(п) равно (2π)⁻¹² раз пth коэффициент Фурье в q-расширение из модульный дискриминант функция)^[8] он включен в число арифметических функций, потому что он мультипликативен и встречается в тождествах, содержащих определенные σ_k(п) и р_k(п) функций (потому что они также являются коэффициентами в разложении модульные формы ).

c_q(п) - сумма Рамануджана

c_q(п), Сумма Рамануджана, является суммой псилы первобытного qth корни единства:

${displaystyle c_ {q} (n) = sum _ {stackrel {1leq aleq q} {gcd (a, q) = 1}} e ^ {2pi i {frac {a} {q}} n}.}$

Несмотря на то, что он определяется как сумма комплексных чисел (иррационально для большинства значений q), это целое число. При фиксированном значении п это мультипликативно в q:

Если q и р взаимно просты, тогда ${displaystyle c_ {q} (n) c_ {r} (n) = c_ {qr} (n).}$

ψ(п) - пси-функция Дедекинда

В Пси-функция Дедекинда, используемые в теории модульные функции, определяется формулой

${displaystyle psi (n) = nprod _ {p | n} left (1+ {frac {1} {p}} ight).}$

Полностью мультипликативные функции

λ (п) - функция Лиувилля

λ(п), функция Лиувилля, определяется как

${displaystyle lambda (n) = (- 1) ^ {Omega (n)}.}$

χ(п) - символы

Все Персонажи Дирихле χ(п) полностью мультипликативны. Два символа имеют специальные обозначения:

В главный персонаж (мод п) обозначается χ₀(а) (или же χ₁(а)). Он определяется как

${displaystyle chi _ {0} (a) = {egin {cases} 1 & {ext {if}} gcd (a, n) = 1, 0 & {ext {if}} gcd (a, n) eq 1.end {случаи}}}$

В квадратичный характер (mod п) обозначается Символ Якоби для нечетных п (не определено даже для п.):

${displaystyle {Bigg (} {frac {a} {n}} {Bigg)} = left ({frac {a} {p_ {1}}} ight) ^ {a_ {1}} left ({frac {a} {p_ {2}}} ight) ^ {a_ {2}} cdots left ({frac {a} {p_ {omega (n)}}} ight) ^ {a_ {omega (n)}}.}$

В этой формуле ${displaystyle ({frac {a} {p}})}$ это Символ Лежандра, определенная для всех целых чисел а и все нечетные простые числа п к

${displaystyle left ({frac {a} {p}} ight) = {egin {cases} ;;, 0 & {ext {if}} aequiv 0 {pmod {p}}, + 1 & {ext {if}} aot Equiv 0 {pmod {p}} {ext {и для некоторого целого}} x,; aequiv x ^ {2} {pmod {p}} - 1 & {ext {если таких нет}} x.end {случаях }}}$

Следуя обычному соглашению для пустого продукта, ${displaystyle left ({frac {a} {1}} ight) = 1.}$

Аддитивные функции

ω(п) - различные простые делители

ω (п), определенный выше как количество различных простых чисел, делящих п, является аддитивным (см. Основная функция омега ).

Полностью аддитивные функции

Ω (п) - простые делители

Ω (п), определенный выше как количество простых факторов п с учетом кратностей, полностью аддитивен (см. Основная функция омега ).

ν_п(п) – п-адическая оценка целого числа п

Для фиксированного простого числа п, ν_п(п), определенный выше как показатель наибольшей степени п разделение п, является полностью аддитивным.

Ни мультипликативный, ни аддитивный

π(Икс), Π (Икс), θ(Икс), ψ(Икс) - функции счисления простых чисел

Эти важные функции (которые не являются арифметическими функциями) определены для неотрицательных вещественных аргументов и используются в различных утверждениях и доказательствах теорема о простых числах. Это функции суммирования (см. Основной раздел чуть ниже) арифметических функций, которые не являются ни мультипликативными, ни аддитивными.

π(Икс), функция подсчета простых чисел, - это количество простых чисел, не превышающих Икс. Это функция суммирования характеристическая функция простых чисел.

${displaystyle pi (x) = sum _ {pleq x} 1}$

Связанная функция подсчитывает простые степени с весом 1 для простых чисел, 1/2 для их квадратов, 1/3 для кубов, ... Это функция суммирования арифметической функции, которая принимает значение 1 /k для целых чисел, являющихся k-й степенью одного простого числа, и значение 0 для других целых чисел.

${displaystyle Pi (x) = sum _ {p ^ {k} leq x} {frac {1} {k}}.}$

θ(Икс) и ψ(Икс), функции Чебышева, определяются как суммы натуральных логарифмов простых чисел, не превосходящих Икс.

${displaystyle vartheta (x) = sum _ {pleq x} log p,}$

${displaystyle psi (x) = sum _ {p ^ {k} leq x} log p.}$

Функция Чебышева ψ(Икс) - функция суммирования функции фон Мангольдта чуть ниже.

Λ (п) - функция фон Мангольдта

Λ (п), функция фон Мангольдта равна 0, если аргумент п это основная сила п^k, в этом случае это натуральный логарифм простого числа п:

${displaystyle Lambda (n) = {egin {cases} log p & {ext {if}} n = 2,3,4,5,7,8,9,11,13,16, ldots = p ^ {k} { ext {степень простого числа}} 0 & {ext {if}} n = 1,6,10,12,14,15,18,20,21, dots ;;;; {ext {степень простого числа} } .end {case}}}$

п(п) - статистическая сумма

п(п), статистическая сумма, - это количество способов представления п как сумма положительных целых чисел, где два представления с одними и теми же слагаемыми в разном порядке не считаются разными:

${displaystyle p (n) = | left {(a_ {1}, a_ {2}, dots a_ {k}): 0$

λ (п) - функция Кармайкла

λ(п), функция Кармайкла, является наименьшим положительным числом такое, что ${displaystyle a ^ {lambda (n)} Equiv 1 {pmod {n}}}$ для всех а взаимно простой с п. Эквивалентно, это наименьший общий множитель порядков элементов мультипликативная группа целых чисел по модулю п.

Для степеней нечетных простых чисел и 2 и 4, λ(п) равна тотент-функции Эйлера п; для степеней 2 больше 4 он равен половине тотальной функции Эйлера от п:

${displaystyle lambda (n) = {egin {case} ;; phi (n) & {ext {if}} n = 2,3,4,5,7,9,11,13,17,19,23,25 , 27, точки {frac {1} {2}} phi (n) & {ext {if}} n = 8,16,32,64, точки на конце {case}}}$

и для общего п это наименьшее общее кратное λ каждого из простых множителей мощности п:

${displaystyle lambda (p_ {1} ^ {a_ {1}} p_ {2} ^ {a_ {2}} dots p_ {omega (n)} ^ {a_ {omega (n)}}) = имя оператора {lcm} [лямбда (p_ {1} ^ {a_ {1}}) ,; лямбда (p_ {2} ^ {a_ {2}}), точки, лямбда (p_ {омега (n)} ^ {a_ {омега (n )}})].}$

час(п) - Номер класса

час(п), функция числа классов, является порядком группа идеального класса алгебраического расширения рациональных чисел с дискриминант п. Обозначения неоднозначны, так как обычно существует множество расширений с одним и тем же дискриминантом. Видеть квадратичное поле и круговое поле для классических примеров.

р_k(п) - Сумма k квадраты

р_k(п) это количество способов п можно представить как сумму k квадраты, где представления, которые отличаются только порядком слагаемых или знаками квадратных корней, считаются разными.

${displaystyle r_ {k} (n) = | {(a_ {1}, a_ {2}, точки, a_ {k}): n = a_ {1} ^ {2} + a_ {2} ^ {2} + cdots + a_ {k} ^ {2}} |}$

D(п) - арифметическая производная

С использованием Обозначение Хевисайда для производной, D(п) функция такая, что

${displaystyle D (n) = 1}$ если п премьер, и

${displaystyle D (mn) = mD (n) + D (m) n}$ (Правило продукта )

Функции суммирования

Учитывая арифметическую функцию а(п), это функция суммирования А(Икс) определяется

${displaystyle A (x): = sum _ {nleq x} a (n).}$

А можно рассматривать как функцию действительной переменной. Учитывая положительное целое число м, А постоянно открытые интервалы м < Икс < м + 1 и имеет скачкообразный разрыв для каждого целого числа, для которого а(м) ≠ 0.

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

${displaystyle A_ {0} (m): = {frac {1} {2}} left (sum _ {n$

Отдельные значения арифметических функций могут сильно колебаться - как в большинстве приведенных выше примеров. Функции суммирования «сглаживают» эти колебания. В некоторых случаях можно найти асимптотическое поведение для функции суммирования для больших Икс.

Классический пример этого явления^[9] дается функция сумматора делителя, функция суммирования d(п), количество делителей п:

${displaystyle liminf _ {нет информации} d (n) = 2}$

${displaystyle limsup _ {n o infty} {frac {log d (n) log log n} {log n}} = log 2}$

${displaystyle lim _ {n o infty} {frac {d (1) + d (2) + cdots + d (n)} {log (1) + log (2) + cdots + log (n)}} = 1 .}$

An средний порядок арифметической функции представляет собой некоторую более простую или лучше понятую функцию, которая асимптотически имеет ту же функцию суммирования и, следовательно, принимает те же значения «в среднем». Мы говорим что грамм является средний заказ из ж если

${displaystyle sum _ {nleq x} f (n) sim sum _ {nleq x} g (n)}$

в качестве Икс стремится к бесконечности. Пример выше показывает, что d(п) имеет журнал средних заказов (п).^[10]

Свертка Дирихле

Учитывая арифметическую функцию а(п), позволять F_а(s), для сложных s, - функция, определяемая соответствующими Серия Дирихле (где это сходится ):^[11]

${displaystyle F_ {a} (s): = sum _ {n = 1} ^ {infty} {frac {a (n)} {n ^ {s}}}.}$

F_а(s) называется производящая функция из а(п). Простейший такой ряд, соответствующий постоянной функции а(п) = 1 для всех п, является ς(s) Дзета-функция Римана.

Производящая функция функции Мёбиуса является обратной по отношению к дзета-функции:

${displaystyle zeta (s), sum _ {n = 1} ^ {infty} {frac {mu (n)} {n ^ {s}}} = 1, ;; {mathfrak {R}}, s> 0. }$

Рассмотрим две арифметические функции а и б и их соответствующие производящие функции F_а(s) и F_б(s). Продукт F_а(s)F_б(s) можно вычислить следующим образом:

${displaystyle F_ {a} (s) F_ {b} (s) = left (sum _ {m = 1} ^ {infty} {frac {a (m)} {m ^ {s}}} ight) left ( sum _ {n = 1} ^ {infty} {frac {b (n)} {n ^ {s}}} ight).}$

Это простое упражнение, чтобы показать, что если c(п) определяется

${displaystyle c (n): = sum _ {ij = n} a (i) b (j) = sum _ {imid n} a (i) bleft ({frac {n} {i}} ight),}$

тогда

${displaystyle F_ {c} (s) = F_ {a} (s) F_ {b} (s).}$

Эта функция c называется Свертка Дирихле из а и б, и обозначается ${displaystyle a * b}$.

Особенно важным случаем является свертка с постоянной функцией а(п) = 1 для всех п, что соответствует умножению производящей функции на дзета-функцию:

${displaystyle g (n) = sum _ {dmid n} f (d).}$

Умножение на обратную дзета-функцию дает Инверсия Мёбиуса формула:

${displaystyle f (n) = sum _ {dmid n} mu left ({frac {n} {d}} ight) g (d).}$

Если ж мультипликативен, значит, тоже грамм. Если ж полностью мультипликативно, то грамм является мультипликативным, но может быть или не быть полностью мультипликативным.

Отношения между функциями

Существует множество формул, связывающих арифметические функции друг с другом и с функциями анализа, особенно степеней, корней, экспоненциальных и логарифмических функций. Страница тождества суммы делителей содержит много более общих и связанных примеров тождеств, включающих арифметические функции.

Вот несколько примеров:

Свёртки Дирихле

${displaystyle sum _ {delta mid n} mu (delta) = sum _ {delta mid n} lambda left ({frac {n} {delta}} ight) | mu (delta) | = {egin {case} 1 & {ext {if}} n = 1 0 & {ext {if}} neq 1end {case}}}$ куда λ - функция Лиувилля.^[12]

${displaystyle sum _ {delta mid n} varphi (delta) = n.}$      ^[13]

${displaystyle varphi (n) = sum _ {delta mid n} mu left ({frac {n} {delta}} ight) delta = nsum _ {delta mid n} {frac {mu (delta)} {delta}}. }$ Инверсия Мёбиуса

${displaystyle sum _ {dmid n} J_ {k} (d) = n ^ {k}.}$      ^[14]

${displaystyle J_ {k} (n) = sum _ {delta mid n} mu left ({frac {n} {delta}} ight) delta ^ {k} = n ^ {k} sum _ {delta mid n} { frac {mu (delta)} {delta ^ {k}}}.}$ Инверсия Мёбиуса

${displaystyle sum _ {delta mid n} delta ^ {s} J_ {r} (delta) J_ {s} left ({frac {n} {delta}} ight) = J_ {r + s} (n)}$      ^[15]

${displaystyle sum _ {delta mid n} varphi (delta) dleft ({frac {n} {delta}} ight) = sigma (n).}$      ^[16][17]

${displaystyle sum _ {delta mid n} | mu (delta) | = 2 ^ {omega (n)}.}$      ^[18]

${displaystyle | mu (n) | = sum _ {delta mid n} mu left ({frac {n} {delta}} ight) 2 ^ {omega (delta)}.}$ Инверсия Мёбиуса

${displaystyle sum _ {delta mid n} 2 ^ {omega (delta)} = d (n ^ {2}).}$      

${displaystyle 2 ^ {omega (n)} = sum _ {delta mid n} mu left ({frac {n} {delta}} ight) d (delta ^ {2}).}$ Инверсия Мёбиуса

${displaystyle sum _ {delta mid n} d (delta ^ {2}) = d ^ {2} (n).}$      

${displaystyle d (n ^ {2}) = sum _ {delta mid n} mu left ({frac {n} {delta}} ight) d ^ {2} (delta).}$ Инверсия Мёбиуса

${displaystyle sum _ {delta mid n} dleft ({frac {n} {delta}} ight) 2 ^ {omega (delta)} = d ^ {2} (n).}$      

${displaystyle sum _ {delta mid n} lambda (delta) = {egin {case} & 1 {ext {if}} n {ext {is a square}} & 0 {ext {if}} n {ext {не квадрат .}} конец {случаи}}}$ где λ - Функция Лиувилля.

${displaystyle sum _ {delta mid n} Лямбда (дельта) = log n.}$      ^[19]

${displaystyle Lambda (n) = sum _ {delta mid n} mu left ({frac {n} {delta}} ight) log (delta).}$ Инверсия Мёбиуса

Суммы квадратов

Для всех ${displaystyle kgeq 4, ;;; r_ {k} (n)> 0.}$     (Теорема Лагранжа о четырех квадратах ).

${displaystyle r_ {2} (n) = 4sum _ {dmid n} left ({frac {-4} {d}} ight),}$ ^[20]

где Символ Кронекера имеет ценности

${displaystyle left ({frac {-4} {n}} ight) = {egin {case} + 1 & {ext {if}} nequiv 1 {pmod {4}} - 1 & {ext {if}} nequiv 3 { pmod {4}} ;;; 0 & {ext {if}} n {ext {четно}}. end {case}}}$

Есть формула для r₃ в разделе о номера классов ниже.

${displaystyle r_ {4} (n) = 8sum _ {stackrel {dmid n} {4, mid, d}} d = 8 (2 + (- 1) ^ {n}) sum _ {stackrel {dmid n} { 2, mid, d}} d = {egin {case} 8sigma (n) & {ext {if}} n {ext {is odd}} 24sigma left ({frac {n} {2 ^ {u}}}) ight) & {ext {if}} n {ext {is even}} end {case}},}$    

куда ν = ν₂(п).    ^[21][22][23]

${displaystyle r_ {6} (n) = 16sum _ {dmid n} chi left ({frac {n} {d}} ight) d ^ {2} -4sum _ {dmid n} chi (d) d ^ {2 },}$

куда ${displaystyle chi (n) = left ({frac {-4} {n}} ight).}$^[24]

Определите функцию σ_k^*(п) в качестве^[25]

${displaystyle sigma _ {k} ^ {*} (n) = (- 1) ^ {n} sum _ {dmid n} (- 1) ^ {d} d ^ {k} = {egin {cases} sum _ {dmid n} d ^ {k} = sigma _ {k} (n) & {ext {if}} n {ext {is odd}} sum _ {stackrel {dmid n} {2, mid, d}} d ^ {k} -sum _ {stackrel {dmid n} {2, mid, d}} d ^ {k} & {ext {if}} n {ext {четно}}. end {case}}}$

То есть, если п странно, σ_k^*(п) это сумма k-ые степени делителей п, то есть, σ_k(п), и если п это даже сумма kй степени четных делителей п минус сумма k-ые степени нечетных делителей числа п.

${displaystyle r_ {8} (n) = 16sigma _ {3} ^ {*} (n).}$    ^[24][26]

Примите условность Рамануджана. τ(Икс) = 0, если Икс не является целым числом.

${displaystyle r_ {24} (n) = {frac {16} {691}} sigma _ {11} ^ {*} (n) + {frac {128} {691}} left {(- 1) ^ {n -1} 259 а.е. (n) -512 а.е. осталось ({frac {n} {2}} ight) ight}}$    ^[27]

Свертки суммы делителей

Здесь «свертка» не означает «свертку Дирихле», а вместо этого относится к формуле для коэффициентов произведение двух степенных рядов:

${displaystyle left (sum _ {n = 0} ^ {infty} a_ {n} x ^ {n} ight) left (sum _ {n = 0} ^ {infty} b_ {n} x ^ {n} ight) = сумма _ {i = 0} ^ {infty} сумма _ {j = 0} ^ {infty} a_ {i} b_ {j} x ^ {i + j} = sum _ {n = 0} ^ {infty} left (сумма _ {i = 0} ^ {n} a_ {i} b_ {ni} ight) x ^ {n} = sum _ {n = 0} ^ {infty} c_ {n} x ^ {n}. }$

Последовательность ${displaystyle c_ {n} = sum _ {i = 0} ^ {n} a_ {i} b_ {n-i}}$ называется свертка или Продукт Коши последовательностей а_п и б_п.
Видеть Серия Эйзенштейна для обсуждения серий и функциональных идентичностей, включенных в эти формулы.^[28]

${displaystyle sigma _ {3} (n) = {frac {1} {5}} left {6nsigma _ {1} (n) -sigma _ {1} (n) + 12sum _ {0$    ^[29]

${displaystyle sigma _ {5} (n) = {frac {1} {21}} left {10 (3n-1) sigma _ {3} (n) + sigma _ {1} (n) + 240sum _ {0$    ^[30]

${displaystyle {egin {align} sigma _ {7} (n) & = {frac {1} {20}} left {21 (2n-1) sigma _ {5} (n) -sigma _ {1} (n ) + 504sum _ {0$    ^[30][31]

${displaystyle {egin {align} sigma _ {9} (n) & = {frac {1} {11}} left {10 (3n-2) sigma _ {7} (n) + sigma _ {1} (n ) + 480sum _ {0$    ^[29][32]

${displaystyle au (n) = {frac {65} {756}} sigma _ {11} (n) + {frac {691} {756}} sigma _ {5} (n) - {frac {691} {3 }} сумма _ {0$ куда τ(п) - функция Рамануджана.^[33][34]

С σ_k(п) (для натурального числа k) и τ(п) являются целыми числами, приведенные выше формулы могут использоваться для доказательства сравнений^[35] для функций. Видеть Рамануджан тау функция для некоторых примеров.

Расширьте область действия функции разделения, установив п(0) = 1.

${displaystyle p (n) = {frac {1} {n}} sum _ {1leq kleq n} sigma (k) p (n-k).}$    ^[36] Это повторение можно использовать для вычисления п(п).

Номер класса, связанный

Питер Густав Лежен Дирихле обнаружил формулы, которые связывают номер класса час из поля квадратичных чисел к символу Якоби.^[37]

Целое число D называется основной дискриминант если это дискриминант поля квадратичных чисел. Это эквивалентно D ≠ 1 и либо а) D является свободный от квадратов и D ≡ 1 (мод.4) или б) D ≡ 0 (мод 4), D/ 4 не содержит квадратов, и D/ 4 ≡ 2 или 3 (мод 4).^[38]

Расширьте символ Якоби, чтобы он принимал четные числа в «знаменателе», определяя Символ Кронекера:

${displaystyle left ({frac {a} {2}} ight) = {egin {cases} ;;, 0 & {ext {if}} a {ext {is even}} (- 1) ^ {frac {a ^ {2} -1} {8}} & {ext {if}} a {ext {нечетное. }} конец {случаи}}}$

Тогда если D <−4 - фундаментальный дискриминант^[39][40]

${displaystyle {egin {align} h (D) & = {frac {1} {D}} sum _ {r = 1} ^ {| D |} rleft ({frac {D} {r}} ight) & = {frac {1} {2-left ({frac {D} {2}} ight)}} sum _ {r = 1} ^ {| D | / 2} left ({frac {D} {r}} ight) .end {выровнено}}}$

Также существует формула, относящаяся к р₃ и час. Опять же, пусть D быть фундаментальным дискриминантом, D <−4. потом^[41]

${displaystyle r_ {3} (| D |) = 12left (1-left ({frac {D} {2}} ight) ight) h (D).}$

Связанные с простым подсчетом

Позволять ${displaystyle H_ {n} = 1 + {frac {1} {2}} + {frac {1} {3}} + cdots + {frac {1} {n}}}$ быть пth номер гармоники. потом

${displaystyle sigma (n) leq H_ {n} + e ^ {H_ {n}} log H_ {n}}$ верно для любого натурального числа п если и только если Гипотеза Римана правда.^[42]

Гипотеза Римана также эквивалентна утверждению, что для всех п > 5040,

${displaystyle sigma (n)$ (где γ - Константа Эйлера – Маскерони ). Это Теорема Робина.

${displaystyle sum _ {p} u _ {p} (n) = Omega (n).}$

${displaystyle psi (x) = sum _ {nleq x} Lambda (n).}$    ^[43]

${displaystyle Pi (x) = sum _ {nleq x} {frac {Lambda (n)} {log n}}.}$    ^[44]

${displaystyle e ^ {heta (x)} = prod _ {pleq x} p.}$    ^[45]

${displaystyle e ^ {psi (x)} = имя оператора {lcm} [1,2, точки, lfloor xfloor].}$    ^[46]

Личность Менона

В 1965 г. П. Кесава Менон доказано^[47]

${displaystyle sum _ {stackrel {1leq kleq n} {gcd (k, n) = 1}} gcd (k-1, n) = varphi (n) d (n).}$

Это было обобщено рядом математиков. Например,

Б. Сьюри^[48]

${displaystyle sum _ {stackrel {1leq k_ {1}, k_ {2}, dots, k_ {s} leq n} {gcd (k_ {1}, n) = 1}} gcd (k_ {1} -1, k_ {2}, точки, k_ {s}, n) = varphi (n) sigma _ {s-1} (n).}$

Н. Рао^[49]

${displaystyle sum _ {stackrel {1leq k_ {1}, k_ {2}, dots, k_ {s} leq n} {gcd (k_ {1}, k_ {2}, dots, k_ {s}, n) = 1}} gcd (k_ {1} -a_ {1}, k_ {2} -a_ {2}, dots, k_ {s} -a_ {s}, n) ^ {s} = J_ {s} (n ) d (n),}$

куда а₁, а₂, ..., а_s целые числа, gcd (а₁, а₂, ..., а_s, п) = 1.

Ласло Фейес Тот^[50]

${displaystyle sum _ {stackrel {1leq kleq m} {gcd (k, m) = 1}} gcd (k ^ {2} -1, m_ {1}) gcd (k ^ {2} -1, m_ {2 }) = varphi (n) sum _ {stackrel {d_ {1} mid m_ {1}} {d_ {2} mid m_ {2}}} varphi (gcd (d_ {1}, d_ {2})) 2 ^ {омега (имя оператора {lcm} (d_ {1}, d_ {2}))},}$

куда м₁ и м₂ странные, м = lcm (м₁, м₂).

Фактически, если ж любая арифметическая функция^[51][52]

${displaystyle sum _ {stackrel {1leq kleq n} {gcd (k, n) = 1}} f (gcd (k-1, n)) = varphi (n) sum _ {dmid n} {frac {(mu * f) (d)} {varphi (d)}},}$

где * обозначает свертку Дирихле.

Разное

Позволять м и п быть четкими, нечетными и положительными. Тогда символ Якоби удовлетворяет закону квадратичная взаимность:

${displaystyle left ({frac {m} {n}} ight) left ({frac {n} {m}} ight) = (- 1) ^ {(m-1) (n-1) / 4}.}.$    

Позволять D(п) - арифметическая производная. Тогда логарифмическая производная

${displaystyle {frac {D (n)} {n}} = sum _ {stackrel {pmid n} {p {ext {prime}}}} {frac {v_ {p} (n)} {p}}}$ ^[53]

Позволять λ(п) - функция Лиувилля. потом

${displaystyle | lambda (n) | mu (n) = lambda (n) | mu (n) | = mu (n),}$ и

${displaystyle lambda (n) mu (n) = | mu (n) | = mu ^ {2} (n).}$    

Позволять λ(п) быть функцией Кармайкла. потом

${displaystyle lambda (n) mid phi (n).}$ Дальше,

${displaystyle lambda (n) = phi (n) {ext {тогда и только тогда, когда}} n = {egin {case} 1,2,4; 3,5,7,9,11, ldots {ext {(что есть,}} p ^ {k} {ext {, где}} p {ext {- нечетное простое число)}}; 6,10,14,18, ldots {ext {(то есть}} 2p ^ { k} {ext {, где}} p {ext {нечетное простое число)}}. end {case}}}$

Видеть Мультипликативная группа целых чисел по модулю n и Примитивный корень по модулю n. 

${displaystyle 2 ^ {omega (n)} leq d (n) leq 2 ^ {Omega (n)}.}$    ^[54][55]

${displaystyle {frac {6} {pi ^ {2}}} <{frac {phi (n) sigma (n)} {n ^ {2}}} <1.}$    ^[56]

${displaystyle {egin {выравнивается} c_ {q} (n) & = {frac {mu left ({frac {q} {gcd (q, n)}} ight)} {phi left ({frac {q} {gcd (q, n)}} ight)}} phi (q) & = sum _ {delta mid gcd (q, n)} mu left ({frac {q} {delta}} ight) delta .end {выровнено} }}$    ^[57] Обратите внимание, что${displaystyle phi (q) = sum _ {delta mid q} mu left ({frac {q} {delta}} ight) delta.}$    ^[58]

${displaystyle c_ {q} (1) = mu (q).}$

${displaystyle c_ {q} (q) = phi (q).}$

${displaystyle sum _ {delta mid n} d ^ {3} (delta) = left (sum _ {delta mid n} d (delta) ight) ^ {2}.}.}$    ^[59] Сравните это с 1³ + 2³ + 3³ + ... + п³ = (1 + 2 + 3 + ... + п)²

${displaystyle d (uv) = sum _ {delta mid gcd (u, v)} mu (delta) dleft ({frac {u} {delta}} ight) dleft ({frac {v} {delta}} ight). }$    ^[60]

${displaystyle sigma _ {k} (u) sigma _ {k} (v) = sum _ {delta mid gcd (u, v)} delta ^ {k} sigma _ {k} left ({frac {uv} {delta). ^ {2}}} право).}$    ^[61]

${displaystyle au (u) au (v) = sum _ {delta mid gcd (u, v)} delta ^ {11} au left ({frac {uv} {delta ^ {2}}} ight),}$ куда τ(п) - функция Рамануджана.^[62]

Первые 100 значений некоторых арифметических функций