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

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

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

Наибольший общий делитель, или НОД, — самый большой из общих делителей данных чисел. НОД(a, b) — это обозначение НОД чисел a и b: буквы в скобках показывают, для каких чисел его находят. Например, НОД(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.

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

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

Почему учитывают только общие множители? НОД должен делить оба исходных числа, поэтому в его разложении могут быть только множители, вошедшие в оба разложения. А если взять больше повторений какого-либо множителя, чем есть в одном из чисел, полученное произведение уже не будет делителем этого числа. Например, 36 = 2² · 3², а 60 = 2² · 3 · 5, поэтому НОД равен 2² · 3 = 12.

Если у чисел нет общих простых множителей, их разложения не дают общего произведения больше 1. Тогда общий делитель только один — 1, а числа взаимно просты. Верно и обратное: если числа взаимно просты, общих простых множителей у них быть не может, иначе произведение такого множителя делило бы оба числа и было бы больше 1. Например, у 8 = 2³ и 15 = 3 · 5 общих простых множителей нет.

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

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

Разбор задач

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

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

Ответ: 6.

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

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

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

Задача 3. Определите, взаимно ли просты числа 24 и 35, и обоснуйте ответ. Чтобы ответить, найдём их НОД разложением на простые множители. Если он равен 1, числа взаимно просты.

1. Разложим числа на простые множители: 24 = 2³ · 3, а 35 = 5 · 7. В первом разложении есть множители 2 и 3, во втором — 5 и 7.
2. Общих простых множителей нет. Следовательно, произведение общих множителей равно 1, то есть НОД(24, 35) = 1.
3. По определению числа с НОД, равным 1, взаимно просты. Значит, 24 и 35 взаимно просты, хотя оба числа составные.

Ответ: да, числа взаимно просты; их НОД равен 1.

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

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

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

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

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

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

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

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

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

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