Реферат: Расширенный алгоритм Евклида

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

Описывается расширенный алгоритм Евклида и рассматриваются его приложения к решению олимпиадных задач. Приводятся алгоритмы решения линейных сравнений и диофантовых уравнений.


Алгоритм вычисления наибольшего общего делителя (НОД) был открыт древнегреческими математиками и известен как алгоритм “взаимного вычитания”. И хотя упоминание об этом алгоритме имеется еще у Аристотеля, впоследствии его стали называть алгоритмом Евклида. Что такое наибольший общий делитель, его свойства и методы вычисления рассмотрены в [1].


Напомним, что НОД двух чисел можно вычислить согласно следующей рекуррентности:

НОД(a, b) = (1)


На языке Си процедура вычисления НОД имеет вид:


int gcd(int a, int b)

{

if (b == 0) return a;

return gcd(b, a % b);

}


Алгоритм Евклида можно расширить для нахождения по заданным a и b таких целых x и y, что ax + by = d, где d – наибольший общий делитель a и b.


Лемма. Пусть для положительных целых чисел a и b (a > b) известны d = НОД(a, b) = НОД(b, a mod b), а также числа x’ и y’, для которых

d = x’ * b + y’ * (a mod b)

Тогда значения x и y, являющиеся решениями уравнения ax + by = d, находятся из соотношений

x = y’, y = x’ – y’ * (2)

Через здесь обозначена целая часть числа x.

Доказательство. Поскольку a mod b = a – * b, то

d = x’ * b + y’ * (a – * b) = y’ * a + (x’ – y’ * ) * b = x * a + y * b,

где обозначено x = y’, y = x’ – y’ * .


Функция gcdext(int a, int b, int *d, int *x, int *y), приведенная ниже, по входным числам a и b находит d = НОД(a, b) и такие x, y что d = a * x + b * y. Для поиска неизвестных x и y необходимо рекурсивно запустить функцию gcdext(b, a mod b, d, x, y) и пересчитать значения x и y по выше приведенной формуле. Рекурсия заканчивается, когда b = 0. При b = 0 НОД(a, 0) = a и a = a * 1 + 0 * 0, поэтому полагаем x = 1, y = 0.


void gcdext(int a,int b, int *d, int *x, int *y)

{

int s;

if (b == 0)

{

*d = a; *x = 1; *y = 0;

return;

}

gcdext(b,a % b,d,x,y);

s = *y;

*y = *x - (a / b) * (*y);

*x = s;

}


Для ручного выполнения расширенного алгоритма Евклида удобно воспользоваться таблицей с четырьмя столбцами (как показано ниже в примере), соответствующих значениям a, b, x, y. Процесс вычисления разделим на три этапа:

а) Сначала вычислим НОД(a, b), используя первые два столбца таблицы и соотношение (1). В последней строке в колонке а будет находиться значение d = НОД(a, b).

б) Занесем значения 1 и 0 соответственно в колонки x и y последней строки.

в) Будем заполнять последовательно строки для колонок x и y снизу вверх. Значения x и y в последнюю строку уже занесены на этапе б). Считая, что в текущей заполненной строке уже находятся значения (x’, y’), мы при помощи формул (2) будем пересчитывать и записывать значения (x, y) в соответствующие ячейки выше стоящей строки.


^ 1. Расширенный алгоритм Евклида. Найдем решение уравнения 5x + 3y = 1. Вычисление НОД(5, 3) и нахождение соответствующих x, y произведем в таблице:


a

b

x

y

5
a)


3

-1

2
в)


3

2

1

-1

2

1

0

1

1

0

1

0


б)



Порядок и направление вычислений указаны стрелками и буквами.

Из таблицы находим, что НОД(5, 3) = 5 * (-1) + 3 * 2 = 1, то есть x = -1, y = 2.

