Задачи и дополнения

1. Доказать следующее свойство функции Мёбиуса: μ(nm) = μ(n)μ(m) для любых взаимно простых n и m.

2. Функция f называется сумматорной функцией для g, если

(запись d\n означает, что суммирование распространяется на все различные делители числа n).

Показать, что сумматорная функция для функции Мёбиуса равна нулю при n > 1 и единице при n = 1.

3. Пусть f - сумматорная функция для g (см. задачу 2). Верна следующая замечательная формула обращения Мёбиуса, лежащая в основе всех приложений функции μ(n):

Действительно,

В получившейся двойной сумме изменим порядок суммирования. Заметим для этого, что аргумент к функции g(k) при двойном суммировании пробегает всевозможные делители числа n, и если k фиксировано, то d пробегает все делители n, которые в свою очередь делятся на k. Поэтому двойную сумму (4) можно переписать в виде:

при этом запись k\d\n обозначает, что d пробегает все делители n, делящиеся на k. Введем обозначения m = n/d и t = n/k, тогда m пробегает всевозможные делители t и в силу утверждения задачи 2

Следовательно,

Обращаясь теперь к выражению (5), мы видим, что в сумме по k

имеется лишь одно ненулевое слагаемое, отвечающее значению k = n, и потому

что равносильно (3).

4. Назовем число d периодом слова а, если а получается сочленением одинаковых слов длины d и не является сочленением одинаковых слов меньшей длины. Пусть Р_d(m) означает общее число слов длины n в алфавите из m символов, имеющих период d.

Убедиться, что

и, пользуясь формулой обращения (3), получить оценку (2).