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

Определение:

Наибольшим общим делителем (англ. — greatest common divisor) для двух целых чисел и называется наибольшее натуральное , такое что делится на и делится на . Более формально,

Свойства НОД

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел [math]m[/math] или [math]n[/math] не ноль.

Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел:

Определение:

Наибольший общий делитель для целочисленного множества определяется как

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

Утверждение:

Пусть и — натуральные числа. Тогда где — делитель и . (Если не делится на будем считать, что присутствует в разложении в -ой степени.)

Разложим [math]a[/math] и [math]b[/math] на множители: пусть , где [math]p_j, q_j[/math] — простые, а [math]\alpha_j, \beta_j[/math] — натуральные (такие разложения существуют, по основной теореме арифметики). Без ограничения общности, можно считать, что [math]p_j = q_j, k = n[/math] (если это не так, сделаем соответствующие [math]\alpha[/math] и [math]\beta[/math] равными нулю). Очевидно, что в таком случае [math]a[/math] и на [math]b[/math] делятся на . Проверим его максимальность. Пусть существует [math]q \gt p[/math], такое что [math]a[/math] и [math]b[/math] делятся на [math]q[/math]. Тогда оно необходимо будет раскладываться на те же простые множители, что и [math]p[/math].

Пусть . Значит, существует . Из этого следует, что либо , либо . Но в первом случае, не окажется делителем , а во втором — . Значит, такого не существует.

Связь с наименьшим общим кратным

Определение:

Наименьшим общим кратным (англ. — least common multiple) для двух чисел и называется наименьшее натуральное число, которое делится на и без остатка. Более формально

Существует представление НОК через разложение числа на простые множители:

Утверждение:

Пусть и — натуральные числа. Тогда

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

Наибольший общий делитель связан с наименьшим общим кратным следующим равенством:

Лемма:

Пусть и — целые числа. Тогда .

Доказательство:

По утверждению о НОД и утверждению о НОК, пользуясь тем, что , получаем нашу лемму.

Алгоритм Вычисления

Наивный алгоритм

В наивном методе, мы считаем, что нам известны разложения чисел [math]a[/math] и [math]b[/math] на простые множители.

// [math]p[/math] — множество простых чисел в разложении [math]a[/math]
// [math]q[/math] — множество простых чисел в разложении [math]b[/math]
// [math]\alpha[/math] — степени простых чисел в разложении [math]a[/math]
// [math]\beta[/math] — степени простых чисел в разложении [math]b[/math]
function naiveGcd(p, q, [math]\alpha[/math], [math]\beta[/math]): 
    gcd [math]\leftarrow[/math] 1
    i, j [math]\leftarrow[/math] 0, 0
    while i < p.length() and j < q.length():
        if [math]p_i[/math] == [math] q_j[/math] : 
        t [math]\leftarrow[/math] min([math]\alpha_i[/math], [math]\beta_i[/math])
            gcd = gcd [math]\cdot[/math] [math]p_i^t[/math]
        else if [math]p_i[/math] < [math]q_j[/math] :
            i += 1
        else:
            j += 1
    return gcd

Корректность алгоритма следует из того, что он по сути просто делает пересечение двух упорядоченных массивов ([math]p[/math] и [math]q[/math]), только результат записывает не в массив, а агрегирует в переменной [math]\gcd[/math]. Асимптотика равна минимуму из длин массивов [math]p[/math] и [math]q[/math].

Стандартный алгоритм Евклида

Теорема:

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое [math]r_k[/math] — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

Тогда — последний ненулевой член этой последовательности.

Существование таких [math]r_1, r_2, \cdots[/math], то есть возможность деления с остатком [math]m[/math] на [math]n[/math] для любого целого [math]m[/math] и целого [math]n\ne 0[/math], доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

Лемма:

Пусть , тогда

Доказательство:

