Кратко:
- НОД (наибольший общий делитель) — максимальное целое положительное число, делящее оба числа. Обозначение: $\mathrm{НОД}(a,b)$.
- НОК (наименьшее общее кратное) — наименьшее положительное целое, кратное обоим числам. Обозначение: $\mathrm{НОК}(a,b)$.
Как находят:
1) Евклидов алгоритм (быстро для НОД):
- Пока $b\ne 0$: вычислить $r=a\mathrm{mod}b$, затем положить $a:=b,b:=r$.
- Ответ: $|a|$ — это $\mathrm{НОД}(a,b)$.
Пример: для $a=48,b=18$:
$$48=18\cdot 2+12,18=12\cdot 1+6,12=6\cdot 2+0\Rightarrow \mathrm{НОД}(48,18)=6.$$
2) НОК через НОД:
$$\mathrm{НОК}(a,b)=\frac{|a\cdot b|}{\mathrm{НОД}(a,b)}.$$ В примере: $\mathrm{НОК}(48,18)=\frac{|48\cdot 18|}{6}=144$.
3) Через простые множители (подходит для нескольких чисел):
- Разложить числа на простые: $a=\prod p_i^{{\alpha }_i},b=\prod p_i^{{\beta }_i}$.
- Тогда
$$\mathrm{НОД}(a,b)=\prod p_i^{\min ({\alpha }_i,{\beta }_i)},\mathrm{НОК}(a,b)=\prod p_i^{\max ({\alpha }_i,{\beta }_i)}.$$ - Пример для $48=2^4\cdot 3^1,18=2^1\cdot 3^2$:
$\mathrm{НОД}=2^{\min (4,1)}{3}^{\min (1,2)}=2\cdot 3=6$,
$\mathrm{НОК}=2^{\max (4,1)}{3}^{\max (1,2)}=2^4\cdot 3^2=144$.
4) Для более чем двух чисел: применять попарно или через общие простые степени (минимумы для НОД, максимумы для НОК).
Особые случаи:
- $\mathrm{НОД}(a,0)=|a|$.
- Для ненулевых $a$ $\mathrm{НОК}(a,0)=0$ (обычно $\mathrm{НОК}(0,0)=0$).
- Берут абсолютные значения при отрицательных входах: используются $|a|$, $|b|$.
Если нужно — покажу вычисление для конкретных чисел.