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