Лекция 06. Формула обращения Мёбиуса. Сравнения и их свойства

• Формула обращения Мёбиуса позволяет менять порядок слагаемых в сумме.  

• Функция Мёбиуса определяется как 1, если n = 1, 0, если n простое, и -1 в степени p, если n = p^r.  

• Сумма по всем делителям n равна 1, если n = 1, и 0, если n > 1.  

• Формула Эйлера: сумма по делителям n равна n.  

• Формула 2: сумма по делителям n равна n * M_n / d.  

• Функция Эйлера: сумма по числам от 1 до n, взаимно простым с n.  

• Введение функции I_a, которая равна 1, если a и n взаимно просты, и 0 иначе.  

• Сумма по делителям a: сумма по делителям наибольшего общего делителя a и n.  

• Перестановка порядков суммирования: суммирование по парам чисел a и d.  

• Группировка слагаемых с одинаковым значением d.  

• Сумма по всем d, делящим n, и фиксирование значения d.  

• Сумма по всем a, делящимся на d и не превосходящим n.  

• Фиксирование значения d и суммирование по a, делящимся на d.  

• Доказательство формулы 2: сумма по делителям n, делящимся на d, умноженная на M_d / d.  

• Следствие 1: функция Эйлера равна произведению простых чисел, делящих n, минус 1.  

• Доказательство методом пристального взгляда.  

• Следствие 2: функция Эйлера мультипликативна: если m и n взаимно просты, то F_m * F_n = F_m * F_n.  

• Доказательство основных фактов о функции Эйлера без использования формулы обращения Мёбиуса.  

• Переход к доказательству формулы обращения Мёбиуса.  

• Обсуждение эквивалентности функций и формулы обращения Мёбиуса.  

• Введение двух функций: f и g, которые связаны соотношением.  

• Обнаружение, что соотношение верно в обе стороны.  

• Возможность доказательства формул через рациональные дроби или формулу обращения Мёбиуса.  

• Пример использования формулы обращения для доказательства другой формулы.  

• Введение обозначений для конкретных и общих выражений.  

• Доказательство формулы 1 через формулу 2.  

• Изменение обозначений для упрощения вычислений.  

• Применение перестановки слагаемых для упрощения суммы.  

• Преобразование суммы по делителям числа n.  

• Использование условия делимости для упрощения суммирования.  

• Вынесение констант за скобки для упрощения выражения.  

• Доказательство формулы 2 через формулу 1.  

• Преобразование правой части формулы 1.  

• Применение аналогичных трюков для упрощения суммы.  

• Обсуждение аналогий между доказательствами.  

• Вынесение констант за скобки и упрощение выражения.  

• Завершение доказательства и проверка правильности.  

• Рассматривается деление целого числа на другое целое число.  

• Обсуждается суммирование по делителям числа.  

• Функция Мёбиуса применяется для суммирования по делителям.  

• Введение понятия сравнения по модулю.  

• Сравнение означает, что числа имеют одинаковые остатки по модулю.  

• Перечисление простых свойств сравнений.  

• Сравнение можно складывать и умножать.  

• Если числа сравнимы по модулю, то их разность делится на модуль.  

• Доказательство свойства умножения сравнений.  

• Если все элементы сравнения и модуль делятся на одно и то же число, то можно сократить на это число.  

• Пример сокращения на делитель и доказательство.  

• Важная лемма используется для доказательства свойств сравнений.  

• Пример применения важной леммы для доказательства свойства 5.  

• Если число взаимно просто с модулем, то существует обратный элемент по модулю.  

• Доказательство существования обратного элемента.  

• Если два числа сравнимы с единицей по модулю, то они равны.  

• Доказательство единственности обратного элемента.  

• Теорема Эйлера утверждает, что если числа взаимно просты, то их степень по модулю равна единице.  

• Обсуждение доказательства теоремы Эйлера.  

• Рассматривается множество натуральных чисел, взаимно простых с m.  

• Вводится понятие фиат, которое равно количеству элементов в этом множестве.  

• Рассматриваются числа, умноженные на элементы множества, и их остатки по модулю m.  

• Остатки по модулю m изменяются от 0 до m-1.  

• Вводится свойство, что если число взаимно просто с m и сравнимо с другим числом по модулю m, то оно тоже взаимно просто с m.  

• Доказывается, что все остатки по модулю m различны.  

• Перемножаются все сравнения из звездочки.  

• Доказывается, что произведение чисел из множества взаимно просто с m.  

• Произведение чисел из множества равно произведению остатков по модулю m.  

• Формулируется китайская теорема об остатках.  

• Рассматривается система сравнений, где x имеет остаток b1 по модулю m1, b2 по модулю m2 и т.д.  

• Доказывается, что существует с, такое что с сравнимо с единицей по модулю m.  

• Рассматриваются свойства сравнений и их решения.  

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

• Приводится более сложная формулировка китайской теоремы об остатках.  

• Рассматриваются взаимно простые модули и их произведения.  

• Доказывается существование обратного элемента для произведения модулей.  

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

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

• Объясняется, что обратный элемент по модулю меньшего модуля существует.  

• Задается выражение, задающее все решения китайской системы.  

• Рассматривается выражение по модулю большего модуля.  

• Объясняется, почему все слагаемые, кроме одного, равны нулю.  

• Доказывается, что икс со звездочкой сравнимо с бка по модулю мкат.  

• Доказывается, что если икс и икс штрих два решения, то их разность делится на мжое.  

• Объясняется, что произведение модулей также делит разность решений.  

• Проверяется, что икс сравнимы с икс штрих по модулю м большое.  

• Проверяется, что икс со звездочкой является решением системы.  

• Объясняется, что все решения системы можно найти, взяв числа, сравнимые с икс со звездочкой по модулю м большое.