Алгоритм Евклида: наибольший общий делитель (НОД)
Найди наибольший общий делитель двух чисел цепочкой делений, не выписывая делители.
- Россия: 6 класс
- Украина: 6 класс
- Франция: 5 класс
- Великобритания: Year 5
- Иран: 7 класс
- Афганистан: 5 класс
- Сирия: 5 класс
- Палестина: 5 класс
Подсказки для взрослых
Выписывать все делители удобно для небольших чисел, но для больших это долго. Больше 2000 лет назад Евклид нашёл более быстрый способ — цепочку делений. Наибольший общий делитель изучают в 6 классе; алгоритм Евклида — хороший способ пойти дальше.
Раздели большее число на меньшее. Потом раздели делитель на остаток. Продолжай так: каждый раз делитель становится новым делимым, а остаток — новым делителем.
Остановись, когда остаток равен 0. Последний остаток, не равный 0 (последний делитель), и есть НОД.
Почему это работает: любое число, на которое делятся 84 и 60, делит и 84 − 60 = 24, и наоборот. Значит, у чисел 84 и 60 те же общие делители, что у 60 и 24. Каждое деление заменяет пару на меньшую с тем же НОД.
Каждая верная цифра становится зелёной. Если не получается, нажми «Покажи этот шаг».