Greatest Common Divisor

Greatest Common Divisor

'’Общий делитель’’ чисел $a_1, a_2, …, a_n$ - число, делящее все числа $a_1, a_2, …, a_n$ без остатка.

Алгоритм

1. Представим каждое число, как произведение его простых множителей и запишем их ввиде степеней
2. Выпишем делители, общие для всех чисел
3. Выберем наименьшую степень каждого из них
4. Посчитаем результат

Пример

$168 = 2^3 \cdot 3^1 \cdot 7^1$

$180 = 2^2 \cdot 3^7 \cdot 5^1$

$3014 = 2^4 \cdot 3^3 \cdot 7^1$

$GCD(168, 180, 3014) = 2^3 \cdot 3^1 = 12$

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

Дано: числа $m$ и $n$. Найти: наибольший общий делитель этих чисел

Алгоритм

1. разделим $m$ на $n$, $r$ - остаток от деления
2. если $r = 0$, то n - искомое значение
3. если $r \neq 0$, то $m = n$, $n = r$ и пока $r$ не станет равной нулю

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

’'’Во первых’’’, алгоритм всегда сходится. ‘'’Во вторых’’’, на каждой из итераций имеем:

1. $m = n \cdot q_1 + r_1$

2. $n = r_1 \cdot q_2 + r_2$

3. $r_1 = r_2 \cdot q_3 + r_3$

…

k+1. $r_{k-1} = r_k \cdot q_{k+1} + r_{k+1}$

k+2. $r_k = r_{k+1} \cdot q_{k+2} + 0$

’'’На первом шаге’’’:

Допустим, что $c = GCD(m, n)$.

Тогда $m = c \cdot d_m$, $n = c \cdot d_n$, где $d_m$ и $d_n $- некоторые целые числа.

Значит, $r_1 = m - n q_1 = c \cdot (d_m - d_n \cdot q_1$)

Т.е. $r_1$ тоже делится на $c$

’'’На $i$-том шаге’’’: точно так же, $r_i$ делится на $c$.

’'’Последний шаг’’’: Т.к. остаток от деления на этом шаге 0, то $r_k = c = GCD(m, n)$

’'’Q.E.D.’’’

Greatest Common Divisor вычитанием

Алгоритм

1. из большего числа вычитаем меньшее
2. если получается 0, то числа равны - возвращаем одно из них

Вычетание $q$ раз - это то же самое, что взять остаток от деления на $q$.

Обобщенный алгоритм Евклида (Соотношения Безу)

Дано: числа $m$ и $n$

Найти: НОД для $m$ и $n$ $d = GCD(m, n)$ и два числа $a$ и $b$ таких, что $am + bn = d$

Алгоритм

1. Инициализация:
2. : $a’ = 1$, $b = 1$
3. : $a = 0$, $b’ = 0$
4. : $c = m$, $d = n$
5. $c = qd + r$
6. : $q$ - частное, $r$ - остаток от деления $c$ на $d$.
7. $r = 0$? имеем $am + bn = d$
8. $r \neq 0$?
9. : повторяем итерацию
10. : $c = d$, $d = r$
11. : $t = a$’, $a’ = a$, $a = t - qa$
12. : $t = b$’, $b’ = b$, $b = t - qb$

Доказательство: см. Кнут, т.1 стр. 33

Sources

• Д. Кнут “Искусство Программирования”, т. 1