Question

Найти наибольший общий делитель чисел: 18 и 30; 15 и 45; 72 и 108​

Answer 1

НОД 18 и 30

Делители 18 - 1, 2, 3, 6, 9, 18

Делители 30 - 1, 2, 3, 5, 6, 10, 15, 30

Ответ: НОД 18 и 30 равен 6

НОД 15 и 45

Делители 15 - 1, 3, 5, 15

Делители 45 - 1, 3, 5, 9, 15, 45

Ответ: НОД 15 и 45 равен 15

НОД 72 и 108

Делители 72 - 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72

Делители 108 - 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108

Ответ: НОД 72 и 108 равен 36

Answer 2

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

1. НОД(18, 30):

   • Делим 30 на 18: 30 = 1 * 18 + 12
   • Теперь переходим к следующей итерации с числами 18 и 12.
   • Делим 18 на 12: 18 = 1 * 12 + 6
   • Снова переходим к следующей итерации с числами 12 и 6.
   • Делим 12 на 6: 12 = 2 * 6 + 0

   Как только получили остаток 0, остановились. НОД(18, 30) равен последнему ненулевому остатку, который в данном случае равен 6.

2. НОД(15, 45):

   • Делим 45 на 15: 45 = 3 * 15 + 0

   Опять получили остаток 0, и НОД(15, 45) равен последнему ненулевому остатку, равному 15.

3. НОД(72, 108):

   • Делим 108 на 72: 108 = 1 * 72 + 36
   • Теперь переходим к следующей итерации с числами 72 и 36.
   • Делим 72 на 36: 72 = 2 * 36 + 0

   Опять получили остаток 0, и НОД(72, 108) равен последнему ненулевому остатку, который равен 36.

Итак, наибольшие общие делители для данных пар чисел:

1. НОД(18, 30) = 6
2. НОД(15, 45) = 15
3. НОД(72, 108) = 36