Теорема о делении с остатком. Алгоритм Евклида
Пример
Пусть модуль .
Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:
- ;
- ;
- ;
- ;
- ;
- ,
где через обозначен остаток от деления целого числа на 6.
Напомним теорему о делении с остатком:
Теорема о делении с остатком
Для любых целых и , , существует единственный набор целых чисел и , что и , где — модуль числа .
Легко доказывается, что для любых целых чисел и , деление с остатком возможно и числа и определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество ; полная система наименьших положительных вычетов – множество ; полная система наименьших по абсолютной величине вычетов – множество ; приведённая система вычетов – множество , так как ; фактор-множество .
Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные числа – модули . Чаще всего модули выбирают из множества простых чисел.
Пусть
- ,
- ,
- ,
- .
Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. , то кольцо Z, по определению, является евклидовым. Таким образом, в качестве чисел можно выбрать остатки от деления числа на соответственно.
Рассмотрим гомоморфное отображение:
- .
Тогда каждому целому числу А можно поставить в соответствие кортеж наименьших неотрицательных вычетов по одному из соответствующих классов.
Важно отметить, что при преобразовании числа нет потери информации, если выполнено условие , поскольку всегда, зная можно восстановить само число . Поэтому кортеж можно рассматривать как один из способов представления целого числа – модулярное представление, или представление в системе остаточных классов (СОК).
Для дальнейшего используем расширенный алгоритм Евклида или его аналог – алгоритм нахождения линейного представления наибольшего общего делителя целых чисел: если числа а и b одновременно не равны нулю, то существуют целые числа и , такие, что .
Действительно, пусть – наименьшее целое положительное число вида , например, , где числа и не обязательно определены однозначно. Существование числа следует только из принципа полной упорядоченности. Очевидно, что . Остаётся показать, что . Для этого надо проверить выполнение двух условий: а) и б) если и то .
От противного: допустим, что свойство а) не выполняется, для определенности положим, что не выполнено . Тогда по теореме о делении с остатком , , и, следовательно,
- ,
что противоречит минимальности .
Выполнение свойства б) проверяется непосредственно:
- ;
- ;
- .