Найдите наибольший общий делитель чисел 12 и 18.
Алгоритм НОД
Разложим числа 12 и 18 на множители, далее определим их НОД (наибольший общий делитель).
Как разложить число на множители можно посмотреть в статье Разложить на множители.
Найдем наибольший общий делитель 12 и 18.
Будем искать НОД по шагам.
1. Разложим на множители число 18:
| 18 | 2 |
| 9 | 3 |
| 3 | 3 |
| 1 |
Получаем разложение на множители числа 18:
2. Разложим на множители число 12:
| 12 | 2 |
| 6 | 2 |
| 3 | 3 |
| 1 |
Получаем разложение на множители числа 12:
3. Какие множители являются общими в этих двух разложениях чисел на множители?
12 –> (2, 2, 3)
Совпадают (2, 3)
4. Произведение совпадающих множителей и является наибольшим общим делителем чисел 12 и 18:
Ответ: наибольшим общим делителем чисел 12 и 18 является число 6:
Кроме того, можно, используя алгоритм Евклида, найти нод для чисел 12 и 18.