Теорема о делении с остатком. Алгоритм Евклида — различия между версиями

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 25: Строка 25:
 
Для любых целых <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>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>\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>.  
 
Чаще всего модули <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>\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>.

Версия 12:58, 10 декабря 2014

Пример

Пусть модуль 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|, и, следовательно,

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 .
Источник — «https://vscripts.ru/w/index.php?title=Теорема_о_делении_с_остатком._Алгоритм_Евклида&oldid=1044»