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

В теории чисел — арифметическая , арифметическая или теоретико-числовая функция. Обычно это любая функция f ( n ), областью определения которой являются целые положительные числа , а диапазоном значений является подмножество комплексных чисел . Харди и Райт включили в свое определение требование, чтобы арифметическая функция «выражала некоторое арифметическое свойство n ». Существует более широкий класс теоретико-числовых функций, которые не подходят под это определение, например функции подсчета простых чисел . В этой статье приведены ссылки на функции обоих классов.

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

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

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

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

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

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

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

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

Обозначения

В этой статье, ${\textstyle \sum _{p}f(p)}$ и ${\textstyle \prod _{p}f(p)}$ означают, что сумма или произведение относится ко всем простым числам :

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

и

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

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

$$\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 .$$

Обозначения ${\textstyle \sum _{d\mid n}f(d)}$ и ${\textstyle \prod _{d\mid n}f(d)}$означают, что сумма или произведение вычисляется по всем положительным делителям n , включая 1 и n . Например, если n = 12 , то

$$\prod _{d\mid 12}f(d)=f(1)f(2)f(3)f(4)f(6)f(12).$$

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

$$\sum _{p\mid 18}f(p)=f(2)+f(3),$$

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

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

Ω( n ), ω ( n ), ν _p ( n ) – разложение по простым степеням

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

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

$$n=\prod _{p}p^{\nu _{p}(n)}.$$

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

ω ( п ) знак равно k ,

Ω( п ) знак равно а ₁ + а ₂ + ... + а _k .

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

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

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

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

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

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

$$\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}\right).$$

Установка k = 0 во втором произведении дает

$$\tau (n)=d(n)=(1+a_{1})(1+a_{2})\cdots (1+a_{\omega (n)}).$$

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

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

$$\varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)=n\left({\frac {p_{1}-1}{p_{1}}}\right)\left({\frac {p_{2}-1}{p_{2}}}\right)\cdots \left({\frac {p_{\omega (n)}-1}{p_{\omega (n)}}}\right).$$

J _k ( n ) – Жордановая функция тотента

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

$$J_{k}(n)=n^{k}\prod _{p\mid n}\left(1-{\frac {1}{p^{k}}}\right)=n^{k}\left({\frac {p_{1}^{k}-1}{p_{1}^{k}}}\right)\left({\frac {p_{2}^{k}-1}{p_{2}^{k}}}\right)\cdots \left({\frac {p_{\omega (n)}^{k}-1}{p_{\omega (n)}^{k}}}\right).$$

μ( n ) – функция Мёбиуса

µ( n ) , функция Мёбиуса, важна из-за формулы обращения Мёбиуса . См. свертку Дирихле ниже.

$$\mu (n)={\begin{cases}(-1)^{\omega (n)}=(-1)^{\Omega (n)}&{\text{if }}\;\omega (n)=\Omega (n)\\0&{\text{if }}\;\omega (n)\neq \Omega (n).\end{cases}}$$

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

τ( n ) – ваша функция Рамануджана

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

$$\sum _{n\geq 1}\tau (n)q^{n}=q\prod _{n\geq 1}(1-q^{n})^{24}.$$

Хотя трудно сказать, какое именно «арифметическое свойство n » оно «выражает», ( τ ( n ) равно (2π) ⁻¹² умноженное на n -й коэффициент Фурье в q-разложении модульной дискриминантной функции) он включен в число арифметических функций, поскольку он мультипликативен и встречается в тождествах, включающих определенные функции σk _n ) и rk ( ₍ n ) (поскольку они также являются коэффициентами в разложении модулярных форм ).

c _q ( n ) – сумма Рамануджана

c _q ( n ) , сумма Рамануджана, представляет собой сумму n -х степеней примитивных корней q -й степени из единицы :

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

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

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

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

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

$$\psi (n)=n\prod _{p|n}\left(1+{\frac {1}{p}}\right).$$

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

λ( n ) – функция Лиувилля

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

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

χ ( n ) – символы

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

Главный характер (mod n ) обозначается χ ₀ ( a ) (или χ ₁ ( a )). Это определяется как

