кольцо вычетов по модулю

Ответ от Александр Титов[гуру]
Пожалуй, наиболее наглядный пример кольца вычетов по модулю N представляют собой обыкновенные стрелочные часы. Они являются кольцом вычетов по модулю 12. На них есть числа от 1 до 12. После 12 следует 1, потом 2; 3 и т. д. до 12, а потом опять 1; 2; 3 и так по кругу до бесконечности.
В общем случае кольцо вычетов по модулю N - это множество из N чисел, построенное подобно стрелочным часам. Но отсчёт начинается, как правило, не с 1, а с 0. Оно содержит N натуральных чисел (за исключением единственного ненатурального - 0). Порядок следования чисел таков: 0; 1; 2 и т. д. до N - 1, после чего снова следует 0, а потом опять 1; 2; 3 и т. д. до N - 1, затем вновь 0; 1; 2 и так до бесконечности.

В определение кольца входят также операции над элементами этого кольца - сложение, вычитание и умножение.
Операции сложения и вычитания выполняются так же, как и на стрелочных часах. Например:
4 + 5 = 9
11 + 4 = 3
4 - 9 = 7
и т. д.
В общем случае, если имеем числа от 0 до N - 1, то сложение и вычитание осуществляется по обычному правилу, если результат не превышает N - 1 или не меньше 0. В противном случае к результату прибавляем или отнимаем N, чтобы получилось число в указанных пределах.
Например, в кольце вычетов по модулю 20 есть числа от 0 до 19. Вот несколько примеров в этом кольце
1. 3 + 6 = 9 - это число лежит в пределах от 0 до 19 включительно - его оставляем.
2. 14 - 10 = 4 - аналогично.
3. В обычном ряду чисел 17 + 8 = 25. Это больше, чем 19, поэтому чтобы получить тот же результат в кольце вычетов по модулю 20, от суммы отнимаем 20. Поэтому в кольце вычетов по модуль 20 будет 17 + 8 = 5.
4. В обычном ряду чисел 2 - 14 = -12, а в кольце вычетов по модулю 20 будет 2 - 14 = 8 (к результату прибавили 20).
По другому это можно представить себе так. Складываем и вычитаем числа в обычном смысле слова, потом делим результат нацело на мощность кольца N, частное отбрасываем, а остаток сохраняем. Это и будет результатом. Поскольку остаток от деления на N всегда лежит в пределах от 0 до N - 1 включительно, то и результат операции над элементами кольца будет лежать в тех же пределах.
В приведённых выше примерах по кольцу вычетов по модулю 20:
1. 3 + 5 = 6 При делении 9 на 20 получаем в частном 0 и в остатке 9. Остаток - это результат, т. е. 4 + 5 = 9.
2. 14 - 10 = 4. Делим 4 на 20, получаем в частном 0 и в остатке 4, т. е. 14 - 10 = 4.
3. 17 + 8 = 25. Это в обычном ряду чисел. В кольце вычетов по модулю 20 результат 25 делим на 20. Получаем в частном 1 и в остатке 5. Частное отбрасываем, а остаток сохраняем, как результат, т. е. 17 + 8 = 5
4. 2 - 14 = -12. Делим -12 на 20, получаем в частном -1, а в остатке 8 (потому что -12 = (-1)*20 + 8). Сохраняем только остаток, т. е. 2 - 14 = 8.
Точно также воспроизводится и операция умножения. Умножают два числа в обычном смысле слова, потом результат нацело делят на N, частное отбрасывают, а остаток сохраняют.
Пример в кольце вычетов по модулю 17:
3*4 = 12
5*5 = 8 (25 делим на 17, в частном 1 и в остатке 8)
13*16 = 4 (208 делим на 17, в частном 12 и в остатке 4)
По принципу кольца вычетов построены также электронные часы с количеством часов от 0 до 23), а также множество дней недели (где 0 - это понедельник, 1 - это вторник и т. д., 6 - это воскресенье), и вообще почти весь календарь. В тех случаях, когда что либо имеет периодически изменяющуюся структуру, где новый период полностью повторяет старый, и используется кольцо вычетов по модулю N, где N - число элементов в одном периоде.