Решить уравнение в кольце вычетов по модулю

Обратный элемент в кольце по модулю

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

Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.

Обратный элемент в кольце по модулю

Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .

Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.

Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.

Для того, чтобы показать это, рассмотрим следующее уравнение:

Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если .
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:

Таким образом, найденное x и будет являться обратным к a.

Области целостности в теории колец

Областью целостности называют коммутативное кольцо без делителей нуля. Так, кольцо целых чисел есть область целостности.

Теорема 2.9. Конечная область целостности является полем.

Поле — это кольцо, умножение которого коммутативно, а каждый ненулевой элемент а имеет обратный элемент относительно умножения. Так как область целостности, по определению, является коммутативным кольцом, то достаточно доказать, что для конечной области целостности любой ненулевой элемент обратим, т.е. для всякого существует единственный , такой, что .

Фиксируем произвольный элемент и определяем отображение множества всех ненулевых элементов в себя по формуле ( в области целостности при и ). Отображение является инъекцией, поскольку из равенства вытекает равенство , откуда ввиду отсутствия делителей нуля и . Так как носитель по условию теоремы конечен, то, согласно теореме 1.8, также и биекция. Поэтому для любого существует единственный элемент , такой, что . В частности, при равенство выполнено для некоторого однозначно определенного , то есть .

Доказательство теоремы 2.9 опирается на условие конечности кольца. Это условие действительно важно. Пример кольца целых чисел показывает, что бесконечная область целостности может и не быть полем.

Теорема 2.9 имеет интересные следствия. Рассмотрим кольцо вычетов по модулю .

Следствие 2.2. Кольцо вычетов по модулю является полем тогда и только тогда, когда — простое число.

Пусть является полем. Покажем, что в этом случае число р простое. Предположим, что оно составное. Тогда найдутся такие числа и , что . Поскольку в этом случае , по крайней мере числа и являются в кольце делителями нуля и — не поле. Следовательно, число не может быть составным.

Пусть — простое число. Предположим, что элементы и кольца будут делителями нуля, т.е. . При простом равенство произведения нулю по модулю означает, что либо делится на , либо делится на , т.е. либо , либо . Учитывая неравенства и , заключаем, что либо , либо . Таким образом, при простом делителей нуля нет и кольцо , как конечная область целостности, является полем.

Мультипликативная группа вычетов по модулю

Мультипликативную группу поля вычетов по модулю обозначают и называют мультипликативной группой вычетов по модулю .

Для произвольного легко видеть, что ненулевые элементы и кольца будут делителями нуля тогда и только тогда, когда произведение делится на (т.е. ). Например, в кольце делителями нуля будут элементы 2 и 6, 3 и 4, 3 и 8, 4 и 6, 4 и 9, 6 и 6, 6 и 8, 6 и 10, 8 и 9.

Замечание 2.3. Следствие 2.2 допускает интерпретацию с точки зрения теории чисел: каково бы ни было простое число , для всякого ненулевого найдется единственное ненулевое , такое, что . Этот результат имеет место именно в силу того, что для каждого элемента поля есть обратный элемент относительно умножения. Это — один из примеров применения общей алгебры к теории чисел.

Пример 2.14. В заключение приведем «таблицу сложения» (табл. 2.1) и «таблицу умножения» (табл. 2.2) для поля .

Таблицы, подобные приведенным выше, которые определяют операции в конечных алгебрах, носят название таблиц Кэли. Из таблиц Кэли для поля вычетов по модулю 5 следует, что в этом поле выполняются слегка шокирующие при первом взгляде равенства: и т.п. Но ни о каких «отрицательных» числах и ни о каких «дробях» тут речи нет, поскольку рассматриваются другие объекты — остатки при делении на 5. Просто равенство означает, что элемент 1 есть элемент, противоположный 4 в аддитивной группе вычетов по модулю 5: . Аналогично по умножению — в мультипликативной группе вычетов по модулю 5 элемент 3 есть обратный к 2 , так как , а элемент 4 обратен к себе самому.

Пример 2.15. Рассмотрим пример решения системы линейных алгебраических уравнений в поле . При записи уравнений будем опускать знак ©5 умножения там, где это не приводит к недоразумениям. Будем решать систему

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

Воспользовавшись таблицами Кэли, вычислим коэффициенты при переменных. В итоге имеем

Из последнего уравнения находим . Подставив во второе уравнение, будем иметь

Из первого уравнения после подстановки найденных значений переменных получим

Таким образом, и — решение системы линейных уравнений.

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