Теория остатков

Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей ( a , b ). Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что r n = au + bv = ( a, b ).

Действ

ительно, из цепочки равенств имеем:

r n = r n -2 - r n -1 q n = r n -2 - ( r n -3 - r n -2 q n -1 ) q n = .

(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение)

. = au + bv = ( a , b ).

Пример. Пусть а = 525, b = 231. (ниже приводится запись деления уголком, и каждый раз то, что было в уголке, т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок)

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

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;}

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

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

r1 = a + b( - q0)

r2 = b − r1q1 = a( − q1) + b(1 + q1q0)

(a,b) = rn = as + bt

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

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

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

ax + by = c ,

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

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

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

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

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

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

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

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

 Скачать реферат