Определение.
d = НОД (a1, … an), если d – наибольшее целое число, на которое делятся все a1, … an.
m = НОК (a1, … an), если m – наименьшее целое число, которое делится на все a1, … an.
Алгоритм Евклида
Пример. НОД (72, 96) = НОД (72, 96 - 72) = НОД (72, 24) = 24.
Идея вычисления наибольшего общего делителя в том, что некоторые числа заменяем их линейными комбинациями таким образом, что числа уменьшаются, а наибольший общий делитель остаётся прежним.
Приведём более строгое описание работы алгоритма.
Теорема
Множество общих делителей не меняется при элементарных преобразованиях набора (a1, … an), то есть при замене ai числом ai - q× ak.
В самом деле, если некоторое число d было общим делителем набора (a1, … an), то все линейные комбинации этих чисел, в том числе ai - q× ak, делятся на d.
Аналогично, если число d1 является общим делителем для набора, в котором провели замену, то оно является делителем q× ak, а, следовательно, является делителем ai. Следовательно, является делителем исходного набора.
Пример
|
|
276 = 84 × 3 + 24
84 = 24 × 3 + 12
24 = 12 × 2
НОД (276, 84) = НОД (84, 24) = НОД (12, 24) = НОД (12, 0) = 12
Общая формула алгоритма для двух чисел.
a = bq1 + r1
b = r1q2 + r2
r1 = r2q3 + r3
r2 = r3q4 + r4
…
В конце концов остаток при делении окажется равен нулю, поскольку остатки уменьшаются с каждым шагом, и все они положительные.
rk-1 = rkqk+1 + rk+1
rk = rk+1qk+2
Тогда НОД (a, b) = rk+1 (то есть наибольший общий делитель равен последнему ненулевому остатку).
Алгоритм Евклида относится к так называемым «быстрым» алгоритмам, поскольку на каждом шаге остаток уменьшается по крайней мере в 2 раза, поэтому за сравнительно небольшое количество шагов алгоритм заканчивает работу.
Для трёх чисел вычисление наибольшего общего делителя может быть, например, таким.
НОД (65, 182, 130) = НОД (65, 182, 0) = НОД (65, 52, 0) = НОД (13, 0, 0) = 13.
Упражнения.
- Найти НОД (111 111, 1111)
Решение:
Таким образом, НОД (111111, 1111) = 11.
2. Найти НОД (98, 147, 112)
Решение.
НОД (98, 147, 112) = НОД (98, 147, 14) = НОД (0, 147, 14) = НОД (0, 7, 14) = НОД (0, 7, 0) = 7