Найдите наибольший общий делитель: 45 и 65?

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

Способ 1. Алгоритм Евклида (пошагово)

1. 65 разделить на 45: 65 = 45 × 1 + 20.
2. Теперь найти НОД(45, 20): разделим 45 на 20: 45 = 20 × 2 + 5.
3. Теперь НОД(20, 5): разделим 20 на 5: 20 = 5 × 4 + 0.
4. Когда остаток стал 0, последний ненулевой остаток — это НОД. Здесь НОД = 5.

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

• 45 = 3² × 5
• 65 = 5 × 13 Общие простые множители: только 5 (и в обоих случаях его степень в общей части минимальна — 5¹). Следовательно, НОД = 5.

Проверка 5 делит и 45, и 65. Большого общего делителя больше 5 нет, потому что 65 не делится на 3 или на 9, и единственный общий простой множитель — это 5.

Ответ: НОД(45, 65) = 5.