$$\chi _{0}(a)={\begin{cases}1&{\text{if }}\gcd(a,n)=1,\\0&{\text{if }}\gcd(a,n)\neq 1.\end{cases}}$$

Квадратичный характер (mod n ) обозначается символом Якоби для нечетного n он не определен (для четного n ):

$$\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{a_{1}}\left({\frac {a}{p_{2}}}\right)^{a_{2}}\cdots \left({\frac {a}{p_{\omega (n)}}}\right)^{a_{\omega (n)}}.$$

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

$$\left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{if }}a\equiv 0{\pmod {p}},\\+1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x,\;a\equiv x^{2}{\pmod {p}}\\-1&{\text{if there is no such }}x.\end{cases}}$$

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

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

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

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

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

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

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

ν _p ( n ) – p -адическая оценка целого числа n

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

Логарифмическая производная

$\operatorname {ld} (n)={\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}$, где $D(n)$ является арифметической производной.

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

π ( x ), Π ( x ), θ ( x ), ψ ( x ) – функции счета простых чисел

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

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

$$\pi (x)=\sum _{p\leq x}1$$

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

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

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

$$\vartheta (x)=\sum _{p\leq x}\log p,$$

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

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

Λ( n –

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

$$\Lambda (n)={\begin{cases}\log p&{\text{if }}n=2,3,4,5,7,8,9,11,13,16,\ldots =p^{k}{\text{ is a prime power}}\\0&{\text{if }}n=1,6,10,12,14,15,18,20,21,\dots \;\;\;\;{\text{ is not a prime power}}.\end{cases}}$$

p ( n ) – функция разделения

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

$$p(n)=\left|\left\{(a_{1},a_{2},\dots a_{k}):0<a_{1}\leq a_{2}\leq \cdots \leq a_{k}\;\land \;n=a_{1}+a_{2}+\cdots +a_{k}\right\}\right|.$$

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

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

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

$$\lambda (n)={\begin{cases}\;\;\phi (n)&{\text{if }}n=2,3,4,5,7,9,11,13,17,19,23,25,27,\dots \\{\tfrac {1}{2}}\phi (n)&{\text{if }}n=8,16,32,64,\dots \end{cases}}$$

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

$$\lambda (p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}})=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})].$$

h ( n ) – Номер класса

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

r _k ( n ) – Сумма k квадратов

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

$$r_{k}(n)=\left|\left\{(a_{1},a_{2},\dots ,a_{k}):n=a_{1}^{2}+a_{2}^{2}+\cdots +a_{k}^{2}\right\}\right|$$

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

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

• $D(n)=1$ если n простое, и
• $D(mn)=mD(n)+D(m)n$ ( правило продукта )

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

Учитывая арифметическую функцию a ( n ), ее функция суммирования A ( x ) определяется выражением

$$A(x):=\sum _{n\leq x}a(n).$$

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

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

$$A_{0}(m):={\frac {1}{2}}\left(\sum _{n<m}a(n)+\sum _{n\leq m}a(n)\right)=A(m)-{\frac {1}{2}}a(m).$$

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

Классический пример этого явления задается суммирующей функцией делителей , функцией суммирования d ( n ), количеством делителей n :

$$\liminf _{n\to \infty }d(n)=2$$

$$\limsup _{n\to \infty }{\frac {\log d(n)\log \log n}{\log n}}=\log 2$$

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

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

$$\sum _{n\leq x}f(n)\sim \sum _{n\leq x}g(n)$$

поскольку x стремится к бесконечности. Пример выше показывает, что d ( n ) имеет средний порядок log( n ).

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

Учитывая арифметическую функцию a ( n ), пусть F _a ( s ) для комплексного s будет функцией, определяемой соответствующим рядом Дирихле (где он сходится ):

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

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

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

$$\zeta (s)\,\sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}=1,\;\;\Re s>1.$$

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

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

Несложно показать, что если c ( n ) определяется формулой

$$c(n):=\sum _{ij=n}a(i)b(j)=\sum _{i\mid n}a(i)b\left({\frac {n}{i}}\right),$$

