Используя алгоритм Евклида, найдите нод для чисел 126 и 15.
Пример алгоритма Евклида рассмотрим по шагам.
1. 126 > 15, будем делить 126 на 15.
2. Делим 126 на 15, получаем 8 и остаток 6:
126 : 15 = 8
остаток 6
остаток 6
Перепишем это так:
126 = 15 * 8 + 6
3. Делим число 15 на остаток 6, получим частное 2 и остаток 3:
15 : 6 = 2
остаток 3
остаток 3
Это можно записать так:
15 = 6 * 2 + 3
4. Делим 6 на остаток 3:
6 : 3 = 2
остаток 0
остаток 0
Это можно записать так:
6 = 3 * 2 + 0 =
3 * 2
3 * 2
5. Так как мы получили ноль в остатке, деление останавливаем. НОД равен 3.
Перепишем алгоритм нахождения НОД без пояснений:
1. 126 = 15 * 8 + 6
2. 15 = 6 * 2 + 3
3. 6 = 3 * 2
2. 15 = 6 * 2 + 3
3. 6 = 3 * 2
Ответ:
НОД(126, 15) = 3