Задача: найти наибольший общий делитель (НОД) чисел.
а) НОД(108, 72, 96)
Способ 1. Евклидов алгоритм (пошагово)
- Найдем НОД(108, 72):
108 = 72 × 1 + 36
72 = 36 × 2 + 0
НОД(108,72) = 36
- Теперь НОД(36, 96):
96 = 36 × 2 + 24
36 = 24 × 1 + 12
24 = 12 × 2 + 0
НОД(36,96) = 12
Итак, НОД(108, 72, 96) = 12.
Способ 2. Разложение на простые множители (для проверки)
- 108 = 2^2 · 3^3
- 72 = 2^3 · 3^2
- 96 = 2^5 · 3^1
Общие простые множители: 2 и 3.
Минимальные степени: 2^min(2,3,5) = 2^2 = 4; 3^min(3,2,1) = 3^1 = 3.
Произведение: 4 · 3 = 12.
Ответ: 12.
б) НОД(15, 30, 47)
Способ 1. Эвклид разом
- НОД(15, 30) = 15
- Затем НОД(15, 47):
47 = 15 × 3 + 2
15 = 2 × 7 + 1
2 = 1 × 2 + 0
НОД(15, 47) = 1
Итак, НОД(15, 30, 47) = 1.
Способ 2. Разложение на простые множители
- 15 = 3 · 5
- 30 = 2 · 3 · 5
- 47 — простое число, не делится на 2, 3 или 5
Общего множителя нет, кроме единицы. Значит, НОД = 1.
Ответ: 1.
Если хочешь, могу привести ещё один вид доказательства или разобрать похожие примеры.
