2. Наибольший общий делитель. Взаимно простые числа

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

Делитель числа — натуральное число, на которое данное число делится без остатка. Например, 12 делится без остатка на 1, 2, 3, 4, 6 и 12, поэтому это его делители. Перечень делителей помогает выяснить, какие равные группы можно составить из предметов или какие числа могут делить данное число.

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

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

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

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

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

Для небольших чисел НОД удобно искать перебором. Сначала выпиши делители первого числа, затем — второго, чтобы ничего не пропустить. Отметь числа, которые есть в обоих списках, и выбери самое большое: именно оно делит оба числа и является НОД.

Чтобы проверить, взаимно ли просты числа, достаточно найти их общие делители. Если среди них только 1, НОД равен 1 и числа взаимно простые. Например, у 8 и 15 общий делитель только 1; если же находится общий делитель больше 1, взаимной простоты нет.

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

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

Общие делители, НОД и взаимно простые числа

Сравни пары чисел в таблице. В столбце «Общие делители» перечислены числа, которые делят оба числа из пары без остатка.

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

Разбор задач

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

1. Делители 18: 1, 2, 3, 6, 9, 18. Делители 24: 1, 2, 3, 4, 6, 8, 12, 24. Списки составлены так, чтобы проверить деление каждого числа без остатка.
2. Общие делители — 1, 2, 3 и 6. Наибольшее из них — 6, поэтому НОД(18, 24) = 6. Ответ: 6.

Задача 2. Сократите дробь 24/36. Чтобы значение дроби не изменилось, нужно разделить числитель и знаменатель на одно и то же число. Возьмём их НОД: деление на наибольший общий делитель сразу даст несократимую дробь.

1. Находим НОД(24, 36). Общие делители этих чисел: 1, 2, 3, 4, 6 и 12, а наибольший из них — 12. Значит, оба члена дроби можно разделить на 12.
2. Делим числитель и знаменатель: 24 : 12 = 2, 36 : 12 = 3. Получаем 2/3; числа 2 и 3 не имеют общего делителя, кроме 1. Ответ: 2/3.

Задача 3. Есть 36 красных и 48 синих карандашей. Их нужно разложить в одинаковые наборы так, чтобы в каждом наборе было поровну карандашей каждого цвета и все карандаши были использованы. Какое наибольшее число наборов можно составить? Число наборов должно делить и 36, и 48 без остатка. Поэтому ищем общий делитель этих чисел, а для наибольшего количества наборов — их НОД.

1. Находим НОД(36, 48). Разложения на простые множители: 36 = 2 · 2 · 3 · 3, а 48 = 2 · 2 · 2 · 2 · 3. Общие множители — два числа 2 и одно число 3, поэтому НОД = 2 · 2 · 3 = 12.
2. Значит, можно составить 12 одинаковых наборов. В каждом будет 36 : 12 = 3 красных и 48 : 12 = 4 синих карандаша; все карандаши использованы. Ответ: 12 наборов.

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

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

Другая ошибка — считать, что взаимно простые числа должны сильно отличаться. Разница между числами не определяет их взаимную простоту: важны только общие делители. Например, соседние числа 8 и 9 взаимно просты; проверь, что оба делятся без остатка только на общий делитель 1.

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

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

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

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

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

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

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