Рассмотрим, например, как получены значения (x, y) для первой строки. Со второй строки берем значения (x’, y’) = (1, -1). По формулам (2) получим:

x = y’ = -1,

y = x’ – y’ * = 1 – (-1) * = 1 + 1 = 2


Линейным сравнением называется уравнение вида ax = b (mod n). Оно имеет решение тогда и только тогда, когда b делится на d = НОД(a, n). Если d > 1, то уравнение можно упростить, заменив его на a’x = b’ (mod n’), где a’ = a / d, b’ = b / d, n’ = n / d. После такого преобразования числа a’ и n’ являются взаимно простыми.


Алгоритм решения уравнения a’x = b’ (mod n’) со взаимно простыми a’ и n’ состоит из двух частей:

1. Решаем уравнение a’x = 1 (mod n’). Для этого при помощи расширенного алгоритма Евклида ищем решение (x0, y0) уравнения a’x + n’y = 1. Взяв по модулю n’ последнее равенство, получим a’x0 = 1 (mod n’).

2. Умножим на b’ равенство a’x0 = 1 (mod n’). Получим a’(b’x0) = b’ (mod n’), откуда решением исходного уравнения a’x = b’ (mod n’) будет x = b’x0 (mod n’).


Лемма. Если НОД(k, m) = 1, то равенство ak = bk (mod m) эквивалентно a = b (mod m).

Доказательство. Из ak = bk (mod m) следует, что (a – b) * k делится на m. Но поскольку k и m взаимно просты, то a – b делится на m, то есть a = b (mod m).


Пример. Решить уравнение 18x = 6 (mod 8).

Значение d = НОД(18, 8) = 2 является делителем 6, поэтому решение существует. После упрощения получим уравнение 9x = 3 (mod 4). Что согласно лемме эквивалентно 3x = 1 (mod 4). Решая уравнение 3x + 4y = 1 с помощью расширенного алгоритма Евклида, получим x = -1, y = 1. Откуда x = -1 (mod 4) = 3. То есть x = 3 будет как решением уравнения 3x = 1 (mod 4), так и 18x = 6 (mod 8).


^ ДИОФАНТОВЫ УРАВНЕНИЯ


Диофантовыми называются уравнения вида

P(x1, x2, ..., xn) = 0,

где P(x1, ..., xn) – многочлен с целыми коэффициентами.


В этой главе рассмотрим алгоритм нахождения решения линейного диофантового уравнения с двумя неизвестными вида a * x + b * y = c (далее для простоты будем опускать знаки умножения и писать прото ax + by = c).


Теорема 1. Уравнение ax + by = c имеет решение в целых числах тогда и только тогда, когда c делится на НОД(a, b).


Теорема 2. Если пара (x0, y0) является решением уравнения ax + by = c, то все множество его решений (x, y) описывается формулой:

x = x0 + kb,

y = y0 – ka,

где k  Z. Очевидно, что если ax0 + by0 = c, то a(x0 + kb) + b(y0 – ka) = c для любого целого k.


Для нахождения частичного решения (x0, y0) уравнения ax + by = c следует сначала найти решение (x’, y’) уравнения ax + by = d (d – наибольший общий делитель a и b) при помощи расширенного алгоритма Евклида, после чего умножить его на c / d. То есть

x0 = x’ * c / d,

y0 = y’ * c / d


Пример. Найти множество решений уравнения 5x + 3y = 7.

1. Уравнение имеет решение, так как 7 делится на НОД(5, 3) = 1.

2. Находим решение уравнения 5x’ + 3y’ = 1 при помощи расширенного алгоритма Евклида: (x’, y’) = (-1, 2).

3. Находим решение (x0, y0) исходного диофантового уравнения:

x0 = -1 * 7 / 1 = -7,

y0 = 2 * 7 / 1 = 14

Согласно теореме 2 множество решений исходного диофантового уравнения имеет вид:

(x, y) = (-7 + 3k, 14 – 5k)