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

Пример

Пусть модуль $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.

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

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

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

Легко доказывается, что для любых целых чисел $a$ и $b$ , $b \not= 0$ деление с остатком возможно и числа $q$ и $r$ определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество $\left\{0, 1, 2, 3, 4, 5 \right\}$ ; полная система наименьших положительных вычетов – множество $\left\{0, 1, 2, 3, 4, 5, 6 \right\}$ ; полная система наименьших по абсолютной величине вычетов – множество $\left\{-2,-1, 0, 1, 2, 3 \right\}$ ; приведённая система вычетов – множество $\left\{1,5 \right\}$ , так как $\phi(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}}$ .

Тогда каждому целому числу А можно поставить в соответствие кортеж $\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|$ , и, следовательно,