Наибольший общий делитель (НОД): как решать
Найти наибольший общий делитель.
Определения
- Общий делитель
- Число, на которое делятся оба данных числа. Для 18 и 24 общие делители - 1, 2, 3, 6.
- Наибольший общий делитель (НОД)
- Самый большой из общих делителей. НОД(18, 24) = 6.
- Взаимно простые числа
- Числа, у которых НОД равен единице: 8 и 15. Общих делителей, кроме единицы, у них нет.
Объяснение
НОД нужен прежде всего для сокращения дробей: разделив числитель и знаменатель на их НОД, получаем несократимую дробь сразу, за один шаг. Кроме того, НОД встречается в задачах на разрезание и раскладывание - когда надо разделить два набора на одинаковые части наибольшего размера.
Первый способ - через разложение на простые множители. Раскладываем оба числа, выписываем общие множители и перемножаем их. Для 18 = 2 · 3 · 3 и 24 = 2 · 2 · 2 · 3 общими будут одна двойка и одна тройка, значит НОД = 2 · 3 = 6. Каждый общий множитель берут в наименьшей степени из встречающихся.
Второй способ - алгоритм Евклида, он быстрее для больших чисел и не требует разложения. Делим большее число на меньшее с остатком, потом меньшее на остаток, и так пока остаток не станет нулём. Последний ненулевой остаток и есть НОД.
Для 18 и 24 это выглядит так: 24 : 18 = 1 и остаток 6; затем 18 : 6 = 3 и остаток 0. Последний ненулевой остаток - 6, значит НОД равен 6. Алгоритм работает потому, что общие делители пары чисел совпадают с общими делителями меньшего числа и остатка.
Проверить ответ легко: оба числа обязаны делиться на найденный НОД нацело, а после деления полученные частные обязаны стать взаимно простыми. Для 18 и 24 частные 3 и 4 - у них общих делителей нет, значит НОД найден верно, а не занижен.
Если числа взаимно простые, их НОД равен единице. Это не ошибка и не тупик: значит, дробь из этих чисел уже несократима, а наборы нельзя разделить на равные части крупнее одной штуки.
Правила и формулы
- НОД через разложение: общие множители в наименьшей степени
18 = 2 · 3², 24 = 2³ · 3 → НОД = 2 · 3 = 6 - Алгоритм Евклида: делим с остатком, пока остаток не станет нулём
- НОД - последний ненулевой остаток
24 : 18 ост. 6; 18 : 6 ост. 0 → НОД = 6 - Проверка: частные после деления на НОД взаимно просты
18 : 6 = 3, 24 : 6 = 4 - У взаимно простых чисел НОД равен единице
Порядок действий
- Выберите способ: разложение - для небольших чисел, алгоритм Евклида - для крупных.
- При разложении выпишите общие простые множители в наименьшей степени.
- При алгоритме Евклида делите большее на меньшее с остатком и повторяйте.
- Остановитесь, когда остаток станет нулём, - предыдущий остаток и есть НОД.
- Проверьте: разделите оба числа на НОД, частные обязаны быть взаимно простыми.
Разбор примеров
- Раскладываем: 18 = 2 · 3 · 3, 24 = 2 · 2 · 2 · 3.
- Общие множители: одна двойка и одна тройка.
- 2 · 3 = 6
- Проверка: 18 : 6 = 3, 24 : 6 = 4, они взаимно просты.
- 48 : 36 = 1, остаток 12.
- 36 : 12 = 3, остаток 0.
- Последний ненулевой остаток - 12.
- Раскладываем: 8 = 2 · 2 · 2, 15 = 3 · 5.
- Общих простых множителей нет.
Где обычно ошибаются
- Берут общие множители в наибольшей степени вместо наименьшей.
- Находят какой-нибудь общий делитель и останавливаются, не проверив, наибольший ли он.
- В алгоритме Евклида берут последний остаток, который равен нулю, вместо предыдущего.
Примеры с решением
- 35 = 5 · 7
- 50 = 5 · 10
- Общий множитель: 5. У 7 и 10 общих делителей больше нет, значит НОД = 5.
- 6 = 3 · 2
- 33 = 3 · 11
- Общий множитель: 3. У 2 и 11 общих делителей больше нет, значит НОД = 3.
- 20 = 5 · 4
- 55 = 5 · 11
- Общий множитель: 5. У 4 и 11 общих делителей больше нет, значит НОД = 5.
- 90 = 10 · 9
- 80 = 10 · 8
- Общий множитель: 10. У 9 и 8 общих делителей больше нет, значит НОД = 10.
- 90 = 10 · 9
- 50 = 10 · 5
- Общий множитель: 10. У 9 и 5 общих делителей больше нет, значит НОД = 10.
Подсказки, если не получается
- Ищем самый большой общий делитель обоих чисел.
- Разложи оба числа на множители и найди общие.
- Проверь: 35 : 5 и 50 : 5 делятся нацело?
Другие темы раздела «Делимость»
- Признаки делимости
- Простые и составные числа
- Делители числа
- Наименьшее общее кратное (НОК)
- Деление с остатком
Полная справка по разделу — на странице Делимость.