Теория остатков (стр. 2 из 10)

_ _42| 42 | 0

_ 63| 42 | 21 2

_ 231| 189 | 42 1

525| 462 | 63 3

231 2

Запись того же самого в виде цепочки равенств:

525 = 231 · 2 + 63

231 = 63 · 3 + 42

63 = 42 · 1 + 21

42 = 21 · 2

Таким образом, (525, 231) = 21. Линейное представление наибольшего общего делителя:

21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 =

= 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) =

= 525 · 4 - 231 · 9,

и наши пресловутые u и v из Z равны, соответственно, 4 и - 9.

Приступим теперь к исполнению второй части названия этого пункта - анализу алгоритма Евклида. Нас будет интересовать наихудший случай - когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает

Теорема (Ламэ, 1845 г.). Пусть n N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = _{n +2} , b = _{n +1} , где _k - k- ое число Фибоначчи.

Следствие. Если натуральные числа a и b не превосходят N N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает log _Ф ( 5 N ) - 2, где - верхнее целое , = (1 + 5)/2 - больший корень характеристического уравнения последовательности Фибоначчи.

Доказательство. Максимальное число шагов n достигается при а = _n+2 , b = _{n +1} , где n - наибольший номер такой, что _{n +2} < N . Рассматривая формулу для n -ого члена последовательности Фибоначчи, легко понять, что _{n +2} - ближайшее целое к (1/ 5) ^{n +2} . Значит (1/ 5) ^{n +2} < N , следовательно, n+2 < log _Ф ( 5 N ), откуда моментально даже n < log _Ф ( 5 N ) - 3 (именно "минус три", ведь рассматривается верхнее целое).

log _Ф ( 5 N ) 4,785 · lg N + 1,672, поэтому, например, с любой парой чисел, меньших миллиона, алгоритм Евклида разбирается не более, чем за 4,785 · 6 + 1,672 - 3 = 31 - 3 = 28 шагов.

Листинг алгоритма Евклида на языке С

// Обобщенный алгоритм Евклида для поиска наибольшего общего // делителя gcd = НОД(u,v) целых положительных чисел u и v // и коэффициентов a и b уравнения a*u + b*v = gcd// Все числа полагаются типа long // Подстановки упрощающие запись исходного текста#define isEven(x) ((x & 0x01L) == 0) // x - четное?#define isOdd(x) ((x & 0x01L)) // x - нечетное?#define swap(x,y) (x ^= y, y ^= x, x ^= y) // обмен значений x и y void GenEuclid(long *u, long *v, long *a, long *b, long *gcd){int k; // Параметр цикловlong a1, b1, g1; // Вспомогательные переменные // Алгоритм предполагает, что u > v, если u < v, то они переставляютсяif (*u < *v) swap(*u, *v);// Если u = n * 2^k1 или v = m * 2^k2, то перед поиском НОД// производим сокращение u = u/(2^k), v = v/(2^k),// где k - минимальное из k1, k2. Показатель k запоминаем.for (k = 0; isEven(*u) && isEven(*v); ++k){ *u >>= 1; *v >>= 1;}// Задание начальных значений*a = 1; *b = 0; *gcd = *u; a1 = *v; b1 = *u - 1; g1 = *v;do { do { if (isEven(*gcd)){ if (isOdd(*a) || isOdd(*b)){ *a += *v; *b += *u; } *a >>= 1; *b >>= 1; *gcd >>= 1; } if (isEven(g1) || *gcd < g1){ swap(*a, a1); swap(*b, b1); swap(*gcd, g1); } } while (isEven(*gcd)); while(*a < a1 || *b < b1){ *a += *v; *b += *u; } *a -= a1; *b -= b1; *gcd -= g1;} while (g1 > 0);while (*a >= *v && *b >= *u){ *a -= *v; *b -= *u;}// производим умножение коэффициентов уравнения // на сокращенный ранее множитель 2^k*a <<= k; *b <<= k; *gcd <<= k;}

Расширенный алгоритм Евклида и соотношение Безу

Формулы для r_i могут быть переписаны следующим образом:

r₁ = a + b( - q₀)

r₂ = b − r₁q₁ = a( − q₁) + b(1 + q₁q₀)

(a,b) = r_n = as + bt

здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве основной теоремы арифметики.

1.3 Применения алгоритма Евклида

Пусть требуется решить линейное диофантово уравнение:

ax + by = c ,

где a , b , c Z ; a и b - не нули.

Попробуем порассуждать, глядя на это уравнение.

