Математические основы системы остаточных классов
§ 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 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.
Там же доказывается, что время выполнения алгоритма Евклида оценивается равенством , где L(a) и L(b) - число цифр в а и b соответственно. В правом столбце этого алгоритма каждый остаток выражен через . Надо вычислить и . Очевидно, что и . Сравнивая обе части на i-м шаге, получим
откуда получается следующая индуктивная процедура вычисления и
:
Пример. Применим расширенный алгоритм Евклида к числам а = 342, b = 612. Весь алгоритм представим в виде следующей таблицы.
Расширенный алгоритм Евклида
Номер итерации |
q |
A0 |
a1 |
x0 |
x1 |
Y0 |
y1 |
|
0 |
- |
342 |
612 |
1 |
0 |
0 |
1 |
|
1 |
0 |
612 |
342 |
0 |
1 |
1 |
0 |
|
2 |
1 |
342 |
270 |
1 |
-1 |
0 |
1 |
|
3 |
1 |
270 |
72 |
-1 |
2 |
1 |
-1 |
|
4 |
3 |
72 |
54 |
2 |
-7 |
-1 |
4 |
|
5 |
1 |
54 |
18 |
-7 |
9 |
4 |
-5 |
|
6 |
3 |
18 |
0 |
9 |
-34 |
-5 |
19 |
Заметим, что равенство выполняется на каждом шаге итерации. Алгоритм выдаёт d = 18, x = 9, y = -5 и тогда 18=342•9 + 612•(-5).