Question

Знайдіть НСД двох чисела) 15 31: б) 55 і 66: в) 108 і 105​

Answer 1

15 | 3                              31 - простое число

5 | 5

1

15 = 3 · 5

НОД (15 и 31) = 1 - наибольший общий делитель

Числа 15 и 31 взаимно простые, так как у них нет общих делителей, кроме единицы.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

55 | 5                              66 | 2

11 | 11                                33 | 3

1                                       11 | 11

55 = 5 · 11                        1

                                       66 = 2 · 3 · 11

НОД (55 и 66) = 11 - наибольший общий делитель

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

108 | 2                               105 | 3

54 | 2                                 35 | 5

27 | 3                                 7 | 7

9 | 3                                   1

3 | 3                                   105 = 3 · 5 · 7

1

108 = 2 · 3³

НОД (108 и 105) = 3 - наибольший общий делитель

Answer 2

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

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

а) НСД(15, 31):

1. 31 = 15 * 2 + 1
2. 15 = 1 * 15 + 0

Останній ненульовий залишок - 1. Отже, НСД(15, 31) = 1.

б) НСД(55, 66):

1. 66 = 55 * 1 + 11
2. 55 = 11 * 5 + 0

Останній ненульовий залишок - 11. Отже, НСД(55, 66) = 11.

в) НСД(108, 105):

1. 108 = 105 * 1 + 3
2. 105 = 3 * 35 + 0

Останній ненульовий залишок - 3. Отже, НСД(108, 105) = 3.