Question

Найдите Нод(12,75) Нод(12,45) Нод(12,36) Нод(18,54) Нод(17,18)

Answer 1

1) нод(12,75) = 3
12 /2       75 / 5
6  / 2       15 / 5
3 / 3         3 / 3
1              1
2) нод(12,45) = 3 
12 / 2   45 / 5 
6  / 2     9  / 3
3 / 3       3 / 3
1              1
3) нод (12,36) = 2*2*3= 12
12 / 2     36 / 2 
 6 / 2      18 / 2
 3 / 3       9  / 3
  1            3 / 3
                  1          
4) нод (18,54) = 2*3*3= 18
18 / 2   54 / 2
9  / 3    27 / 3
3 / 3     9  / 3
1          3 / 3 
             1
5) нод (17,18) = 1
17 / 17   18 / 2
1              9 / 3
               3 / 3
                 1

Answer 2

Чтобы найти наибольший общий делитель (НОД) для пары чисел, можно использовать алгоритм Эвклида. Алгоритм Эвклида основан на простой итеративной процедуре нахождения НОД двух чисел.

НОД(12, 75): 1. Делим 75 на 12. Получаем остаток 3. 2. Заменяем 75 на 12, а 12 на 3. 3. Делим 12 на 3. Получаем остаток 0. 4. Так как остаток равен 0, то 3 является НОД(12, 75).

НОД(12, 45): 1. Делим 45 на 12. Получаем остаток 9. 2. Заменяем 45 на 12, а 12 на 9. 3. Делим 12 на 9. Получаем остаток 3. 4. Заменяем 9 на 3, а 3 на 0. 5. Так как остаток равен 0, то 3 является НОД(12, 45).

НОД(12, 36): 1. Делим 36 на 12. Получаем остаток 0. 2. Так как остаток равен 0, то 12 является НОД(12, 36).

НОД(18, 54): 1. Делим 54 на 18. Получаем остаток 0. 2. Так как остаток равен 0, то 18 является НОД(18, 54).

НОД(17, 18): 1. Делим 18 на 17. Получаем остаток 1. 2. Заменяем 18 на 17, а 17 на 1. 3. Делим 17 на 1. Получаем остаток 0. 4. Так как остаток равен 0, то 1 является НОД(17, 18).

Таким образом, НОД(12, 75) = 3, НОД(12, 45) = 3, НОД(12, 36) = 12, НОД(18, 54) = 18 и НОД(17, 18) = 1.