Найди наибольший общий делитель чисел 45,63 и 105

Задача: найти наибольший общий делитель (НОД) чисел 45, 63 и 105.

Способ 1. По очередному вычислению НОД двух чисел (алгоритм Евклида)

• Сначала найдём НОД(45, 63):
  • 63 = 45·1 + 18
  • 45 = 18·2 + 9
  • 18 = 9·2 + 0
  • Значит, НОД(45,63) = 9
• Теперь найдём НОД(9, 105):
  • 105 = 9·11 + 6
  • 9 = 6·1 + 3
  • 6 = 3·2 + 0
  • Значит, НОД(9,105) = 3
• Итак, НОД(45,63,105) = 3.

Способ 2. Разложение на простые множители

• 45 = 3^2 · 5
• 63 = 3^2 · 7
• 105 = 3 · 5 · 7 Общие множители: только 3, минимальная степень 3 — это 3^1 = 3. Следовательно, НОД = 3.

Ответ: 3.