Просмотр исходного текста страницы Теорема о делении с остатком. Алгоритм Евклида

Напомним теорему о делении с остатком:

'''Теорема о делении с остатком'''

Для любых целых <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> определяются однозначно. 


Рассмотрим следующий пример:

'''Пример'''

Пусть модуль <math>p = 6</math>.

Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:

:<math>K_0 = \left\{\ldots,-18,-12,-6,0,6,12,18,\ldots \right\}, r=0</math>;

:<math>K_1 = \left\{\ldots,-17,-11,-5,1,7,13,19,\ldots \right\}, r=1</math>;

:<math>K_2 = \left\{\ldots,-16,-10,-4,2,8,14,20,\ldots \right\}, r=2</math>;

:<math>K_3 = \left\{\ldots,-15,-9,-3,3,9,15,21,\ldots \right\}, r=3</math>;

:<math>K_4 = \left\{\ldots,-14,-8,-2,4,10,16,22,\ldots \right\}, r=4</math>;

:<math>K_5 = \left\{\ldots,-13,-7,-1,5,11,17,23,\ldots \right\}, r=5</math>,

где через <math>r</math> обозначен остаток от деления целого числа на 6.

В данном примере полная система наименьших неотрицательных вычетов есть множество <math>\left\{0, 1, 2, 3, 4, 5 \right\}</math>; 

полная система наименьших положительных вычетов – множество <math>\left\{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>\varphi(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>A \equiv {\alpha}_1 \pmod{p_1}</math>,
: <math>A \equiv {\alpha}_2 \pmod{p_2}</math>,
: <math>\ldots</math>,
: <math>A \equiv {\alpha}_n \pmod{p_n}</math>.

Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. <math>\forall a \in Z, \forall b \in Z, b\not= 0 \, \exist q \in Z, \exist r \in Z (0 \le r <b):\, a=bq+r </math>, то кольцо Z, по определению, является евклидовым. Таким образом, в качестве чисел <math> {\alpha}_i, i=0,\ldots,n </math> можно выбрать остатки от деления числа <math>A</math> на <math>p_i</math> соответственно.

Рассмотрим гомоморфное отображение: 

:<math>Z \to Z{|{\equiv}_{p_1}} \times Z{|{\equiv}_{p_2}} \times \ldots \times Z{|{\equiv}_{p_n}} </math> .

Тогда каждому целому числу <math>A</math> можно поставить в соответствие кортеж <math>\left\{{\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n \right\}</math> наименьших неотрицательных вычетов по одному из соответствующих классов. 

Важно отметить, что при преобразовании числа нет потери информации, если выполнено условие <math>A < p_1 \cdot p_2 \cdot \ldots \cdot p_n</math>, поскольку всегда, зная <math>\left({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n \right)</math> можно восстановить само число <math>A</math>. Поэтому кортеж  можно рассматривать как один из способов представления целого числа <math>A</math> – модулярное представление, или представление в системе остаточных классов (СОК).

Для дальнейшего используем расширенный алгоритм Евклида или его аналог – алгоритм нахождения линейного представления наибольшего общего делителя целых чисел: если числа а и b одновременно не равны нулю, то существуют целые числа <math>x</math> и <math>y</math>, такие, что <math>a \cdot b = a \cdot x + b \cdot y</math>.

Действительно, пусть <math>d</math> – наименьшее целое положительное число вида <math>a \cdot x + b \cdot y</math>, например, <math>d = a \cdot x_0 + b \cdot y_0</math>, где числа <math>x_0</math> и <math>y_0</math> не обязательно определены однозначно. Существование числа <math>d</math> следует только из принципа полной упорядоченности. Очевидно, что <math>d > 0</math>. Остаётся показать, что <math>d = (a,b)</math>. Для этого надо проверить выполнение двух условий: а) <math>d|a</math> и <math>d|b</math> б) если <math>c|a</math> и <math>c|b</math>
то <math>c|d</math>.

От противного: допустим, что свойство а) не выполняется, для определенности положим, что не выполнено <math>d|b</math>. Тогда по теореме о делении с остатком <math>a = dq + r</math>, <math>0 \le r < |d|</math>, и, следовательно, 

:<math>r=b-dq = b-(ax_0+by_0)q = a(-qx_0)+b(1-qy_0)</math>, 

что противоречит минимальности <math>d</math>.

Выполнение свойства б) проверяется непосредственно: 

:<math>c|a \Rightarrow \left(\exist q_1 \in Z\right)\left(a = q_1\, c\right)</math>;

:<math>c|b \Rightarrow \left(\exist q_2 \in Z\right)\left(a = q_2\, c\right)</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 x_i + b y_i</math>. Надо вычислить <math>x_i</math> и <math>y_i</math>. Очевидно, что <math>x_0 = 1, y_0 = 0</math> и <math>x_1 = 0, y_1 = 1</math>. Сравнивая обе части на ''i''-м шаге, получим 

:<math>a_i = a x_i + b y_i = a_{i-2} - a_{i-1} q_{i-1} = \left(a x_{i-2} + b y_{i-2} \right) - \left(a x_{i-1} + b y_{i-1} \right) q_{i-1} =</math>

:<math> \left(a x_{i-2} - x_{i-1} q_{i-1} \right) + \left(b y_{i-2} - y_{i-1} q_{i-1} \right)</math>,

откуда получается следующая индуктивная процедура вычисления <math>x_i</math> и <math>y_i</math>:

:<math>q_{i-1} = \left \lfloor \frac{a_{i-2}}{a_{i-1}} \right \rfloor</math>,

:<math>a_i = a_{i-2} - a_{i-1} q_{i-1}</math>,

:<math>x_i = x_{i-2} - x_{i-1} q_{i-1}</math>,

:<math>y_i = y_{i-2} - y_{i-1} q_{i-1}</math>.


'''Пример (Расширенный алгоритм Евклида)'''. 

Применим расширенный алгоритм Евклида к числам <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>.