Вычисление мультипликативных обратных элементов по заданному модулю
Рассмотрим вопрос о мультипликативных обратных элементов по заданному модулю в фактор-кольце .
Теорема
Пусть , тогда класс имеет мультипликативный обратный элемент по модулю тогда и только тогда, когда .
Теорема
Характеристика конечного поля – простое число.
Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.
Первый способ
Из условия получаем или и, следовательно, – мультипликативный обратный к по модулю .
Второй способ
Напомним теорему Эйлера.
Определение
Функция Эйлера — это количество чисел от до , взаимно простых с .
Т.е. это количество таких натуральных чисел из отрезка , наибольший общий делитель (НОД) которых с равен единице.
Tеоремa Эйлера
Если и взаимно просты, то , где - функция Эйлера.
Доказательство теоремы достаточно простое, возможны различные варианты. Приведем здесь теоретико-числовое доказательство.
Доказательство
Пусть — все различные натуральные числа, меньшие и взаимно простые с ним.
Рассмотрим все возможные произведения для всех от до .
Поскольку взаимно просто с и взаимно просто с , то и также взаимно просто с , то есть для некоторого .
Отметим, что все остатки при делении на различны. Действительно, пусть это не так, то существуют такие , что
или
- .
Так как взаимно просто с , то последнее равенство равносильно тому, что
- или .
Это противоречит тому, что числа попарно различны по модулю .
Перемножим все сравнения вида . Получим:
или
- .
Так как число взаимно просто с , то последнее сравнение равносильно тому, что
или
- .
В частном случае, когда простое, теорема Эйлера превращается в так называемую малую теорему Ферма:
Малая теорема Ферма
Если - простое число и - произвольное целое число, не делящееся на , то .
Следствие
В кольце классов вычетов по модулю из следует, что .
Таким образом, для вычисления мультипликативного обратного к классу по модулю в случае, когда , достаточно возвести в степень , где , если – простое число, и в противном случае.
При таком методе вычисления мультипликативного обратного элемента задача сводится к цепочке умножений и делений с остатком на модуль . Эта задача решается без особых трудностей, если наименьший положительный вычет , где , представлен в СОК.
Однако, вообще говоря, не является наименьшим показателем степени, для которого .
Разложение кольца вычетов
Из китайской теоремы об остатках следует
Утверждение
Пусть - каноническое представление числа . Тогда функция, которая каждому классу ставит в соответствие кортеж , где , является кольцевым изоморфизмом кольца класса вычетов по модулю и кольца кортежей вида , где .
Более того, если обозначить через любую из кольцевых операций или , то
- .
Таким образом,
- ,
т.е. кольцо классов вычетов по модулю раскладывается в прямое произведение колец классов вычетов по модулям . Это разложение колец индуцирует разложение групп их обратимых элементов:
- .
Можно сделать вывод о том, что произвольное целое положительное число , где и для , однозначно представимо своими наименьшими неотрицательными остатками по модулям , причём сложение (а, следовательно, и вычитание) и умножение выполняются покомпонентно.