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

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 - наибольший общий делитель