Инструкция
1
Наибольший общий делитель (НОД) двух целых чисел – это наибольшее целое число, на которое делятся оба исходных числа без остатка. При этом хотя бы одно из них должно быть отличным от нуля, как и НОД.
2
НОД легко вычислить по алгоритму Евклида или бинарному методу. По алгоритму Евклида определения НОД чисел a и b, одно из которых не равно нулю, существует такая последовательность чисел r_1 > r_2 > r_3 > … > r_n, в которой элемент r_1 равен остатку от деления первого числа на второе. А другие члены последовательности равны остаткам от деления предпредыдущего члена на предыдущий, а предпоследний элемент делится на последний без остатка.
3
Математически последовательность можно представить в виде:
a = b*k_0 + r_1
b = r_1*k_1 + r_2
r_1 = r_2*k_2 + r_3
…
r_(n - 1) = r_n*k_n,
где k_i – целочисленный множитель.
НОД (a, b) = r_n.
4
Алгоритм Евклида называют взаимным вычитанием, поскольку НОД получается при последовательном вычитании меньшего из большего. Нетрудно предположить, что НОД (a, b) = НОД (b, r).
5
Пример.
Найдите НОД (36, 120). По алгоритму Евклида отнимите от 120 число, кратное 36, в данном случае это 120 – 36*3 = 12. Теперь отнимите от 120 число, кратное 12, получится 120 – 12*10 = 0. Следовательно, НОД (36, 120) = 12.
6
Бинарный алгоритм нахождения НОД основан на теории сдвига. Согласно этому методу НОД двух чисел обладает следующими свойствами:
НОД (a, b) = 2*НОД (a/2, b/2) для четных a и b
НОД (a, b) = НОД (a/2, b) для четного a и нечетного b (наоборот верно НОД (a, b) = НОД (a, b/2))
НОД (a, b) = НОД ((a - b)/2, b) для нечетных a > b
НОД (a, b) = НОД ((b - a)/2, a) для нечетных b > a
Таким образом, НОД (36, 120) = 2*НОД (18, 60) = 4*НОД (9, 30) = 4* НОД (9, 15) = 4*НОД ((15 - 9)/2=3, 9) = 4*3 = 12.
7
Наименьшее общее кратное (НОК) двух целых чисел – это наименьшее целое число, которое делится на оба исходных числа без остатка.
НОК можно вычислить через НОД: НОК (a, b) = |a*b|/НОД (a, b).
8
Второй способ вычисления НОК – каноническое разложение чисел на простые множители:
a = r_1^k_1*…*r_n^k_n
b = r_1^m_1*…*r_n^m_n,
где r_i – простые числа, а k_i и m_i – целые числа ≥ 0.
НОК представляется в виде тех же простых множителей, где в качестве степеней берутся максимальные из двух чисел.
9
Пример.
Найдите НОК (16, 20):
16 = 2^4*3^0*5^0
20 = 2^2*3^0*5^1
НОК (16, 20) = 2^4*3^0*5^1 = 16*5 = 80.