Русский
Наибольший общий делитель через общие простые множители или алгоритм Евклида.
Обновлено
Курс математики Coddy учит самому методу: вы прорабатываете каждый шаг на интерактивной доске и узнаёте, где именно ход пошёл не так.
Делитель числа делит его без остатка: делители 12 — это 1, 2, 3, 4, 6 и 12. Общий делитель двух чисел встречается в обоих списках. Наибольший общий делитель — самый большой из общих: наибольшее число, которое делит оба нацело.
НОД чисел 24 и 36 равен 12. Оба делятся на 1, 2, 3, 4, 6 и 12, и 12 — наибольший из них. В английском его называют greatest common divisor (GCD) или highest common factor (HCF); все названия означают в точности одно и то же, и какое вам преподавали — вопрос скорее географии.
Его главная работа — сокращение. Чтобы привести 24/36 к несократимому виду, разделите обе части на НОД: 24 ÷ 12 = 2 и 36 ÷ 12 = 3, получится 2/3 за один шаг. Деление на меньший общий делитель тоже работает, но заставляет идти по кругу — и ровно поэтому ищут наибольший.
Впишите два или больше целых числа через запятую или пробел: 24, 36 или 54 24 36. До десяти за раз.
НОД наверху. Ниже тот же ответ получается через общие простые множители и — ровно для двух чисел — по алгоритму Евклида.
Каждая строка — простое. НОД берёт наименьший показатель в строке, а любая строка с прочерком выпадает целиком, потому что множитель, общий лишь для части чисел, общим не является.
Каждая строка делит и записывает остаток; следующая повторяет с делителем и этим остатком. Когда остаток становится нулём, предыдущий и есть ваш ответ.
Пары, которые попадаются чаще всего, с причиной, а не только с результатом.
| Числа | НОД | Почему |
|---|---|---|
| 24 и 36 | 12 | У обоих есть 2² и 3 |
| 48 и 18 | 6 | У обоих есть 2 и 3 |
| 8 и 12 | 4 | У обоих есть 2², но тройка только у 12 |
| 15 и 25 | 5 | У обоих есть одна пятёрка |
| 8 и 9 | 1 | Общих простых нет — взаимно простые |
| 7 и 21 | 7 | 7 делит 21, поэтому меньшее число и есть НОД |
| 54, 24 и 36 | 6 | 2 и 3 есть во всех трёх |
24, 3624 = 2³ · 3 и 36 = 2² · 3². Для каждого простого берём меньший показатель: 2² (у 24 три двойки, а у 36 только две) и 3¹ (у 36 две тройки, а у 24 только одна). Получается 2² · 3 = 12. Путь Евклида согласен: 36 = 1 × 24 + 12, затем 24 = 2 × 12 + 0, значит последний ненулевой остаток равен 12.
24, 36НОД равен 12, поэтому делим обе части на него: 24 ÷ 12 = 2 и 36 ÷ 12 = 3, получается 2/3. Если бы вы заметили только множитель 2, вы получили бы 12/18, затем 6/9, затем 2/3 — то же место, но на три шага позже. Именно поиск наибольшего общего делителя превращает это в один шаг.
8, 98 = 2³ и 9 = 3². Общих простых у них нет, поэтому в НОД нечего положить, и ответ равен 1. Такие числа называют взаимно простыми. Это также значит, что дробь 8/9 уже несократима.
48, 1848 = 2 × 18 + 12. Теперь повторяем с 18 и 12: 18 = 1 × 12 + 6. Повторяем с 12 и 6: 12 = 2 × 6 + 0. Остаток нулевой, значит предыдущий остаток, 6, и есть НОД. Обратите внимание, что ничего не разлагалось — именно поэтому способ работает на числах в сотни знаков.
