§ 5.3. Арифметика остатков

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

Хотелось бы превратить эти «часы» в прибор для вычисления сумм в Бесспорно, «часы» для арифметики остатков — это то же самое, что счет на пальцах для нормальной арифметики. Последний, между прочим, имеет длинную и выдающуюся историю. В средние века ему обучали в монастырских школах, а одна из первых английских книг по арифметике, «Основа наук» Роберта Рекорда (Robert Recorde), содержала целый параграф, объясняющий «искусство счета руками». Так что мы в хорошей компании.

Итак, предположим, что нужно сложить два класса из Будем предполагать, что оба класса записаны в приведенной форме, т.е. неотрицательны и меньше Процесс вычисления а следующий. Поместим стрелку «часов» в

точку, помеченную а, затем передвинем ее по часовой стрелке на b мест. Теперь стрелка будет показывать сумму а

Численный пример. Предположим, что Вам нужно к 4 прибавить 5 в Поместите стрелку «часов» на 5 и передвиньте ее вперед на 4 места. Когда Вы будете это делать, стрелка минует 0 и остановится на 1. Значит

К сожалению, наш прибор будет слишком медленно работать при больших (как и счет на пальцах, который трудноосуществим при слишком больших числах). Поэтому требуется более математизированный способ вычисления сумм в Реально, он достаточно прост. Пусть классы в которые нам предстоит сложить. Операция определяется формулой:

Интерпретация этой формулы требует некоторой осторожности. Слева в ней стоит сумма двух классов а справа мы имеем класс, соответствующий сумме двух целых чисел. Итак, сложение классов определяется в терминах операции, которую мы хорошо знаем: сложение целых чисел.

Вернемся к примеру сложения в которое мы выполнили с помощью прибора. Мы хотим к 4 прибавить 5. Учитывая формулу, сначала сложим 4 и 5; их сумма, очевидно, равна 9. Отсюда следует, что На первый взгляд кажется, что новый результат суммирования отличается от полученного с помощью прибора. Но не забывайте, что т. е.

Последний пример указывает на одну важную проблему. Мы видели, что класс эквивалентности может быть представлен любым своим элементом; это основной принцип из § 5.1. Но складывая два класса, мы сначала суммируем их представителей, а затем берем соответствующий класс. Как же мы можем быть уверенными в том, что при выборе каких-то других представителей, результирующий класс останется прежним? Для уверенности в том, что Вы уловили суть, рассмотрим еще

раз сумму 5 и 4 в Следуя сформулированному выше правилу, мы нашли, что их сумма равна 9. Однако, и формула говорит нам, что если сложить 13 и 12, то получится 25. Так, поначалу может показаться, что выбирая различные представители классов, мы получаем разные суммы. Но это только кажется. На основании того, что делится на 8, мы заключаем:

Один из путей решения проблемы мог бы состоять в записи классов в приведенном виде перед их сложением. Это неудобно и совсем необязательно. Как подсказывает разобранный выше пример, результат суммирования не зависит от выбора представителей классов. Это очень важно и должно быть проверено в деталях. Пусть два класса в Пусть Мы хотим показать, что Но равенство означает, что кратно и то же самое верно для Сумма кратных снова кратна откуда число

должно быть кратно Следовательно, что и требовалось доказать.

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

Как и в случае суммы, мы должны быть уверены, что определение умножения не зависит от выбора представителей классов. Итак, предположим, что Нужно проверить, что Равенство влечет: кратно скажем, для некоторого целого Аналогично для некоторого целого s. Умножая а на получим

Значит кратно

Зная теперь, как складываются и перемножаются классы, любопытно выяснить, так же ли ведут себя эти операции, как их тезки в Пусть — классы в Сложение классов обладает следующими свойствами:

Элемент а называется противоположным а. Заметим, что если а записан в приведенном виде, то приведенным видом класса а будет а. Умножение классов обладает следующими свойствами:

Итак, каждое свойство умножения соответствует свойству сложения, за одним исключением: существование противоположного элемента. Мы вернемся к этому вопросу в § 5.7, где обсудим деление классов.

Есть еще свойство дистрибутивности

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

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

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

В качестве важного следствия этого примера получаем, что в не всегда можно сокращать на ненулевой элемент. Другими словами, если то не всегда справедливо рассуждение:

Так, например, но Мы вернемся к этому вопросу в § 5.7, рассмотрев сначала некоторые приложения арифметики остатков.