§ 5.7. Деление по модулю n

Настало время вернуться к проблеме деления классов в Но сначала рассмотрим тот же самый вопрос в более знакомой ситуации. Пусть вещественные числа. Один из способов деления а на состоит в умножении а на Число

называется обратным к и однозначно определяется как решение уравнения С практической точки зрения этот способ не облегчает дела, потому что для вычисления мы все равно должны разделить 1 на Однако с теоретической точки зрения иногда бывает лучше рассуждать об обратном элементе, нежели о делении. Наконец, существует только если поскольку уравнение не имеет решений. Держа эти замечания в уме, вернемся к

Как всегда, фиксированное натуральное число. Предположим, что а Назовем а обратным к а, а сам элемент а обратимым, если в справедливо равенство: Ясно, что 0 не имеет обратного в . К сожалению, 0 может быть не единственным элементом в не имеющим обратного. Необходимо рассмотреть этот момент очень подробно.

Предположим, что имеет обратный элемент а, и посмотрим, что мы с этого будем иметь. Из уравнения

следует, что делится на Иначе говоря,

для некоторого целого к. Равенство (7.1) влечет: Таким образом мы заключаем, что если а имеет обратный элемент в то

Верно ли обратное? Для ответа предположим, что а — такое целое число, для которого Равенство (7.1) подсказывает применить расширенный алгоритм Евклида к числам Этот алгоритм даст нам такие целые числа что

Полученное уравнение эквивалентно тождеству

в Значит класс а, найденный с помощью расширенного алгоритма Евклида, является обратным к а в Итак, если то а обратим в Подведем итог в следующей теореме.

Теорема обратимости. Класс а обратим в тогда и только тогда, когда целые а взаимно просты.

Рассуждения, приведенные выше, являются конструктивным доказательством теоремы обратимости, в том смысле, что они представляют собой процедуру для проверки существования обратного элемента и его вычисления, если он есть. Конечно, эта процедура — непосредственное применение расширенного алгоритма Евклида. Например, обладает ли 3 обратным в ? И если «да», то чему он равен? Применяя расширенный алгоритм Евклида к числам 32 и 3, мы найдем, что и

Так что обратный элемент существует. Переписывание этого уравнения по модулю 32 приводит к равенству: Итак, обратный элемент к 3 в

Множество обратимых элементов в обозначающееся символом играет ключевую роль в главах 9, 10 и 11. По теореме обратимости мы имеем:

Для простого числа множество вычислить очень легко, потому что в этом случае условие равносильно такому: не делит а. Поскольку это справедливо для всех натуральных чисел, меньших имеем

К сожалению, такое простое описание множества верно только для простого Если составное и его множитель, то так что к не

обратим в Два простых примера.

Ключевое свойство множества состоит в том, что оно содержит произведение любых своих элементов. Более точно, если обратимые классы в то произведение а тоже обратимо в Это утверждение является очень важным для главы 9, так что проверим его детально. Пусть а — обратный элемент для для Тогда обратным к произведению а будет Действительно,

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

Вернемся к проблеме делимости а на с которой мы начинали этот параграф. Прежде всего нам нужно узнать, имеет ли обратный элемент в Если имеет, то мы найдем его с помощью расширенного алгоритма Евклида. Пусть, например, это будет 0. Чтобы разделить а на мы вычислим произведение а Разделим, в качестве примера, 2 на 3 в После применения алгоритма Евклида к 3 и 8 мы имеем: и 3 сам себе обратен. Поэтому результат деления 2 на 3 в равен 6.

Применим результаты этого параграфа к решению линейных сравнений в Линейное сравнение — это уравнение вида

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

существует такой что Умножая обе стороны уравнения (7.2) на а, получаем:

и уравнение решено. Например, для решения сравнения мы сначала ищем обратный элемент к 7 по модулю 15. Так как обратным к 7 по модулю 15 будет . Умножая сравнение на 13, получаем

что является искомым решением.

Заметим, метод, применяемый к решению линейных сравнений, показывает, что в случае сравнение имеет одно и только одно решение по модулю Иначе говоря, несмотря на бесконечность числа целых, удовлетворяющих данному уравнению, все они сравнимы друг с другом по модулю Замечание может показаться банальным, но это не так. В самом деле, высказывание не верно, если Уравнение , например, не имеет решений вовсе. Мы вернемся к этому вопросу в начале главы 8.

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)