Теорема о делении с остатком. Алгоритм Евклида — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
+ | Напомним теорему о делении с остатком: | ||
+ | |||
+ | '''Теорема о делении с остатком''' | ||
+ | |||
+ | Для любых целых <math>a</math> и <math>b</math>, <math>b \not= 0</math>, существует единственный набор целых чисел <math>q</math> и <math>r</math>, что <math>a = bq + r</math> и <math>0 \le r < |b|</math>, где <math>|b|</math> — модуль числа <math>b</math>. | ||
+ | |||
+ | Легко доказывается, что для любых целых чисел <math>a</math> и <math>b</math>, <math>b \not= 0</math> деление с остатком возможно и числа <math>q</math> и <math>r</math> определяются однозначно. | ||
+ | |||
+ | |||
+ | Рассмотрим следующий пример: | ||
+ | |||
'''Пример''' | '''Пример''' | ||
Строка 19: | Строка 30: | ||
где через <math>r</math> обозначен остаток от деления целого числа на 6. | где через <math>r</math> обозначен остаток от деления целого числа на 6. | ||
− | + | В данном примере полная система наименьших неотрицательных вычетов есть множество <math>\left\{0, 1, 2, 3, 4, 5 \right\}</math>; полная система наименьших положительных вычетов – множество <math>\left\{0, 1, 2, 3, 4, 5, 6 \right\}</math>; полная система наименьших по абсолютной величине вычетов – множество <math>\left\{-2,-1, 0, 1, 2, 3 \right\}</math>; приведённая система вычетов – множество <math>\left\{1,5 \right\}</math>, так как <math>\phi(6) = 6\,\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) = 2</math> ; фактор-множество <math>Z{|{\equiv}_6} = \left\{K_0, K_1, K_2, K_3, K_4, K_5 \right\}</math>. | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | Один из методов выполнения арифметических операций над | + | Один из методов выполнения арифметических операций над целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные числа – модули <math>p_1, p_2, \ldots, p_n</math>. |
Чаще всего модули <math>p_1, p_2, \ldots, p_n</math> выбирают из множества простых чисел. | Чаще всего модули <math>p_1, p_2, \ldots, p_n</math> выбирают из множества простых чисел. | ||
Версия 13:11, 17 декабря 2014
Напомним теорему о делении с остатком:
Теорема о делении с остатком
Для любых целых и , , существует единственный набор целых чисел и , что и , где — модуль числа .
Легко доказывается, что для любых целых чисел и , деление с остатком возможно и числа и определяются однозначно.
Рассмотрим следующий пример:
Пример
Пусть модуль .
Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:
- ;
- ;
- ;
- ;
- ;
- ,
где через обозначен остаток от деления целого числа на 6.
В данном примере полная система наименьших неотрицательных вычетов есть множество ; полная система наименьших положительных вычетов – множество ; полная система наименьших по абсолютной величине вычетов – множество ; приведённая система вычетов – множество , так как ; фактор-множество .
Один из методов выполнения арифметических операций над целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные числа – модули .
Чаще всего модули выбирают из множества простых чисел.
Пусть
- ,
- ,
- ,
- .
Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. , то кольцо Z, по определению, является евклидовым. Таким образом, в качестве чисел можно выбрать остатки от деления числа на соответственно.
Рассмотрим гомоморфное отображение:
- .
Тогда каждому целому числу А можно поставить в соответствие кортеж наименьших неотрицательных вычетов по одному из соответствующих классов.
Важно отметить, что при преобразовании числа нет потери информации, если выполнено условие , поскольку всегда, зная можно восстановить само число . Поэтому кортеж можно рассматривать как один из способов представления целого числа – модулярное представление, или представление в системе остаточных классов (СОК).
Для дальнейшего используем расширенный алгоритм Евклида или его аналог – алгоритм нахождения линейного представления наибольшего общего делителя целых чисел: если числа а и b одновременно не равны нулю, то существуют целые числа и , такие, что .
Действительно, пусть – наименьшее целое положительное число вида , например, , где числа и не обязательно определены однозначно. Существование числа следует только из принципа полной упорядоченности. Очевидно, что . Остаётся показать, что . Для этого надо проверить выполнение двух условий: а) и б) если и то .
От противного: допустим, что свойство а) не выполняется, для определенности положим, что не выполнено . Тогда по теореме о делении с остатком , , и, следовательно,
- ,
что противоречит минимальности .
Выполнение свойства б) проверяется непосредственно:
- ;
- ;
- .
Алгоритм Евклида для целых чисел
Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел
определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
Тогда НОД , наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.
Существование таких , то есть возможность деления с остатком на для любого целого и целого , доказывается индукцией.
Корректность этого алгоритма вытекает из следующих двух утверждений:
- Пусть , тогда НОД = НОД .
- НОД = для любого ненулевого (так как 0 делится на любое целое число, кроме нуля).
Расширенный алгоритм Евклида для целых чисел
Рассмотрим расширенный алгоритм Евклида для нахождения линейного представления наибольшего общего делителя .
Значения и вычисляются в серии шагов, в каждом из которых мы выражаем (вычисленное в процессе работы алгоритма Евклида) в форме . А именно, рассмотрим последовательность
- , ,
- , ,
- , ,
- , ,
- , ,
- , ,
- , ,
В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения , не превосходит числа цифр в меньшем из чисел и , умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.
В правом столбце алгоритма каждый остаток выражен через . Надо вычислить и . Очевидно, что и . Сравнивая обе части на i-м шаге, получим
- ,
откуда получается следующая индуктивная процедура вычисления и :
- ,
- ,
- ,
- .
Пример (Расширенный алгоритм Евклида).
Применим расширенный алгоритм Евклида к числам .
Весь алгоритм представим в виде следующей таблицы.
Заметим, что равенство выполняется на каждом шаге итерации. Алгоритм выдаёт и тогда .