Алгоритм Евклида, НОД. Пример. НОД для чисел 126 и 15

Используя алгоритм Евклида, найдите нод для чисел 126 и 15.

Пример алгоритма Евклида рассмотрим по шагам.

1. 126 > 15, будем делить 126 на 15.

2. Делим 126 на 15, получаем 8 и остаток 6:

126 : 15 = 8
остаток 6

Перепишем это так:

126 = 15 * 8 + 6

3. Делим число 15 на остаток 6, получим частное 2 и остаток 3:

15 : 6 = 2
остаток 3

Это можно записать так:

15 = 6 * 2 + 3

4. Делим 6 на остаток 3:

6 : 3 = 2
остаток 0

Это можно записать так:

6 = 3 * 2 + 0 =
3 * 2

5. Так как мы получили ноль в остатке, деление останавливаем. НОД равен 3.

Перепишем алгоритм нахождения НОД без пояснений:

1. 126 = 15 * 8 + 6
2. 15 = 6 * 2 + 3
3. 6 = 3 * 2

Ответ:

НОД(126, 15) = 3