затем

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

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

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

$$g(n)=\sum _{d\mid n}f(d).$$

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

$$f(n)=\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)g(d).$$

Если f мультипликативен, то и g мультипликативен . Если f полностью мультипликативен, то g мультипликативен, но может быть или не быть полностью мультипликативным.

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

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

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

Извилины Дирихле

$\sum _{\delta \mid n}\mu (\delta )=\sum _{\delta \mid n}\lambda \left({\frac {n}{\delta }}\right)|\mu (\delta )|={\begin{cases}1&{\text{if }}n=1\\0&{\text{if }}n\neq 1\end{cases}}$ где λ — функция Лиувилля.

$\sum _{\delta \mid n}\varphi (\delta )=n.$      

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

$\sum _{d\mid n}J_{k}(d)=n^{k}.$      

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

$\sum _{\delta \mid n}\delta ^{s}J_{r}(\delta )J_{s}\left({\frac {n}{\delta }}\right)=J_{r+s}(n)$      

$\sum _{\delta \mid n}\varphi (\delta )d\left({\frac {n}{\delta }}\right)=\sigma (n).$      

$\sum _{\delta \mid n}|\mu (\delta )|=2^{\omega (n)}.$      

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

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

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

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

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

$\sum _{\delta \mid n}d\left({\frac {n}{\delta }}\right)2^{\omega (\delta )}=d^{2}(n).$      

$\sum _{\delta \mid n}\lambda (\delta )={\begin{cases}&1{\text{ if }}n{\text{ is a square }}\\&0{\text{ if }}n{\text{ is not square.}}\end{cases}}$ где λ — функция Лиувилля .

$\sum _{\delta \mid n}\Lambda (\delta )=\log n.$      

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

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

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

$r_{2}(n)=4\sum _{d\mid n}\left({\frac {-4}{d}}\right),$

где символ Кронекера имеет значения

$\left({\frac {-4}{n}}\right)={\begin{cases}+1&{\text{if }}n\equiv 1{\pmod {4}}\\-1&{\text{if }}n\equiv 3{\pmod {4}}\\\;\;\;0&{\text{if }}n{\text{ is even}}.\\\end{cases}}$

Формула для r ₃ приведена в разделе о числах классов ниже.

$$r_{4}(n)=8\sum _{\stackrel {d\mid n}{4\,\nmid \,d}}d=8(2+(-1)^{n})\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d={\begin{cases}8\sigma (n)&{\text{if }}n{\text{ is odd }}\\24\sigma \left({\frac {n}{2^{\nu }}}\right)&{\text{if }}n{\text{ is even }}\end{cases}},$$

где ν знак равно ν ₂ ( п ) .

$$r_{6}(n)=16\sum _{d\mid n}\chi \left({\frac {n}{d}}\right)d^{2}-4\sum _{d\mid n}\chi (d)d^{2},$$

где $\chi (n)=\left({\frac {-4}{n}}\right).$

Определим функцию σ _k ^* ( н ) как

$$\sigma _{k}^{*}(n)=(-1)^{n}\sum _{d\mid n}(-1)^{d}d^{k}={\begin{cases}\sum _{d\mid n}d^{k}=\sigma _{k}(n)&{\text{if }}n{\text{ is odd }}\\\sum _{\stackrel {d\mid n}{2\,\mid \,d}}d^{k}-\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d^{k}&{\text{if }}n{\text{ is even}}.\end{cases}}$$

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

$r_{8}(n)=16\sigma _{3}^{*}(n).$    

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

$r_{24}(n)={\frac {16}{691}}\sigma _{11}^{*}(n)+{\frac {128}{691}}\left\{(-1)^{n-1}259\tau (n)-512\tau \left({\frac {n}{2}}\right)\right\}$    

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

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

$\left(\sum _{n=0}^{\infty }a_{n}x^{n}\right)\left(\sum _{n=0}^{\infty }b_{n}x^{n}\right)=\sum _{i=0}^{\infty }\sum _{j=0}^{\infty }a_{i}b_{j}x^{i+j}=\sum _{n=0}^{\infty }\left(\sum _{i=0}^{n}a_{i}b_{n-i}\right)x^{n}=\sum _{n=0}^{\infty }c_{n}x^{n}.$

