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

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

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

Для любых целых $a$ и $b$, $b \not= 0$, существует единственный набор целых чисел $q$ и $r$, что $a = bq + r$ и $0 \le r < |b|$, где $|b|$ — модуль числа $b$.

Легко доказывается, что для любых целых чисел $a$ и $b$, $b \not= 0$ деление с остатком возможно и числа $q$ и $r$ определяются однозначно.

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

Пример

Пусть модуль $p = 6$.

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

$K_0 = \left\{\ldots,-18,-12,-6,0,6,12,18,\ldots \right\}, r=0$;

$K_1 = \left\{\ldots,-17,-11,-5,1,7,13,19,\ldots \right\}, r=1$;

$K_2 = \left\{\ldots,-16,-10,-4,2,8,14,20,\ldots \right\}, r=2$;

$K_3 = \left\{\ldots,-15,-9,-3,3,9,15,21,\ldots \right\}, r=3$;

$K_4 = \left\{\ldots,-14,-8,-2,4,10,16,22,\ldots \right\}, r=4$;

$K_5 = \left\{\ldots,-13,-7,-1,5,11,17,23,\ldots \right\}, r=5$,

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

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

полная система наименьших положительных вычетов – множество $\left\{1, 2, 3, 4, 5, 6 \right\}$;

полная система наименьших по абсолютной величине вычетов – множество $\left\{-2,-1, 0, 1, 2, 3 \right\}$;

приведённая система вычетов – множество $\left\{1,5 \right\}$, так как $\varphi(6) = 6\,\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) = 2$;

фактор-множество $Z{|{\equiv}_6} = \left\{K_0, K_1, K_2, K_3, K_4, K_5 \right\}$.

Один из методов выполнения арифметических операций над целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные числа – модули $p_1, p_2, \ldots, p_n$. Чаще всего модули $p_1, p_2, \ldots, p_n$ выбирают из множества простых чисел.

Пусть

$A \equiv {\alpha}_1 \pmod{p_1}$,

$A \equiv {\alpha}_2 \pmod{p_2}$,

$\ldots$,

$A \equiv {\alpha}_n \pmod{p_n}$.

Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. $\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$, то кольцо Z, по определению, является евклидовым. Таким образом, в качестве чисел ${\alpha}_i, i=0,\ldots,n$ можно выбрать остатки от деления числа $A$ на $p_i$ соответственно.

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

$Z \to Z{|{\equiv}_{p_1}} \times Z{|{\equiv}_{p_2}} \times \ldots \times Z{|{\equiv}_{p_n}}$ .

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

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

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

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

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

$r=b-dq = b-(ax_0+by_0)q = a(-qx_0)+b(1-qy_0)$,

что противоречит минимальности $d$.

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

$c|a \Rightarrow \left(\exist q_1 \in Z\right)\left(a = q_1\, c\right)$;

$c|b \Rightarrow \left(\exist q_2 \in Z\right)\left(a = q_2\, c\right)$;

$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$.

Алгоритм Евклида для целых чисел

Пусть $a$ и $b$ — целые числа, не равные одновременно нулю, и последовательность чисел

$a > b > r_1 > r_2 > r_3 > r_4 > \cdots >r_n$

определена тем, что каждое $r_k$ — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

$a = bq_0 + r_1$

$b = r_1q_1 + r_2$

$r_1 = r_2q_2 + r_3$

$\cdots$

$r_{k-2} = r_{k-1} q_{k-1} + r_k$

$\cdots$

$r_{n-2} = r_{n-1}q_{n-1}+ r_n$

$r_{n-1} = r_n q_n$

Тогда НОД $(a,b)$, наибольший общий делитель $a$ и $b$, равен $r_n$, последнему ненулевому члену этой последовательности.

Существование таких $r_1, r_2, ...$, то есть возможность деления с остатком $a$ на $b$ для любого целого $a$ и целого $b\ne 0$, доказывается индукцией.

Корректность этого алгоритма вытекает из следующих двух утверждений:

• Пусть $a = bq + r$, тогда НОД $(a,b)$ = НОД $(b,r)$.
• НОД $(0,r)$ = $r$ для любого ненулевого $r$ (так как 0 делится на любое целое число, кроме нуля).

Расширенный алгоритм Евклида для целых чисел

Рассмотрим расширенный алгоритм Евклида для нахождения линейного представления наибольшего общего делителя $(a,b) = ax + by$.

Значения $x$ и $y$ вычисляются в серии шагов, в каждом из которых мы выражаем $a_i$ (вычисленное в процессе работы алгоритма Евклида) в форме $a x_i + b y_i$. А именно, рассмотрим последовательность

$a_0 = a$, $a_0 = a x_0 + b y_0$,

$a_1 = b$, $a_1 = a x_1 + b y_1$,

$a_2 = a_0 - a_1 q_1$, $a_2 = a x_2 + b y_2$,

$a_3 = a_1 - a_2 q_2$, $a_3 = a x_3 + b y_3$,

$\cdots$

$a_i = a_{i-2} - a_{i-1} q_{i-1}$, $a_i = a x_i + b y_i$,

$\cdots$

$a_k = a_{k-2} - a_{k-1} q_{k-1}$, $a_k = a x_k + b y_k$,

$0 = a_{k-1} - a_k q_k$, $0 = a x_{k+1} + b y_{k+1}$,

В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения $(a,b)$, не превосходит числа цифр в меньшем из чисел $a$ и $b$, умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.

В правом столбце алгоритма каждый остаток выражен через $a x_i + b y_i$. Надо вычислить $x_i$ и $y_i$. Очевидно, что $x_0 = 1, y_0 = 0$ и $x_1 = 0, y_1 = 1$. Сравнивая обе части на i-м шаге, получим

$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} =$

$\left(a x_{i-2} - x_{i-1} q_{i-1} \right) + \left(b y_{i-2} - y_{i-1} q_{i-1} \right)$,

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

$q_{i-1} = \left \lfloor \frac{a_{i-2}}{a_{i-1}} \right \rfloor$,

$a_i = a_{i-2} - a_{i-1} q_{i-1}$,

$x_i = x_{i-2} - x_{i-1} q_{i-1}$,

$y_i = y_{i-2} - y_{i-1} q_{i-1}$.

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

Применим расширенный алгоритм Евклида к числам $a = 342, b = 612$.

Весь алгоритм представим в виде следующей таблицы.

$\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}$

Заметим, что равенство $a_0 = a x_0 + b y_0$ выполняется на каждом шаге итерации. Алгоритм выдаёт

$d = 18, x = 9, y = -5$,

и тогда

$18=342 \cdot 9 + 612 \cdot (-5)$.