В теории чисел широкое применение имеют комплекснозначные функции натурального аргумента, то есть функции, которые натуральным числам сопоставляют комплексные числа. Подкласс таких функций составляют мультипликативные функции, то есть такие, что для любых чисел a, b, таких, что НОД(a, b) = 1 (их обычно называют взаимно простыми), f(a*b) = f(a) * f(b). Например, функция возведения числа в фиксированную степень является мультипликативной функцией. Вот такое простое определение.

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

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

Среди мультипликативных функций есть несколько интересных, например: функция, возвращающая количество делителей натурального числа (обычно обозначается буквой τ), функция, возвращающая сумму делителей натурального числа (обозначается буквой σ), функция id, возвращающая само число и многие другие. Наиболее важные функции – функция Мёбиуса и функция Эйлера.

Функция Мёбиуса μ(n) – функция, которая возвращает 0, если n делится на квадрат некоторого простого числа; 1, если не делится делится и в его разложении четное число сомножителей, -1 ˜– если нечетное. Эта функция примечательна тем, что если для некоторого n просуммировать значение μ(d) по всем делителям n, то получится 0 (например, для 12: μ(1) + μ(2) + μ(3) + μ(4) + μ(6) + μ(12) = 1 - 1 - 1 + 0 + 1 = 0). Также эта функция связана со всем остальными мультипликативными функциями формулой обращения Мёбиуса (но эт надо объяснить, что есть свертка Дирихле, так что в другой раз), решетом Эратосфена и еще с дзета-функцией Римана.



Функция Эйлера φ(n) возвращает количество натуральных чисел меньше n, взаимно простых с ним. И вот эта функция – настоящая жемчужина теории чисел. При помощи нее можно так дохера всего доказать, что вам и не снилось, а еще с ней связано куча нетривиальных фактов, для доказательства которых нужно владение методами математического анализа (ну и ТФКП желательно), она используется в шифровании с открытым ключом RSA, помогает решать линейные сравнения и с ней связано несколько открытых проблем математики.



В общем, вот такие вот прикольные и полезные штуки эти мультипликативные арифметические функции.

Спасибо за то, что вы с нами.
С любовью, Рителлинг favorite