Последовательность $c_{n}=\sum _{i=0}^{n}a_{i}b_{n-i}$ называется сверткой или произведением Коши последовательностей a _n и b _n .
Эти формулы могут быть доказаны аналитически (см. ряды Эйзенштейна ) или элементарными методами.

$\sigma _{3}(n)={\frac {1}{5}}\left\{6n\sigma _{1}(n)-\sigma _{1}(n)+12\sum _{0<k<n}\sigma _{1}(k)\sigma _{1}(n-k)\right\}.$    

$\sigma _{5}(n)={\frac {1}{21}}\left\{10(3n-1)\sigma _{3}(n)+\sigma _{1}(n)+240\sum _{0<k<n}\sigma _{1}(k)\sigma _{3}(n-k)\right\}.$    

${\begin{aligned}\sigma _{7}(n)&={\frac {1}{20}}\left\{21(2n-1)\sigma _{5}(n)-\sigma _{1}(n)+504\sum _{0<k<n}\sigma _{1}(k)\sigma _{5}(n-k)\right\}\\&=\sigma _{3}(n)+120\sum _{0<k<n}\sigma _{3}(k)\sigma _{3}(n-k).\end{aligned}}$    

${\begin{aligned}\sigma _{9}(n)&={\frac {1}{11}}\left\{10(3n-2)\sigma _{7}(n)+\sigma _{1}(n)+480\sum _{0<k<n}\sigma _{1}(k)\sigma _{7}(n-k)\right\}\\&={\frac {1}{11}}\left\{21\sigma _{5}(n)-10\sigma _{3}(n)+5040\sum _{0<k<n}\sigma _{3}(k)\sigma _{5}(n-k)\right\}.\end{aligned}}$    

$\tau (n)={\frac {65}{756}}\sigma _{11}(n)+{\frac {691}{756}}\sigma _{5}(n)-{\frac {691}{3}}\sum _{0<k<n}\sigma _{5}(k)\sigma _{5}(n-k),$ где τ ( n ) — функция Рамануджана.

Поскольку σ _k ( n ) (для натурального числа k ) и τ ( n ) являются целыми числами, приведенные выше формулы можно использовать для доказательства сравнений. для функций. см . в функции Тау Рамануджана Некоторые примеры .

Расширьте область определения статистической суммы, установив p (0) = 1.

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

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

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

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

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

$$\left({\frac {a}{2}}\right)={\begin{cases}\;\;\,0&{\text{ if }}a{\text{ is even}}\\(-1)^{\frac {a^{2}-1}{8}}&{\text{ if }}a{\text{ is odd. }}\end{cases}}$$

Тогда если D < −4 — фундаментальный дискриминант

$${\begin{aligned}h(D)&={\frac {1}{D}}\sum _{r=1}^{|D|}r\left({\frac {D}{r}}\right)\\&={\frac {1}{2-\left({\tfrac {D}{2}}\right)}}\sum _{r=1}^{|D|/2}\left({\frac {D}{r}}\right).\end{aligned}}$$

Существует также формула, связывающая r ₃ и h . Опять же, пусть D — фундаментальный дискриминант, D < −4. Затем

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

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

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

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

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

$$\sigma (n)<e^{\gamma }n\log \log n$$

(где γ — постоянная Эйлера–Машерони ). Это теорема Робина .

$\sum _{p}\nu _{p}(n)=\Omega (n).$

$\psi (x)=\sum _{n\leq x}\Lambda (n).$    

$\Pi (x)=\sum _{n\leq x}{\frac {\Lambda (n)}{\log n}}.$    

$e^{\theta (x)}=\prod _{p\leq x}p.$    

$e^{\psi (x)}=\operatorname {lcm} [1,2,\dots ,\lfloor x\rfloor ].$    

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

В 1965 году П. Кесава Менон доказал

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

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