Пусть [math] k [/math] — любой общий делитель чисел [math] a [/math] и [math] b [/math], не обязательно максимальный, тогда [math] a = t_1 \cdot k [/math] ; [math] b = t_2 \cdot k [/math]; где [math] t_1 [/math] и [math] t_2 [/math] — целые числа из определения.
Тогда [math] k [/math] также общий делитель чисел [math] b [/math] и [math] r [/math], так как [math] b [/math] делится на [math] k [/math] по определению, а (выражение в скобках есть целое число, следовательно, [math] k [/math] делит [math] r [/math] без остатка)
Обратное также верно и доказывается аналогично: пусть [math] k [/math] — любой общий делитель чисел [math] b [/math] и [math] r [/math], не обязательно максимальный, тогда [math] b = t_1 \cdot k [/math] ; [math] r = t_2 \cdot k [/math]; где [math] t_1 [/math] и [math] t_2 [/math] — целые числа из определения.
Тогда [math] k [/math] также общий делитель чисел [math] a [/math] и [math] b [/math], так как [math] b [/math] делится на [math] k [/math] по определению, а (выражение в скобках есть целое число, следовательно, [math] a [/math] делит [math] a [/math] без остатка)
Следовательно, все общие делители пар чисел [math] a [/math], [math] b [/math] и [math] b [/math], [math] r [/math] совпадают. Другими словами, нет общего делителя у чисел [math] a [/math], [math] b [/math], который не был бы также делителем [math] b [/math], [math] r [/math], и наоборот.
В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.

Лемма:

для любого ненулевого

Далее, оценим асимптотику работы алгоритма.

Теорема:

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

Доказательство этого факта^[1] достаточно громоздкое, поэтому не будем приводить его здесь.

Проще сформулировать алгоритм Евклида так: если даны натуральные числа [math]a[/math] и [math]b[/math] и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

Таким образом, реализация стандартного алгоритма Евклида, достаточно проста:

function euclideanGcd(a, b) :
    while b [math]\neq[/math] 0 :
        t [math]\leftarrow[/math] b
        b [math]\leftarrow[/math] a mod b
        a [math]\leftarrow[/math] t
    return a

Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.

Двоичный алгоритм Евклида

Идея улучшения: давайте вместо долгого деления ограничимся вычитаниями и битовыми сдвигами.

Для начала, опишем еще несколько свойств [math]gcd[/math]:

Утверждение:

Пусть и — натуральные числа, тогда

Тривиальным образом следует из определения

Пользуясь этим, и утверждением о НОДе нуля, определим двоичный алгоритм Евклида (ниже будет дана рекурсивная реализация, для лучшей читаемости):

function binaryGcd(a, b) :
    if a == b or b == 0 : 
        return a
    if a == 0 : 
        return b 
    // первые два случая
    if a mod 2 = 0 :
        if b mod 2 = 0 : 
            return binaryGcd(a / 2, b / 2) [math]\cdot[/math] 2
        else
            return binaryGcd(a / 2, b)
    // второй случай, только [math]a[/math] и [math]b[/math] поменяли местами
    if b mod 2 = 0 : 
        return binaryGcd(a, b / 2)
    // остается третий случай. На самом деле, мы можем оставлять справа и [math]a[/math], и [math]b[/math]
    // поэтому давайте всегда оставлять меньшее
    if a > b : 
        return binaryGcd((a - b) / 2, b)
    return binaryGcd((b - a) / 2, a)

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

Можно показать^[2], что этот алгоритм, в среднем на 60% более эффективен, чем классический.

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

В стандартном алгоритме мы использовали следующее свойство: . Воспользуемся им для того, чтобы решить следующую задачу: найти [math]x[/math] и [math]y[/math] такие, что . Пусть мы нашли пару . Очевидно, что . Получаем: . Следовательно, приходим к расширенному алгоритму Евклида:

// Алгоритм возвращает тройку [math]\gcd, x, y[/math]
function extendedGcd(a, b) : 
    if b == 0 : 
        return a, 1, 0
    gcd, [math]x_1[/math], [math]y_1[/math] [math]\leftarrow[/math] extendedGcd(b, a mod b)
    x [math]\leftarrow[/math] [math]y_1[/math]
    y [math]\leftarrow[/math] [math]x_1[/math] - (a div b) [math]\cdot[/math] [math]y_1[/math]
    return gcd, [math]x[/math], [math]y[/math]

Такое представление наибольшего общего делителя называется соотношением Безу, а числа [math]x[/math] и [math]y[/math] — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

См. также

Примечания

↑ Wolfram MathWorld — алгоритм Евклида
↑ http://maths-people.anu.edu.au/~brent/pd/rpb183pr.pdf Twenty years' analysis of the Binary Euclidean Algorithm

Источники информации

[1] Wolfram MathWorld — алгоритм Евклида

[2] ttp://maths-people.anu.edu.au/~brent/pd/rpb183pr.pdf Twenty years' analysis of the Binary Euclidean Algorithm

[1]

[2]

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

Свойства НОД

Связь с наименьшим общим кратным

Алгоритм Вычисления

Наивный алгоритм

Стандартный алгоритм Евклида

Двоичный алгоритм Евклида

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

См. также

Примечания

Источники информации

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты