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

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

Натуральное число a называют делителем натурального числа b, если b делится на a без остатка. Например, 4 — делитель 20, потому что 20 : 4 = 5. Проверка делимости показывает, можно ли разделить число на равные части указанного размера. Это понятие нужно, чтобы находить делители и сравнивать их у разных чисел.

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

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

Два числа называют взаимно простыми, если их наибольший общий делитель равен 1. Это не значит, что оба числа обязательно простые: например, 8 и 9 — составные, но НОД(8, 9) = 1. Значит, у них нет общего делителя больше единицы. Такое определение позволяет судить о наличии общих делителей, не сравнивая числа по величине.

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

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

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

Если числа большие, удобно разложить их на простые множители — простые числа, произведение которых даёт исходное число. Затем оставляют только те простые множители, которые встречаются в разложениях обоих чисел, и перемножают их. Это работает потому, что любой общий делитель должен состоять из множителей, которые есть в каждом из исходных чисел. Множители, встречающиеся только в одном разложении, не могут войти в общий делитель.

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

Когда НОД равен 1, общих простых множителей у чисел нет, кроме числа 1, которое не является простым множителем. Поэтому числа называют взаимно простыми. Они могут быть составными: например, разложения 8 = 2³ и 9 = 3² не содержат одинаковых простых множителей. Значит, общий делитель у них только 1, хотя каждое число само имеет делители помимо 1 и себя.

Способы нахождения наибольшего общего делителя

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

Разбор задач

Найдите НОД чисел 12 и 18.

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

1. Выпишем делители 12: 1, 2, 3, 4, 6, 12.
2. Выпишем делители 18: 1, 2, 3, 6, 9, 18.
3. Совпадают 1, 2, 3 и 6. Наибольший из них — 6; проверка: 12 : 6 = 2, 18 : 6 = 3.

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

Найдите НОД чисел 36 и 60 разложением на простые множители.

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

1. Разложим числа: 36 = 2² · 3², 60 = 2² · 3 · 5.
2. Общие простые множители — 2 и 3. Для двойки берём 2², а для тройки — 3¹, поскольку такая степень меньше, чем 3².
3. Перемножим: 2² · 3 = 4 · 3 = 12. Проверим: 36 : 12 = 3, 60 : 12 = 5.

Ответ: НОД(36, 60) = 12.

Для двух участков длиной 84 м и 126 м нужно нарезать одинаковые отрезки наибольшей возможной длины без остатка. Какова длина отрезка и сколько их получится?

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

1. Разложим длины на простые множители: 84 = 2² · 3 · 7, 126 = 2 · 3² · 7.
2. Общие множители с наименьшими степенями: 2 · 3 · 7 = 42. Значит, НОД(84, 126) = 42 м — наибольшая длина без остатка.
3. На участке 84 м получится 84 : 42 = 2 отрезка. На участке 126 м получится 126 : 42 = 3 отрезка.

Ответ: длина каждого отрезка — 42 м; на первом участке получится 2 отрезка, на втором — 3.

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

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

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

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

Разные числа не обязательно взаимно простые: например, у 12 и 18 есть общий делитель 6. Эту ошибку допускают, принимая различие чисел за отсутствие общих делителей. Взаимную простоту устанавливают только по НОД: числа взаимно просты, если он равен 1.

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

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

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

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

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