8. Базовая математика
Читать 0 мин.
8.230. НОК и НОД
Наименьшим общим кратным нескольких целых чисел называется наименьшее натуральное число, кратное каждому из этих чисел.
Наибольшим общим делителем нескольких чисел называется наибольшее натуральное число, на которое делится каждое из этих чисел.
Свойства НОДа:
1. Если d = НОД(a, b), то существуют такие целые числа x и y, что выполнено неравенство:
d = ax + by
2. НОД(a, b) = НОД(a + b, b)
3. Если \[НОД (a,b)=c\rightarrow НОД \left(\begin{array}{c}\frac{a}{c}, \frac{b}{c}\end{array}\right)=1\]
Часто, чтобы найти НОД, используют алгоритм Евклида.
Алгоритм Евклида (нахождение НОДа):
1. Большее число делим на меньшее.
2. Если делится без остатка, то меньшее число и есть НОД.
3. Если есть остаток, то большее число заменяем остатком.
4. Выполняем алгоритм до тех пор, пока одно число не будет делиться на другое без остатка.
Например:
НОД (148, 96) = НОД (148 - 96, 96) = НОД(52, 96) = НОД(52, 44) = НОД(52 - 44, 44) = НОД(8, 44) =
= НОД(8, 4) = 4
Также справедливо равенство:
НОД(a, b) ∙ НОК(a, b) = a ∙ b
