Главная > Математика > Дискретная математика. Алгоритмы и программы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

8.8. Функция Мебиуса. Формула обращения Мёбиуса

• Определение. Функция Мёбиуса определяется для всех целых положительных и равна

где разложение на простые сомножители, простые числа, — кратность в разложении.

Пример.

• Лемма 8.8.1.

где суммирование идет по всем делителям числа Доказательство. Если то Пусть теперь разложение на простые сомножители. Тогда Все делители для которых имеют вид Количество таких делителей выбираемых из равно числу сочетаний

• Теорема 8.8.1. Формула обращения Мёбиуса:

где функции, определенные для всех целых положительных

Доказательство. Выполним подстановку в сумме Заметим, что здесь число неявно рассматривается в виде произведения где делители и 5 принимают все допустимые значения независимо друг от друга и порядок суммирования не влияет на значение суммы, т. е.

это вследствие леммы 8.8.1. Тогда

Задача. Установить связь функций Эйлера и Мёбиуса

Решение. свойство 4 функции Эйлера (см. п. 8.7). К данной сумме применим формулу обращения Мёбиуса:

Например, для имеем все делители наконец, выражение в этом случае примет вид

Пусть разложение на простые множители. Так как свойство 3 функции Эйлера (см. п. 8.7),

ЗАДАЧИ И УПРАЖНЕНИЯ

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление