Лекция 07. Классы вычетов. Сравнения и многочлены

• Если a и m взаимно просты, то a в степени fermat m равно единице по модулю m.  

• fermat m - количество элементов в множестве натуральных чисел, не превосходящих m, взаимно простых с m.  

• Частный случай теоремы Эйлера - теорема Ферма: если x и p взаимно просты, то x в степени p-1 равно единице по модулю p.  

• Сравнение по модулю m задает отношение эквивалентности.  

• Классы эквивалентности позволяют вводить операции сложения и умножения.  

• Определение суммы и произведения классов эквивалентности корректно.  

• Элемент a обратим по модулю m тогда и только тогда, когда a и m взаимно просты.  

• Класс вычетов a обратим по модулю m, если существует класс вычетов b такой, что a b равно единице по модулю m.  

• Если для любого x из a x и m взаимно просты, то класс a обратим.  

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

• Для любого целого числа x существует представитель из полной системы вычетов.  

• Все элементы полной системы вычетов различны по модулю m.  

• Определение: приведенная система вычетов по модулю м.  

• В системе есть ровно по одному представителю от каждого обратимого класса вычетов.  

• Элементы системы взаимно просты с м.  

• Для любого б из системы б и м взаимно просты.  

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

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

• В школе доказывали мультипликативность функции Эйлера.  

• Пример: если м и н взаимно просты, то можно построить приведенную систему вычетов по модулю мн.  

• Это доказательство мультипликативности функции Эйлера.  

• Пример: м и н взаимно просты.  

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

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

• Проверка первого свойства: каждый элемент системы взаимно прост с мн.  

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

• Проверка третьего свойства: элементы системы различны.  

• Количество элементов в системе равно количеству способов выбрать а и б.  

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

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

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

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

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

• Многочлен определяется как выражение с целыми коэффициентами и переменной.  

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

• Многочлен называется тождественно нулевым, если все его коэффициенты равны нулю по модулю модуля.  

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

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

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

• Предполагается, что у многочлена степени н-1 не более н корней.  

• Если у многочлена есть корень, его можно разделить на многочлен, делящий на икс минус икс ноль.  

• Доказывается, что многочлен, оставшийся после деления, имеет степень не более н-1.  

• Теорема доказана, но используется предположение, что модуль простое число.  

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

• Использование леммы о том, что x1 - x0 не равно нулю по модулю p.  

• П делит x1 - x0, что делает их взаимно простыми.  

• Это позволяет сократить x1 - x0 в выражении.  

• Рассмотрение многочлена f от x степени p-1.  

• Многочлены не являются тождественно нулевыми.  

• Вычисление степени многочлена a от x.  

• Многочлен a от x имеет p-1 корней.  

• a тождественно равен нулю по модулю p.  

• Это означает, что a равен нулю для любого x по модулю p.  

• Доказательство теоремы Вильсона.  

• Четное число скобок в выражении.  

• Минус единица сравнима с p-1 факториалом по модулю p.  

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

• Введение в лемму Гензеля.  

• Задача нахождения корней многочлена по модулю p в степени альфа.  

• Формулировка леммы Гензеля.  

• Многочлен f от x с целыми коэффициентами.  

• Решение по модулю p и его подъем до старших степеней.  

• Подъем решения по модулю p в степени альфа до p в степени альфа + 1.  

• Использование биномов и формул Тейлора.  

• Линейное сравнение по модулю p для определения коэффициента t.  

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

• Единственность решения линейного сравнения.  

• Завершение доказательства леммы Гензеля.