Теорема о делении с остатком. Алгоритм Евклида — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
Строка 26: | Строка 26: | ||
Легко доказывается, что для любых целых чисел <math>a</math> и <math>b</math>, <math>b \not= 0</math> деление с остатком возможно и числа <math>q</math> и <math>r</math> определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество <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>a</math> и <math>b</math>, <math>b \not= 0</math> деление с остатком возможно и числа <math>q</math> и <math>r</math> определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество <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>. | ||
Строка 65: | Строка 66: | ||
:<math>d=ax_0 + by_0 \Rightarrow d = q_1 c x_0 + q_2 c y_0 \Rightarrow d = \left(q_1 x_0 + q_2 y_0\right) c|d </math>. | :<math>d=ax_0 + by_0 \Rightarrow d = q_1 c x_0 + q_2 c y_0 \Rightarrow d = \left(q_1 x_0 + q_2 y_0\right) c|d </math>. | ||
+ | |||
+ | |||
+ | '''Алгоритм Евклида для целых чисел''' | ||
+ | |||
+ | Пусть <math>a</math> и <math>b</math> — целые числа, не равные одновременно нулю, и последовательность чисел | ||
+ | : <math> a > b > r_1 > r_2 > r_3 > r_4 > \cdots >r_n</math> | ||
+ | определена тем, что каждое <math>r_k</math> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть | ||
+ | : <math>a = bq_0 + r_1</math> | ||
+ | : <math>b = r_1q_1 + r_2</math> | ||
+ | : <math>r_1 = r_2q_2 + r_3</math> | ||
+ | |||
+ | : <math>\cdots</math> | ||
+ | : <math>r_{k-2} = r_{k-1} q_{k-1} + r_k</math> | ||
+ | |||
+ | : <math>\cdots</math> | ||
+ | : <math>r_{n-2} = r_{n-1}q_{n-1}+ r_n</math> | ||
+ | : <math>r_{n-1} = r_n q_n</math> | ||
+ | |||
+ | Тогда '''НОД''' <math>(a,b)</math>, наибольший общий делитель <math>a</math> и <math>b</math>, равен | ||
+ | <math>r_n</math>, последнему ненулевому члену этой последовательности. | ||
+ | |||
+ | |||
+ | '''Существование''' таких <math>r_1, r_2, ...</math>, то есть возможность деления с остатком <math>a</math> на <math>b</math> для любого целого <math>a</math> и целого <math>b\ne 0</math>, доказывается индукцией. | ||
+ | |||
+ | '''Корректность''' этого алгоритма вытекает из следующих двух утверждений: | ||
+ | |||
+ | * Пусть <math>a = bq + r</math>, тогда '''НОД''' <math>(a,b)</math> = '''НОД''' <math>(b,r)</math>. | ||
+ | * '''НОД''' <math>(0,r)</math> = <math>r</math> для любого ненулевого <math>r</math> (так как 0 делится на любое целое число, кроме нуля). | ||
+ | |||
+ | |||
+ | '''Расширенный алгоритм Евклида для целых чисел''' | ||
+ | |||
+ | Рассмотрим расширенный алгоритм Евклида для нахождения линейного представления наибольшего общего делителя <math>(a,b) = ax + by </math>. | ||
+ | |||
+ | Значения <math>x</math> и <math>y</math> вычисляются в серии шагов, в каждом из которых мы выражаем <math>a_i</math> (вычисленное в процессе работы алгоритма Евклида) в форме <math>a x_i + b y_i </math>. А именно, рассмотрим последовательность | ||
+ | |||
+ | : <math>a_0 = a</math>, <math>a_0 = a x_0 + b y_0</math>, | ||
+ | |||
+ | : <math>a_1 = b</math>, <math>a_1 = a x_1 + b y_1</math>, | ||
+ | |||
+ | : <math>a_2 = a_0 - a_1 q_1</math>, <math>a_2 = a x_2 + b y_2</math>, | ||
+ | |||
+ | : <math>a_3 = a_1 - a_2 q_2</math>, <math>a_3 = a x_3 + b y_3</math>, | ||
+ | |||
+ | : <math>\cdots</math> | ||
+ | |||
+ | : <math>a_i = a_{i-2} - a_{i-1} q_{i-1}</math>, <math>a_i = a x_i + b y_i</math>, | ||
+ | |||
+ | : <math>\cdots</math> | ||
+ | |||
+ | : <math>a_k = a_{k-2} - a_{k-1} q_{k-1}</math>, <math>a_k = a x_k + b y_k</math>, | ||
+ | |||
+ | : <math>0 = a_{k-1} - a_k q_k</math>, <math>0 = a x_{k+1} + b y_{k+1}</math>, | ||
+ | |||
+ | |||
+ | В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения <math>(a,b)</math>, не превосходит числа цифр в меньшем из чисел <math>a</math> и <math>b</math>, умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи. | ||
+ | |||
+ | '''Пример (Расширенный алгоритм Евклида)'''. | ||
+ | |||
+ | Применим расширенный алгоритм Евклида к числам <math>a = 342, b = 612</math>. | ||
+ | |||
+ | Весь алгоритм представим в виде следующей таблицы. | ||
+ | |||
+ | |||
+ | <math> \begin{array}{|c|r|r|r|r|r|r|r|} \hline Iteration & q & A_0 & a_1 & x_0 & x_1 & Y_0 & y_1 | ||
+ | \\ \hline 0 & - & 342 & 612 & 1 & 0 & 0 & 1 | ||
+ | \\ \hline 1 & 0 & 612 & 342 & 0 & 1 & 1 & 0 | ||
+ | \\ \hline 2 & 1 & 342 & 270 & 1 & -1 & 0 & 1 | ||
+ | \\ \hline 3 & 1 & 270 & 72 & -1 & 2 & 1 & -1 | ||
+ | \\ \hline 4 & 3 & 72 & 54 & 2 & -7 & -1 & 4 | ||
+ | \\ \hline 5 & 1 & 54 & 18 & -7 & 9 & 4 & -5 | ||
+ | \\ \hline 6 & 3 & 18 & 0 & 9 & -34 & -5 & 19 | ||
+ | |||
+ | \\ \hline \end{array} </math> | ||
+ | |||
+ | |||
+ | Заметим, что равенство <math>a_0 = a x_0 + b y_0</math> выполняется на каждом шаге итерации. Алгоритм выдаёт <math>d = 18, x = 9, y = -5</math> и тогда <math>18=342 \cdot 9 + 612 \cdot (-5)<math>. |
Версия 14:29, 10 декабря 2014
Пример
Пусть модуль .
Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:
- ;
- ;
- ;
- ;
- ;
- ,
где через обозначен остаток от деления целого числа на 6.
Напомним теорему о делении с остатком:
Теорема о делении с остатком
Для любых целых и , , существует единственный набор целых чисел и , что и , где — модуль числа .
Легко доказывается, что для любых целых чисел и , деление с остатком возможно и числа и определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество ; полная система наименьших положительных вычетов – множество ; полная система наименьших по абсолютной величине вычетов – множество ; приведённая система вычетов – множество , так как ; фактор-множество .
Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные числа – модули .
Чаще всего модули выбирают из множества простых чисел.
Пусть
- ,
- ,
- ,
- .
Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. , то кольцо Z, по определению, является евклидовым. Таким образом, в качестве чисел можно выбрать остатки от деления числа на соответственно.
Рассмотрим гомоморфное отображение:
- .
Тогда каждому целому числу А можно поставить в соответствие кортеж наименьших неотрицательных вычетов по одному из соответствующих классов.
Важно отметить, что при преобразовании числа нет потери информации, если выполнено условие , поскольку всегда, зная можно восстановить само число . Поэтому кортеж можно рассматривать как один из способов представления целого числа – модулярное представление, или представление в системе остаточных классов (СОК).
Для дальнейшего используем расширенный алгоритм Евклида или его аналог – алгоритм нахождения линейного представления наибольшего общего делителя целых чисел: если числа а и b одновременно не равны нулю, то существуют целые числа и , такие, что .
Действительно, пусть – наименьшее целое положительное число вида , например, , где числа и не обязательно определены однозначно. Существование числа следует только из принципа полной упорядоченности. Очевидно, что . Остаётся показать, что . Для этого надо проверить выполнение двух условий: а) и б) если и то .
От противного: допустим, что свойство а) не выполняется, для определенности положим, что не выполнено . Тогда по теореме о делении с остатком , , и, следовательно,
- ,
что противоречит минимальности .
Выполнение свойства б) проверяется непосредственно:
- ;
- ;
- .
Алгоритм Евклида для целых чисел
Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел
определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
Тогда НОД , наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.
Существование таких , то есть возможность деления с остатком на для любого целого и целого , доказывается индукцией.
Корректность этого алгоритма вытекает из следующих двух утверждений:
- Пусть , тогда НОД = НОД .
- НОД = для любого ненулевого (так как 0 делится на любое целое число, кроме нуля).
Расширенный алгоритм Евклида для целых чисел
Рассмотрим расширенный алгоритм Евклида для нахождения линейного представления наибольшего общего делителя .
Значения и вычисляются в серии шагов, в каждом из которых мы выражаем (вычисленное в процессе работы алгоритма Евклида) в форме . А именно, рассмотрим последовательность
- , ,
- , ,
- , ,
- , ,
- , ,
- , ,
- , ,
В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения , не превосходит числа цифр в меньшем из чисел и , умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.
Пример (Расширенный алгоритм Евклида).
Применим расширенный алгоритм Евклида к числам .
Весь алгоритм представим в виде следующей таблицы.
Заметим, что равенство выполняется на каждом шаге итерации. Алгоритм выдаёт и тогда