Наибольший общий делитель

Как несложно догадаться, наибольший общий делитель (англ. greatest common divisor) двух целых чисел - наибольшее число, на которое делится каждое из них. Например:

\[\gcd(15, 20) = 5\] \[\gcd(12, 30) = 6\]

Сразу заметим важное свойство:

\[\gcd(a, b) = \gcd(b, a)\]

НОД играет большую роль как в математике, так и в программировании, и часто встречается в задачах на различные темы.

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

Алгоритм Евклида - один из первых алгоритмов в истории, использовался ещё в Древней Греции, и дошёл до наших дней. В изначальном виде он назывался “взаимным вычитанием”, так как заключался в поочерёдном вычитании меньшего числа из большего, пока одно из них не станет равным 0. Сегодня чаще всего вместо вычитания используется взятие остатка от деления, но суть алгоритма сохранилась.

Алгоритм заключается в построении ряда чисел следующего вида (\(a > b\)):

\[a, b, r_1, r_2, \ldots, r_n\]

Где каждое последующее число является остатком от деления предпредыдущего на предыдущее:

\[r_1 = a \bmod b \\ r_2 = b \bmod r_1 \\ \ldots \\ r_n = r_{n - 2} \bmod r_{n - 1}\]

Ряд заканчивается, когда остаток от деления предпоследнего числа на последнее становится равным 0:

\[r_{n - 1} \bmod r_n = 0\]

В таком случае утверждается, что:

\[\gcd(a, b) = r_n\]

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

\(t\) - общий делитель \(a\) и \(b\).

\(r_1 = a \bmod b\), или \(a = bq + r_1\).

Докажем, что \(t\) также является общим делителем \(b\) и \(r_1\).

\(b\) делится на \(t\) по определению.

\(r_1 = a - bq = t * ({a \over t} - {b \over t} * q)\), где \({a \over t}\) и \({b \over t}\) целые по определению.

Значит, \(r_1\) также делится на \(t\), что и требовалось доказать.

Из того, что все общие делители пар \((a, b)\) и \((b, r_1)\) совпадают, в частности следует, что \(\gcd(a, b) = \gcd(b, r_1)\).

Далее по индукции можно доказать следующее:

\[\gcd(a, b) = \gcd(b, r_1) = \gcd(r_1, r_2) = \ldots = \gcd(r_{n - 1}, r_n) = \gcd(r_n, 0)\]

(Нуль в последнем выражении появился из условия \(r_{n - 1} \bmod r_n = 0\)).

Нуль делится на все числа, отличные от нуля, поэтому справедливо следующее свойство:

\[\gcd(x, 0) = x,\ для\ любого\ x \in \mathbb{N}.\]

Следовательно,

\[\gcd(a, b) = r_n,\]

что и требовалось доказать.

Варианты реализации алгоритма Евклида на C++

Существует несколько вариантов реализации алгоритма Евклида, как итеративных так и рекурсивных. Классическая итеративная реализация (работающая быстрее всех рекурсивных) выглядит так:

1
2
3
4
5
6
7
8
9
10
11
12

int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }

    while (b) {
        a %= b;
        swap(a, b);
    }

    return a;
}

Рекурсивно это же можно реализовать так:

1
2
3
4
5
6
7
8
9
10
11

int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }

    if (b) {
        return gcd(b, a % b);
    } else {
        return a;
    }
}

Преимущество рекурсивной реализации заключается в возможности записать её в очень кратком виде (предполагающим, что \(a > b\)):

1
2
3

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

На практике разница во времени работы итеративного и рекурсивного вариантов не столь значительна, так что вы можете использовать любой из них.

Время работы алгоритма Евклида

Согласно некоторым исследованиям, время работы алгоритма Евклида тесно связано с числами Фибоначчи. Это выражается, в частности, в том, что два последовательных числа Фибоначчи - наихудшие входные данные для алгоритма Евклида. При \(a = F_n, b = F_{n - 1}\), алгоритм Евклида совершит ровно \(n - 2\) итерации. Отсюда можно выразить асимптотическую сложность алгоритма: последовательность Фибоначчи возрастает с экспоненциальной скоростью, поэтому алгоритм Евклида работает за \(O(\log \min(a, b))\).

Наименьшее общее кратное

С понятием НОД связано также понятия наименьшего общего кратного (англ. least common multiple). Наименьшее общее кратное двух натуральных чисел - наименьшее натуральное число, которое делится на каждое из них. Оно обозначается следующим образом:

\[lcm(a, b)\]

и связано с НОД формулой:

\[lcm(a, b) = {a * b \over \gcd(a, b)}\]

Реализация на C++:

1
2
3
4
5

int lcm(int a, int b) {
    return a / gcd(a, b) * b;   //используя форму a * b / gcd(a, b),
                                //можно получить переполнение на этапе a * b,
                                //поэтому следует выполнять деление до умножения
}

Взаимнопростые числа

Числа \(a\) и \(b\) называются взаимнопростыми тогда и только тогда, когда они не имеют общих делителей отличных от \(1\). То есть в их отношении должно выполняться условие \(\gcd(a, b) = 1\).

НОД и НОК для произвольного количества чисел

Обе функции легко обобщаются для произвольного числа аргументов последовательным применением:

\[\gcd(a, b, c, d) = \gcd(\gcd(\gcd(a, b), c), d)\] \[lcm(a, b, c, d) = lcm(lcm(lcm(a, b), c), d)\]