Теорема о делении с остатком. Алгоритм Евклида - История изменений

Isaeva в 13:07, 24 июня 2015

2015-06-24T13:07:41Z

Isaeva в 13:02, 24 июня 2015

2015-06-24T13:02:57Z

Isaeva в 12:20, 24 июня 2015

2015-06-24T12:20:55Z

Isaeva в 11:47, 28 января 2015

2015-01-28T11:47:37Z

Isaeva в 11:45, 28 января 2015

2015-01-28T11:45:35Z

Isaeva в 13:02, 23 января 2015

2015-01-23T13:02:23Z

Isaeva в 13:11, 17 декабря 2014

2014-12-17T13:11:34Z

Isaeva в 13:02, 17 декабря 2014

2014-12-17T13:02:19Z

Isaeva в 14:51, 10 декабря 2014

2014-12-10T14:51:28Z

Isaeva в 14:29, 10 декабря 2014

2014-12-10T14:29:05Z

@@ Строка 30: / Строка 30: @@
 где через <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>\left\{0, 1, 2, 3, 4, 5 \right\}</math>;
@@ Строка 153: / Строка 161: @@
-<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
+<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

@@ Строка 49: / Строка 49: @@
 :<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</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> – модулярное представление, или представление в системе остаточных классов (СОК).

← Предыдущая		Версия 12:20, 24 июня 2015
Строка 30:		Строка 30:
	где через <math>r</math> обозначен остаток от деления целого числа на 6.		где через <math>r</math> обозначен остаток от деления целого числа на 6.

−	В данном примере полная система наименьших неотрицательных вычетов есть множество <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>\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>\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>.

← Предыдущая		Версия 11:47, 28 января 2015
Строка 165:		Строка 165:


−	Заметим, что равенство <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>.	+	Заметим, что равенство <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>.

@@ Строка 88: / Строка 88: @@
 : <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>, равен
@@ Строка 130: / Строка 131: @@
 В правом столбце алгоритма каждый остаток выражен через <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} = \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>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>x_i</math> и <math>y_i</math>:

← Предыдущая		Версия 13:02, 23 января 2015
Строка 30:		Строка 30:
	где через <math>r</math> обозначен остаток от деления целого числа на 6.		где через <math>r</math> обозначен остаток от деления целого числа на 6.

−	В данном примере полная система наименьших неотрицательных вычетов есть множество <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>\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>\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>.

@@ Строка 1: / Строка 1: @@
 '''Пример'''
@@ Строка 19: / Строка 30: @@
 где через <math>r</math> обозначен остаток от деления целого числа на 6.
-Напомним теорему о делении с остатком:
+В данном примере полная система наименьших неотрицательных вычетов есть множество <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>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>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> выбирают из множества простых чисел.

← Предыдущая		Версия 13:02, 17 декабря 2014
Строка 157:		Строка 157:


−	Заметим, что равенство <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>.	+	Заметим, что равенство <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:51, 10 декабря 2014
Строка 122:		Строка 122:

	В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения <math>(a,b)</math>, не превосходит числа цифр в меньшем из чисел <math>a</math> и <math>b</math>, умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.		В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (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} = \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>.
		+

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

@@ Строка 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>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>.