2. С помощью алгоритма Евклида найдите НОД чисел 42628 и 33124

Ответ:

1) Делим большее число на меньшее: 42628 = 33124 * 1 + 9504 2) Теперь делим 33124 на остаток 9504: 33124 = 9504 * 3 + 4612 3) Делим 9504 на остаток 4612: 9504 = 4612 * 2 + 280 4) Делим 4612 на остаток 280: 4612 = 280 * 16 + 132 5) Делим 280 на остаток 132: 280 = 132 * 2 + 16 6) Делим 132 на остаток 16: 132 = 16 * 8 + 4 7) Делим 16 на остаток 4: 16 = 4 * 4 + 0 Последний ненулевой остаток равен 4. Значит, НОД(42628, 33124) = 4.

Проверка за 10 секунд: Убедитесь, что 4 является делителем обоих чисел.

Доп. профит: Алгоритм Евклида позволяет быстро находить НОД даже для очень больших чисел.