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

дипломная работа

1.2 Алгоритм Евклида

Определение. Число d ??Z , делящее одновременно числа а , b , c , ... , k ??Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение: d = ( a , b , c , ..., k ) .

Теорема. Если ( a , b ) = d , то найдутся такие целые числа u и v , что d = au + bv .

Доказательство. Рассмотрим множество P = { au + bv ??u,v ??Z }. Очевидно, что P ??Z , а знатоки алгебры могут проверить, что P - идеал в Z . Очевидно, что a , b , 0 ??P . Пусть x , y ??P и y ??0 . Тогда остаток от деления x на y принадлежит P . Действительно:

x = yq + r , 0 ??r < y ,

r = x - yq = ( au 1 + bv 1 ) - ( au 2 + bv 2 ) q = a ( u 1 - u 2 q )+ b ( v 1 - v 2 q ) ??P .

Пусть d ??P - наименьшее положительное число из P (призадумайтесь, почему такое имеется!). Тогда а делится на d . В самом деле, a = dq + r 1 , 0 ??r 1 < d , a ??P , d ??P , значит r 1 ??P , следовательно r 1 = 0. Аналогичными рассуждениями получается, что b делится на d , значит d - общий делитель a и b .

Далее, раз d ??P , то d = au 0 + bv 0 . Если теперь d 1 - общий делитель a и b , то d 1 | ( au 0 + bv 0 ), т.е. d 1 | d . Значит d ??d 1 и d - наибольший общий делитель.

Определение. Целые числа a и b называются взаимно простыми, если (a , b ) = 1.

Вспоминая свойство 1 из предыдущего пункта, легко заметить, что два числа a и b являются взаимно простыми тогда и только тогда, когда найдутся целые числа u и v такие, что au + bv = 1.

Пусть даны два числа a и b ; a ??0, b ??0, считаем, что a > b . Символом := в записи алгоритма обозначаем присваивание. Алгоритм:

1. Ввести a и b .

2. Если b = 0 , то Ответ: а . Конец .

a = bq 1 + r 1

b = r 1 q 2 + r 2

r 1 = r 2 q 3 + r 3

r 2 = r 3 q 4 + r 4

0 ??r 1 < b

0 ??r 2 < r 1

0 ??r 3 < r 2

0 ??r 4 < r 3

· · · · · · · · ·

r n -3 = r n -2 q n -1 + r n -1

r n -2 = r n -1 q n + r n

r n -1 = r n q n +1

0 ??r n -1 < r n -2

0 ??r n < r n -1

r n +1 = 0

3. Заменить r := "остаток от деления а на b ", а := b , b := r .

4. Идти на 2.

В современной буквенной записи, алгоритм Евклида выглядит так: a > b; a, b ??Z .

Имеем: b > r 1 > r 2 >... > r n > 0, следовательно процесс оборвется максимум через b шагов. Очень интересный и практически важный народохозяйственный вопрос о том, когда алгоритм Евклида работает особенно долго, а когда справляется с работой молниеносно, мы рассмотрим чуть позже. Давайте сейчас покажем, что r n = ( a , b ). Просмотрим последовательно равенства сверху вниз: всякий делитель а и b делит r 1 , r 2 ,..., r n . Если же просматривать эту цепочку равенств от последнего к первому, то видно, что r n | r n -1 , r n | r n -2 , и т.д., т.е. r n делит а и b . Поэтому r n - наибольший общий делитель чисел а и b .

Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и 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. (ниже приводится запись деления уголком, и каждый раз то, что было в уголке, т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок)

_

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

}

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

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

r1 = a + b( - q0)

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

(a,b) = rn = as + bt

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

Делись добром ;)