Пусть ( a , b ) = d . Тогда a = a ₁ d ; b = b ₁ d и уравнение выглядит так:

a ₁ d· x + b ₁ d· y = c , т.е. d· ( a ₁ x + b ₁ y ) = c .

Теперь ясно, что у такого уравнения имеется решение (пара целых чисел x и y ) только тогда, когда d | c . Пусть d | c . Поделим обе части уравнения на d , и всюду далее будем считать, что ( a , b ) = 1.

Рассмотрим несколько случаев.

Случай 1. Пусть c = 0, уравнение имеет вид ax + by = 0 - " однородное линейное диофантово уравнение".

x = -

b a

y .

Так как x должен быть целым числом, то y = at , где t - произвольное целое число (параметр). Значит x = - bt и решениями однородного диофантова уравнения ax + by = 0 являются все пары вида {- bt , at }, где t = 0; ±1; ±2;... Множество всех таких пар называется общим решением линейного однородного диофантова уравнения, любая же конкретная пара из этого множества называется частным решением.

Случай 2. Пусть теперь c 0. Этот случай закрывается следующей теоремой.

Теорема. Пусть ( a , b ) = 1, { x ₀ , y ₀ } - частное решение диофантова уравнения ax + by = c . Тогда его общее решение задается формулами:

  

x = x 0 - bt y = y 0 + at .

Таким образом, и в теории линейных диофантовых уравнений общее решение неоднородного уравнения есть сумма общего решения соответствующего однородного уравнения и некоторого (любого) частного решения неоднородного уравнения.

Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения ax + by = c имеет именно такой вид, какой указан в формулировке теоремы. Пусть { x * , y *} - какое-нибудь решение уравнения ax + by = c . Тогда ax * + by * = c , но ведь и ax ₀ + by ₀ = c . Следуя многолетней традиции доказательства подобных теорем, вычтем из первого равенства второе и получим:

a ( x *- x ₀ ) + b ( y *- y ₀ ) = 0

- однородное уравнение. Далее, глядя на случай 1, рассмотрение которого завершилось несколькими строками выше, пишем сразу общее решение: x *- x ₀ = - bt , y *- y ₀ = at , откуда моментально, используя навыки третьего класса средней школы, получаем:

  

x * = x 0- bt , y * = y 0 + at.



Как же искать то самое частное решение { x ₀ , y ₀ }. Мы договорились, что ( a , b ) = 1. Это означает, что найдутся такие u и v из Z , что au + bv = 1, причем эти u и v мы легко умеем находить с помощью алгоритма Евклида. Умножим теперь равенство au + bv = 1 на c и получим: a ( uc ) + b ( vc ) = c , т.е. x ₀ = uc , y ₀ = vc .

Определение. Цепной (или, непрерывной) дробью называется выражение вида:

(Бедные наборщики в докомпьютерные времена буквально стрелялись, когда им приходилось набирать в книжках подобные многоэтажные выражения.) Договоримся называть числа q ₁ , q ₂ ,..., q _n ,... - неполными частными и считаем, что q ₁ Z , а q ₂ ,..., q _n ,... N . Числа называются подходящими дробями цепной дроби .

1 = q 1 , 2 , = q 1 +

1 q 2

, 3 = q 1 +

1

, и т. д.

Цепная дробь может быть как конечной (содержащей конечное число дробных линий и неполных частных), так и бесконечной вниз и вправо (на юго-восток). В первом случае она, очевидно, представляет некоторое рациональное число, во втором случае - пока непонятно что она вообще из себя представляет, но ясно, что все ее подходящие дроби - рациональные числа.

Пусть Q , = a / b ; a , b Z , b > 0. Оказывается, что при этих условиях, указанный выше процесс разложения числа в цепную дробь всегда конечен и выполним с помощью достопочтенного и любимого нами алгоритма Евклида. Действительно, отдадим алгоритму числа a и b , и внимательно посмотрим, что получится.

a = bq 1 + r 1	т.е.	a b	= q 1 +	1 b / r 1
b = r 1 q 2 + r 2	т.е.	b r 1	= q 2 +	1 r 1 / r 2
r 1 = r 2 q 3 + r 3	т.е.	r 1 r 2	= q 3 +	1 r 2 / r 3
. . . . . . .
r n -2 = r n -1 q n + r n	т.е.	r n -2 r n -1	= q n +	1 r n -1 / r n
r n -1 = r n q n +1	т.е.	r n -1 r n	= q n +1 .