• Б. Сури
  $$\sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{\gcd(k_{1},n)=1}}\gcd(k_{1}-1,k_{2},\dots ,k_{s},n)=\varphi (n)\sigma _{s-1}(n).$$
• Н. Рао
  $$\sum _{\stackrel {1\leq 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),$$
  где a ₁ , a ₂ , ..., a _s — целые числа, НОД( a ₁ , a ₂ , ..., a _s , n ) = 1.
• Тот Ласло Фейес
  $$\sum _{\stackrel {1\leq k\leq 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^{\omega (\operatorname {lcm} (d_{1},d_{2}))},$$
  где m ₁ и m ₂ нечетны, m = lcm( m ₁ , m ₂ ).

Действительно, если f — любая арифметическая функция

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

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

Разное

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

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

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

$${\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}.$$

см . в разделе «Арифметическая производная» Подробности .

Пусть λ ( n ) — функция Лиувилля. Затем

$|\lambda (n)|\mu (n)=\lambda (n)|\mu (n)|=\mu (n),$ и

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

Пусть λ ( n ) — функция Кармайкла. Затем

$\lambda (n)\mid \phi (n).$ Дальше,

$\lambda (n)=\phi (n){\text{ if and only if }}n={\begin{cases}1,2,4;\\3,5,7,9,11,\ldots {\text{ (that is, }}p^{k}{\text{, where }}p{\text{ is an odd prime)}};\\6,10,14,18,\ldots {\text{ (that is, }}2p^{k}{\text{, where }}p{\text{ is an odd prime)}}.\end{cases}}$

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

$2^{\omega (n)}\leq d(n)\leq 2^{\Omega (n)}.$    

${\frac {6}{\pi ^{2}}}<{\frac {\phi (n)\sigma (n)}{n^{2}}}<1.$    

${\begin{aligned}c_{q}(n)&={\frac {\mu \left({\frac {q}{\gcd(q,n)}}\right)}{\phi \left({\frac {q}{\gcd(q,n)}}\right)}}\phi (q)\\&=\sum _{\delta \mid \gcd(q,n)}\mu \left({\frac {q}{\delta }}\right)\delta .\end{aligned}}$     Обратите внимание, что $\phi (q)=\sum _{\delta \mid q}\mu \left({\frac {q}{\delta }}\right)\delta .$    

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

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

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

$d(uv)=\sum _{\delta \mid \gcd(u,v)}\mu (\delta )d\left({\frac {u}{\delta }}\right)d\left({\frac {v}{\delta }}\right).$    

$\sigma _{k}(u)\sigma _{k}(v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{k}\sigma _{k}\left({\frac {uv}{\delta ^{2}}}\right).$    

$\tau (u)\tau (v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{11}\tau \left({\frac {uv}{\delta ^{2}}}\right),$ где τ ( n ) — функция Рамануджана.

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

н	факторизация	𝜙( п )	ω ( п )	Ом ( п )	𝜆( п )	𝜇( п )	𝛬( п )	п ( п )	𝜎 0 ( п )	𝜎 1 ( п )	𝜎 2 ( п )	р 2 ( п )	р 3 ( п )	р 4 ( п )
1	1	1	0	0	1	1	0	0	1	1	1	4	6	8
2	2	1	1	1	−1	−1	0.69	1	2	3	5	4	12	24
3	3	2	1	1	−1	−1	1.10	2	2	4	10	0	8	32
4	2 2	2	1	2	1	0	0.69	2	3	7	21	4	6	24
5	5	4	1	1	−1	−1	1.61	3	2	6	26	8	24	48
6	2 · 3	2	2	2	1	1	0	3	4	12	50	0	24	96
7	7	6	1	1	−1	−1	1.95	4	2	8	50	0	0	64
8	2 3	4	1	3	−1	0	0.69	4	4	15	85	4	12	24
9	3 2	6	1	2	1	0	1.10	4	3	13	91	4	30	104
10	2 · 5	4	2	2	1	1	0	4	4	18	130	8	24	144
11	11	10	1	1	−1	−1	2.40	5	2	12	122	0	24	96
12	2 2 · 3	4	2	3	−1	0	0	5	6	28	210	0	8	96
13	13	12	1	1	−1	−1	2.56	6	2	14	170	8	24	112
14	2 · 7	6	2	2	1	1	0	6	4	24	250	0	48	192
15	3 · 5	8	2	2	1	1	0	6	4	24	260	0	0	192
16	2 4	8	1	4	1	0	0.69	6	5	31	341	4	6	24
17	17	16	1	1	−1	−1	2.83	7	2	18	290	8	48	144
18	2 · 3 2	6	2	3	−1	0	0	7	6	39	455	4	36	312
19	19	18	1	1	−1	−1	2.94	8	2	20	362	0	24	160
20	2 2 · 5	8	2	3	−1	0	0	8	6	42	546	8	24	144
21	3 · 7	12	2	2	1	1	0	8	4	32	500	0	48	256
22	2 · 11	10	2	2	1	1	0	8	4	36	610	0	24	288
23	23	22	1	1	−1	−1	3.14	9	2	24	530	0	0	192
24	2 3 · 3	8	2	4	1	0	0	9	8	60	850	0	24	96
25	5 2	20	1	2	1	0	1.61	9	3	31	651	12	30	248
26	2 · 13	12	2	2	1	1	0	9	4	42	850	8	72	336
27	3 3	18	1	3	−1	0	1.10	9	4	40	820	0	32	320
28	2 2 · 7	12	2	3	−1	0	0	9	6	56	1050	0	0	192
29	29	28	1	1	−1	−1	3.37	10	2	30	842	8	72	240
30	2 · 3 · 5	8	3	3	−1	−1	0	10	8	72	1300	0	48	576
31	31	30	1	1	−1	−1	3.43	11	2	32	962	0	0	256
32	2 5	16	1	5	−1	0	0.69	11	6	63	1365	4	12	24
33	3 · 11	20	2	2	1	1	0	11	4	48	1220	0	48	384
34	2 · 17	16	2	2	1	1	0	11	4	54	1450	8	48	432
35	5 · 7	24	2	2	1	1	0	11	4	48	1300	0	48	384
36	2 2 · 3 2	12	2	4	1	0	0	11	9	91	1911	4	30	312
37	37	36	1	1	−1	−1	3.61	12	2	38	1370	8	24	304
38	2 · 19	18	2	2	1	1	0	12	4	60	1810	0	72	480
39	3 · 13	24	2	2	1	1	0	12	4	56	1700	0	0	448
40	2 3 · 5	16	2	4	1	0	0	12	8	90	2210	8	24	144
41	41	40	1	1	−1	−1	3.71	13	2	42	1682	8	96	336
42	2 · 3 · 7	12	3	3	−1	−1	0	13	8	96	2500	0	48	768
43	43	42	1	1	−1	−1	3.76	14	2	44	1850	0	24	352
44	2 2 · 11	20	2	3	−1	0	0	14	6	84	2562	0	24	288
45	3 2 · 5	24	2	3	−1	0	0	14	6	78	2366	8	72	624
46	2 · 23	22	2	2	1	1	0	14	4	72	2650	0	48	576
47	47	46	1	1	−1	−1	3.85	15	2	48	2210	0	0	384
48	2 4 · 3	16	2	5	−1	0	0	15	10	124	3410	0	8	96
49	7 2	42	1	2	1	0	1.95	15	3	57	2451	4	54	456
50	2 · 5 2	20	2	3	−1	0	0	15	6	93	3255	12	84	744
51	3 · 17	32	2	2	1	1	0	15	4	72	2900	0	48	576
52	2 2 · 13	24	2	3	−1	0	0	15	6	98	3570	8	24	336
53	53	52	1	1	−1	−1	3.97	16	2	54	2810	8	72	432
54	2 · 3 3	18	2	4	1	0	0	16	8	120	4100	0	96	960
55	5 · 11	40	2	2	1	1	0	16	4	72	3172	0	0	576
56	2 3 · 7	24	2	4	1	0	0	16	8	120	4250	0	48	192
57	3 · 19	36	2	2	1	1	0	16	4	80	3620	0	48	640
58	2 · 29	28	2	2	1	1	0	16	4	90	4210	8	24	720
59	59	58	1	1	−1	−1	4.08	17	2	60	3482	0	72	480
60	2 2 · 3 · 5	16	3	4	1	0	0	17	12	168	5460	0	0	576
61	61	60	1	1	−1	−1	4.11	18	2	62	3722	8	72	496
62	2 · 31	30	2	2	1	1	0	18	4	96	4810	0	96	768
63	3 2 · 7	36	2	3	−1	0	0	18	6	104	4550	0	0	832
64	2 6	32	1	6	1	0	0.69	18	7	127	5461	4	6	24
65	5 · 13	48	2	2	1	1	0	18	4	84	4420	16	96	672
66	2 · 3 · 11	20	3	3	−1	−1	0	18	8	144	6100	0	96	1152
67	67	66	1	1	−1	−1	4.20	19	2	68	4490	0	24	544
68	2 2 · 17	32	2	3	−1	0	0	19	6	126	6090	8	48	432
69	3 · 23	44	2	2	1	1	0	19	4	96	5300	0	96	768
70	2 · 5 · 7	24	3	3	−1	−1	0	19	8	144	6500	0	48	1152
71	71	70	1	1	−1	−1	4.26	20	2	72	5042	0	0	576
72	2 3 · 3 2	24	2	5	−1	0	0	20	12	195	7735	4	36	312
73	73	72	1	1	−1	−1	4.29	21	2	74	5330	8	48	592
74	2 · 37	36	2	2	1	1	0	21	4	114	6850	8	120	912
75	3 · 5 2	40	2	3	−1	0	0	21	6	124	6510	0	56	992
76	2 2 · 19	36	2	3	−1	0	0	21	6	140	7602	0	24	480
77	7 · 11	60	2	2	1	1	0	21	4	96	6100	0	96	768
78	2 · 3 · 13	24	3	3	−1	−1	0	21	8	168	8500	0	48	1344
79	79	78	1	1	−1	−1	4.37	22	2	80	6242	0	0	640
80	2 4 · 5	32	2	5	−1	0	0	22	10	186	8866	8	24	144
81	3 4	54	1	4	1	0	1.10	22	5	121	7381	4	102	968
82	2 · 41	40	2	2	1	1	0	22	4	126	8410	8	48	1008
83	83	82	1	1	−1	−1	4.42	23	2	84	6890	0	72	672
84	2 2 · 3 · 7	24	3	4	1	0	0	23	12	224	10500	0	48	768
85	5 · 17	64	2	2	1	1	0	23	4	108	7540	16	48	864
86	2 · 43	42	2	2	1	1	0	23	4	132	9250	0	120	1056
87	3 · 29	56	2	2	1	1	0	23	4	120	8420	0	0	960
88	2 3 · 11	40	2	4	1	0	0	23	8	180	10370	0	24	288
89	89	88	1	1	−1	−1	4.49	24	2	90	7922	8	144	720
90	2 · 3 2 · 5	24	3	4	1	0	0	24	12	234	11830	8	120	1872
91	7 · 13	72	2	2	1	1	0	24	4	112	8500	0	48	896
92	2 2 · 23	44	2	3	−1	0	0	24	6	168	11130	0	0	576
93	3 · 31	60	2	2	1	1	0	24	4	128	9620	0	48	1024
94	2 · 47	46	2	2	1	1	0	24	4	144	11050	0	96	1152
95	5 · 19	72	2	2	1	1	0	24	4	120	9412	0	0	960
96	2 5 · 3	32	2	6	1	0	0	24	12	252	13650	0	24	96
97	97	96	1	1	−1	−1	4.57	25	2	98	9410	8	48	784
98	2 · 7 2	42	2	3	−1	0	0	25	6	171	12255	4	108	1368
99	3 2 · 11	60	2	3	−1	0	0	25	6	156	11102	0	72	1248
100	2 2 · 5 2	40	2	4	1	0	0	25	9	217	13671	12	30	744
н	факторизация	𝜙( п )	ω ( п )	Ом ( п )	𝜆( п )	𝜇( п )	𝛬( п )	п ( п )	𝜎 0 ( п )	𝜎 1 ( п )	𝜎 2 ( п )	р 2 ( п )	р 3 ( п )	р 4 ( п )

Ссылки

• Том М. Апостол (1976), Введение в аналитическую теорию чисел , Тексты для студентов Springer по математике , ISBN  0-387-90163-9
• Апостол, Том М. (1989), Модульные функции и ряды Дирихле в теории чисел (2-е издание) , Нью-Йорк: Springer, ISBN  0-387-97127-0
• Бейтман, Пол Т .; Даймонд, Гарольд Г. (2004), Аналитическая теория чисел, введение , World Scientific , ISBN  978-981-238-938-1
• Коэн, Анри (1993), Курс вычислительной алгебраической теории чисел , Берлин: Springer , ISBN  3-540-55640-0
• Эдвардс, Гарольд (1977). Великая теорема Ферма . Нью-Йорк: Спрингер . ISBN  0-387-90230-9 .
• Харди, GH (1999), Рамануджан: Двенадцать лекций по темам, предложенным его жизнью и работой , Провиденс, Род-Айленд: AMS / Челси, hdl : 10115/1436 , ISBN  978-0-8218-2023-0
• Харди, штат Джорджия ; Райт, Э.М. (1979) [1938]. Введение в теорию чисел (5-е изд.). Оксфорд: Кларендон Пресс. ISBN  0-19-853171-0 . МР   0568909 . Збл   0423.10001 .
• Джеймсон, GJO (2003), Теорема о простых числах , издательство Кембриджского университета, ISBN  0-521-89110-8
• Коблиц, Нил (1984), Введение в эллиптические кривые и модульные формы , Нью-Йорк: Springer, ISBN  0-387-97966-2
• Ландау, Эдмунд (1966), Элементарная теория чисел , Нью-Йорк: Челси
• Уильям Дж. ЛеВек (1996), Основы теории чисел , Courier Dover Publications, ISBN  0-486-68906-9
• Лонг, Кэлвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: DC Heath and Company , LCCN   77-171950
• Эллиот Мендельсон (1987), Введение в математическую логику , CRC Press, ISBN  0-412-80830-7
• Нагелл, Трюгве (1964), Введение в теорию чисел (2-е издание) , Челси, ISBN  978-0-8218-2833-5
• Нивен Иван М. ; Цукерман, Герберт С. (1972), Введение в теорию чисел (3-е издание) , John Wiley & Sons , ISBN  0-471-64154-5
• Петтофреззо, Энтони Дж.; Биркит, Дональд Р. (1970), Элементы теории чисел , Энглвуд Клиффс: Прентис Холл , LCCN   77-81766
• Рамануджан, Шриниваса (2000), Сборник статей , Провиденс, Род-Айленд: AMS / Челси, ISBN  978-0-8218-2076-6
• Уильямс, Кеннет С. (2011), Теория чисел в духе Лиувилля , Тексты для студентов Лондонского математического общества, том. 76, Кембридж: Издательство Кембриджского университета , ISBN  978-0-521-17562-3 , Збл   1227.11002

Дальнейшее чтение

• Шварц, Вольфганг; Спилкер, Юрген (1994), Арифметические функции. Введение в элементарные и аналитические свойства арифметических функций и в некоторые из их почти периодических свойств , Серия лекций Лондонского математического общества, том. 184, Издательство Кембриджского университета , ISBN  0-521-42725-8 , Збл   0807.11001

Внешние ссылки

• «Арифметическая функция» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Мэтью Холден, Майкл Оррисон, Майкл Варбл Еще одно обобщение функции тотента Эйлера
• Хуард, Оу, Спирмен и Уильямс. Элементарное вычисление некоторых сумм свертки с использованием функций делителей
• Динева, Розика, Тотент Эйлера, Мёбиуса и функции делителя. Архивировано 16 января 2021 г. в Wayback Machine.
• Ласло Тот, Тождество Менона и арифметические суммы, представляющие функции нескольких переменных