eolymp

Extended Euclidean algorithm (RU)

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

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

medv_gcde_01

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

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’ ·medv_gcde_02      (2)

  Через medv_gcde_02 здесь обозначена целая часть числа a/b.

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

d = x’ · b + y’ · (amedv_gcde_02 · b) = y’ · a + (x’ – y’ · medv_gcde_02 ) · b = x · a + y · b,

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

   Функция 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 произведем в таблице:

medv_gcde_03

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

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

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

x = y’ = -1,

y = x’ – y’ ·medv_gcde_02  = 1 – (-1) ·medv_gcde_04  = 1 + 1 = 2

 

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

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

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

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

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

   Доказательство. Из ak = bk (mod m) следует, что (ab) · k делится на m. Но поскольку k и m взаимно просты, то ab делится на 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 = y0ka,

   где k Є Z. Очевидно, что если ax0 + by0 = c, то a(x0 + kb) + b(y0ka) = 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)

СПИСОК ЛИТЕРАТУРЫ

1. Статья "Наибольший общий делитель ", журнал Потенциал №10, 2008.

2. "Практика и теория программирования", Книга 2. Винокуров Н.А., Ворожцов А.В., – М: Физматкнига, 2008 - 288 с.