19.6. Наибольший общий делитель двух чисел

Определения и обозначения

Делитель числа — натуральное число, на которое данное число делится без остатка. Например, 3 — делитель 12, потому что 12 : 3 = 4. Проверяя делитель, нужно убедиться, что частное целое и остатка нет. Это понятие помогает определить, какими равными группами можно разделить предметы.

Общий делитель двух чисел — число, которое является делителем каждого из них. Например, 3 — общий делитель 12 и 18, так как оба числа делятся на 3 без остатка. Чтобы найти общий делитель, надо проверить его отдельно для каждого числа. Это позволяет отобрать числа, подходящие сразу для обоих.

Наибольший общий делитель двух чисел — наибольшее число среди их общих делителей. Его обозначают НОД, например: НОД(12, 18) = 6. Общих делителей может быть несколько, поэтому недостаточно найти любой из них: нужно выбрать самый большой. НОД показывает, на какое наибольшее число равных частей можно разделить оба количества.

Числа называют взаимно простыми, если их наибольший общий делитель равен 1. Например, 8 и 15 взаимно просты: их единственный общий натуральный делитель — 1. Это не означает, что оба числа должны быть простыми. Такое определение позволяет быстро установить, есть ли у двух чисел общий делитель больше единицы.

Как это устроено

Для небольших чисел НОД удобно искать перебором делителей. Выпиши делители первого числа, а затем — второго и сравни два списка. Например, у 12 делители 1, 2, 3, 4, 6, 12, а у 18 — 1, 2, 3, 6, 9, 18. Общие делители здесь 1, 2, 3 и 6, поэтому НОД равен 6. Такой способ нагляден, но для больших чисел списки быстро становятся длинными.

Для больших чисел используют алгоритм Евклида, основанный на делении с остатком. Пусть большее число разделили на меньшее: делитель и остаток связаны равенством «делимое = делитель · частное + остаток». Если число делит и делимое, и делитель, оно делит также их разность — остаток. И наоборот: общий делитель делителя и остатка делит и делимое, поэтому общие делители пары не меняются.

Повторяй деление с остатком, каждый раз деля предыдущий делитель на полученный остаток. Так исходная пара чисел сменяется парой «делитель и остаток», но НОД остаётся тем же. Остатки при делении натуральных чисел становятся меньше предыдущих делителей, поэтому процесс не может продолжаться бесконечно. Продолжать нужно до деления, при котором остаток окажется равным нулю.

Последний ненулевой остаток и есть НОД исходных чисел. На следующем шаге остаток равен нулю, значит, предыдущий делитель делится на последний ненулевой остаток без остатка. По свойству алгоритма НОД на каждом шаге сохраняется, а на последней паре его значение совпадает с этим ненулевым остатком. Поэтому ответом не является нулевой остаток.

Результат полезно проверить делением: найденное число должно делить оба исходных числа без остатка. Одной этой проверки недостаточно, потому что делить оба числа могут и другие, меньшие числа. Однако алгоритм Евклида гарантирует, что общий делитель больше найденного не существует. При переборе это видно непосредственно: среди общих делителей выбран самый большой.

Поиск наибольшего общего делителя

Для небольших чисел выбирай перебор, а для чисел покрупнее — алгоритм Евклида. В последнем случае на каждом шаге записывай делитель и остаток, чтобы не перепутать их в новой паре. В конце проверь, что ответ делит оба исходных числа.

Разбор задач

Задача 1. Найти НОД чисел 12 и 18, выписав делители каждого числа. Перебор здесь подходит: делителей немного, и их легко сравнить. Ответ должен быть общим делителем и при этом самым большим из них.

1. Выпишем делители 12: 1, 2, 3, 4, 6, 12.
2. Выпишем делители 18: 1, 2, 3, 6, 9, 18.
3. Оставим числа, которые есть в обоих списках: 1, 2, 3, 6.
4. Выберем наибольшее из общих чисел — 6.

Ответ: НОД(12, 18) = 6. Проверка: 12 : 6 = 2, а 18 : 6 = 3, поэтому оба числа делятся на 6 без остатка. В списке общих делителей нет числа больше 6.

Задача 2. Найти НОД чисел 48 и 18 алгоритмом Евклида. Делим большее число на меньшее, а затем на каждом следующем шаге делим предыдущий делитель на полученный остаток. Записываем остаток, чтобы последовательно получить новую пару.

1. 48 : 18 = 2, остаток 12, то есть 48 = 18 · 2 + 12.
2. Делим предыдущий делитель на остаток: 18 : 12 = 1, остаток 6.
3. Теперь делим 12 на 6: 12 : 6 = 2, остаток 0.
4. Последний ненулевой остаток — 6, поэтому НОД равен 6.

Ответ: НОД(48, 18) = 6. Проверка: 48 : 6 = 8 и 18 : 6 = 3. Нулевой остаток показывает, что деление завершено, а последний ненулевой остаток даёт искомый результат.

Задача 3. Найти НОД чисел 252 и 105 и определить, являются ли они взаимно простыми. Перебор делителей потребовал бы длинных списков, поэтому используем алгоритм Евклида. Взаимная простота определяется только после того, как найден НОД.

1. 252 : 105 = 2, остаток 42: 252 = 105 · 2 + 42.
2. 105 : 42 = 2, остаток 21: 105 = 42 · 2 + 21.
3. 42 : 21 = 2, остаток 0.
4. Последний ненулевой остаток равен 21; сравним его с 1.

Ответ: НОД(252, 105) = 21. Числа не являются взаимно простыми, потому что их НОД не равен 1. Проверка: 252 : 21 = 12 и 105 : 21 = 5.

Типичные ошибки

Иногда НОД путают с наименьшим общим делителем. Так происходит, потому что обращают внимание на слово «общий», но забывают сравнить величины; единица часто является общим делителем, однако обычно не самым большим. Чтобы проверить ответ, перечисли общие делители или выполни алгоритм Евклида и выбери наибольший.

При алгоритме Евклида можно неправильно составить пару для следующего деления: например, разделить остаток на прежний делитель. Ошибка возникает, если не записывать, какое число было делителем, а какое — остатком. На следующем шаге именно предыдущий делитель делят на полученный остаток; запиши равенство с остатком, чтобы проверить порядок.

Другой промах — назвать ответом последний делитель, не проследив за остатками, или принять за НОД нулевой остаток. В цепочке делений важно отметить последний остаток, который не равен нулю: именно он сохраняет значение НОД исходных чисел. Проверь конец вычислений: после него должно идти деление с остатком 0.

Не следует объявлять числа взаимно простыми только потому, что среди найденных общих делителей не встретилось число больше 1. Такой вывод может быть следствием неполного перебора или ошибки в вычислениях. Сначала найди НОД корректно, а затем сравни его с единицей: взаимная простота означает, что НОД равен 1.

Связь с другими темами

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

Что запомнить

• НОД — наибольшее число, на которое делятся оба числа.
• НОД можно найти перебором общих делителей.
• Алгоритм Евклида основан на делении с остатком.
• В алгоритме Евклида делитель и остаток последовательно становятся новой парой чисел.
• Последний ненулевой остаток равен НОД исходных чисел.
• Числа взаимно просты тогда и только тогда, когда их НОД равен 1.