Математические основы системы остаточных классов (стр. 2 из 19)
Через А1 – числа, дающие при делении остаток 1.
Например, числа вида
.Через А2 – числа, дающие при делении остаток 2.
Например, числа вида
.Через Ар-1 – числа, дающие при делении остаток р – 1.
Например, числа вида
.Полной системой вычетов по модулю р называется совокупность р-целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю р. Каждый класс вычетов по модулю р содержит в точности одно из чисел совокупности всех возможных остатков от деления на р: 0, 1, …, р – 1. Множество {0, 1, …, р – 1} называется полной системой наименьших неотрицательных вычетов по модулю р. Можно легко доказать, что любая совокупность р чисел (р >1), попарно несравнимых по модулю р, есть полная система вычетов по модулю р. Часто рассматривают полную систему наименьших положительных вычетов: 1, 2, …, р; полную систему наименьших по абсолютной величине вычетов:
при чётном р и 
при р нечётном.Можно ввести в рассмотрение приведённую систему вычетов по модулю р, т. е. систему чисел, взятых по одному и только по одному из каждого класса, взаимно простого с модулем.
Число классов, взаимно простых с модулем р, равно значению функции Эйлера φ(р).
§ 2. Теорема о делении с остатком. Алгоритм Евклида
Рассмотрим пример. Пусть р = 6.
Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:
r = 0; 
r = 1; 
r = 2; 
r = 3; 
r = 4; 
r = 5;где через r обозначен остаток от деления целого числа на 6.
Напомним теорему о делении с остатком:
Теорема: Разделить число
на число 
, 
, с остатком, значит, найти пару целых чисел q и r, таких, что выполняются следующие условия: 
.Легко доказывается, что для любых целых чисел а и
деление с остатком возможно и числа q и r определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество {0, 1, 2, 3, 4, 5}; полная система наименьших положительных вычетов – множество {0, 1, 2, 3, 4, 5, 6}; полная система наименьших по абсолютной величине вычетов – множество {-2,-1, 0, 1, 2, 3}; приведённая система вычетов – множество {1,5}, так как 
; фактор-множество 
Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные простые числа – модули
. Чаще всего числа 
выбирают из множества простых чисел.Пусть
…, 
.Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е.
где 
, то кольцо Z, по определению, является евклидовым. Таким образом, в качестве чисел 
можно выбрать остатки от деления числа А на рiсоответственно.Рассмотрим гомоморфное отображение:
.Тогда каждому целому числу А можно поставить в соответствие кортеж
наименьших неотрицательных вычетов по одному из соответствующих классов.Важно отметить, что при том нет никакой потери информации при условии, что
, так как всегда, зная 
можно восстановить, как мы увидим позже само число А. Поэтому кортеж можно рассматривать как один из способов представления целого числа А в компьютере – модулярное представление или представление в системе остаточных классов (СОК).Для дальнейшего нам требуется расширенный алгоритм Евклида или его аналог – алгоритм нахождения линейного представления наибольшего общего делителя целых чисел: если числа а и b одновременно не равны нулю, то существуют целые числа х и у, такие, что
.Действительно, пусть d – наименьшее целое положительное число вида
, например, 
, где числа х0 и у0 не обязательно определены однозначно. Существование числа d следует только из принципа полной упорядоченности. Очевидно, что d > 0. Остаётся показать, что 
. Для этого надо проверить выполнение двух условий: а) 
и 
; б) если 
и , то 
. Допустим, что свойство а) не выполняется и для определённости положим, что | 
. Тогда по теореме о делении с остатком 
, и, следовательно, 
,что противоречит минимальности d. Выполнение свойства б) проверяется непосредственно:
Рассмотрим теперь расширенный алгоритм Евклида для нахождения линейного представления наибольшего общего делителя
. Значения х и у вычисляются в серии шагов, в каждом из которых мы выражаем аi (вычисленное в процессе работы алгоритма Евклида) в форме 
. А именно, рассмотрим последовательность 
В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения (а, b), не превосходит числа цифр в меньшем из чисел а и b, умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.