3.5. Наибольший общий делитель

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

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

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

Наибольший общий делитель, сокращённо НОД, — самое большое число, на которое без остатка делятся все данные числа. НОД чисел a и b обозначают НОД(a, b). Среди общих делителей он показывает самый большой размер равных частей, на которые можно разделить оба числа.

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

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

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

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

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

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

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

Как определить НОД двух чисел

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

Разбор задач

Задача. Найди все делители числа 20. Нужно проверить натуральные числа, начиная с 1, и оставить только те, на которые 20 делится без остатка. Чтобы не пропустить делитель, можно идти по порядку и записывать результат каждой проверки.

1. Проверяем 1: число 20 делится на 1 без остатка, значит, 1 — делитель.
2. Проверяем 2, 3 и 4: 20 делится на 2 и 4, но не делится на 3 без остатка.
3. Проверяем 5, 6 и 7: 20 делится на 5, но при делении на 6 и 7 остаётся остаток.
4. Проверяем 8, 9 и 10: из них подходит 10, так как 20 : 10 = 2.
5. Числа больше 10 проверяем до 20: делителем оказывается 20, а остальные числа в этом промежутке не подходят.

Ответ: 1, 2, 4, 5, 10, 20.

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

1. Записываем делители 18: 1, 2, 3, 6, 9, 18.
2. Записываем делители 30: 1, 2, 3, 5, 6, 10, 15, 30.
3. Находим совпадения: 1, 2, 3 и 6 делят без остатка оба числа.
4. Сравниваем общие делители: самый большой из них — 6.
5. Проверяем результат: 18 : 6 = 3 и 30 : 6 = 5, деления проходят без остатка.

Ответ: НОД(18, 30) = 6.

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

1. Выписываем делители 24: 1, 2, 3, 4, 6, 8, 12, 24.
2. Выписываем делители 35: 1, 5, 7, 35.
3. Сравниваем списки: в обоих встречается только 1.
4. Значит, НОД(24, 35) = 1; другого общего делителя нет.

Ответ: числа 24 и 35 взаимно простые.

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

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

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

Если при составлении списка пропустить делитель, можно не заметить общий делитель или получить неверный НОД. Например, забытый делитель 6 в списке делителей 12 и 18 изменит вывод. Проверяй натуральные числа по порядку, а после составления перечня убеждайся, что ни одно подходящее число не потерялось.

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

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

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

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

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

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