Question

Знайти НСД чисел 45 і 110

Answer 1

45 | 3                                 110 | 2

15 | 3                                  55 | 5

5 | 5                                   11 | 11

1                                         1

45 = 3² · 5                         110 = 2 · 5 · 11

НОД = 5 - наибольший общий делитель

45 : 5 = 9                          110 : 5 = 22

Ответ: НСД (45; 110) = 5.

Answer 2

НСД (найбільший спільний дільник) чисел 45 і 110 можна знайти за допомогою алгоритму Евкліда.

Алгоритм Евкліда полягає у послідовних діленнях одного числа на інше з наступним заміщенням дільника дільником за залишок до тих пір, поки залишок не стане рівним нулю. НСД визначається як останній ненульовий залишок у цьому процесі.

Давайте застосуємо цей алгоритм до чисел 45 і 110:

1. Ділимо 110 на 45 і отримуємо залишок 20.
2. Тепер ділимо 45 на 20 і отримуємо залишок 5.
3. Ділимо 20 на 5 і отримуємо залишок 0.

Останній ненульовий залишок був 5, отже, НСД(45, 110) = 5.