§ 14. Взаимно простые числа

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

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

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

Взаимно простые числа — два натуральных числа, НОД которых равен 1. Иными словами, их единственный общий натуральный делитель — единица. Такое определение не требует, чтобы сами числа были простыми.

Попарно взаимно простыми называют несколько чисел, если любая выбранная из них пара взаимно проста. Для чисел a, b и c это означает сразу три условия: НОД(a, b) = 1, НОД(a, c) = 1 и НОД(b, c) = 1. Проверять нужно именно каждую пару.

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

Условие НОД(a, b) = 1 точно описывает взаимную простоту, потому что НОД собирает наибольший из всех общих делителей. Если он равен 1, большего общего делителя нет, а значит, нет и другого общего делителя. Если НОД больше 1, найденное число сразу показывает, что числа не взаимно просты.

При разложении на простые множители НОД получают, выбирая общие простые множители с наименьшими показателями степеней. Поэтому отсутствие общих простых множителей даёт произведение без множителей, то есть 1. Например, в разложениях 35 = 5 · 7 и 48 = 2⁴ · 3 общих простых множителей нет, значит, числа взаимно просты.

Для больших чисел разложение может быть неудобным, поэтому применяют алгоритм Евклида. Больший делитель заменяют остатком от деления, поскольку НОД(a, b) = НОД(b, a остаток). Процесс продолжают, пока остаток не станет нулём; последний ненулевой остаток и есть НОД, а остаток 1 означает взаимную простоту.

Взаимная простота не равна простоте каждого числа. Числа 8 и 9 составные, но НОД(8, 9) = 1, потому что 8 = 2³, а 9 = 3². Важен не состав каждого числа, а отсутствие у них общих простых множителей.

Из взаимной простоты следует полезное свойство: если НОД(a, b) = 1 и a делит b · c, то a делит c. Простые множители числа a не могут прийти из b, поэтому они должны содержаться в c. Это свойство объясняет и сокращение дробей: если числитель и знаменатель взаимно просты, общего делителя больше 1 нет, значит, дробь несократима.

Признаки и свойства взаимно простых чисел

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

Разбор задач

Задача 1

Определить, являются ли числа 35 и 48 взаимно простыми. Выберем разложение на простые множители, потому что оно сразу показывает общие простые делители.

1. Разложим числа: 35 = 5 · 7, 48 = 2⁴ · 3.
2. Сравним простые множители: в первом разложении есть 5 и 7, а во втором — 2 и 3.
3. Общих множителей нет, поэтому НОД(35, 48) = 1.

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

Задача 2

Проверить взаимную простоту чисел 391 и 299. Числа достаточно велики, поэтому применим алгоритм Евклида и будем отслеживать последний ненулевой остаток.

1. 391 = 299 · 1 + 92.
2. 299 = 92 · 3 + 23.
3. 92 = 23 · 4 + 0.
4. Последний ненулевой остаток равен 23, значит, НОД(391, 299) = 23.

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

Задача 3

Известно, что числа a и b взаимно просты, а a делит произведение b · c. Доказать, что a делит c. Рассмотрим простые множители числа a и воспользуемся отсутствием общих множителей у a и b.

1. Пусть a = p₁^α¹ · p₂^α² · … · pₖ^αᵏ — разложение числа a на простые множители.
2. Так как НОД(a, b) = 1, ни один из простых множителей p₁, p₂, …, pₖ не входит в разложение b.
3. Из условия a | b · c все необходимые степени этих простых множителей должны содержаться в c.
4. Следовательно, произведение p₁^α¹ · p₂^α² · … · pₖ^αᵏ делит c, то есть a | c.

Ответ: доказано свойство взаимно простых чисел: из НОД(a, b) = 1 и a | b · c следует a | c.

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

Иногда взаимно простыми считают только простые числа. Ошибка возникает из-за слова «простые», но оно обозначает отсутствие общих делителей, а не простоту каждого числа. Проверьте НОД: 8 и 9 составные, однако НОД(8, 9) = 1.

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

НОД всех чисел, равный 1, ещё не гарантирует попарную взаимную простоту. Например, НОД(6, 10, 15) = 1, но пара 6 и 10 имеет НОД 2. Для проверки составьте все пары и найдите НОД каждой.

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

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

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

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

Свойства взаимно простых чисел пригодятся в задачах на делимость и остатки. Они также применяются в простейших диофантовых уравнениях, где требуется найти целые или натуральные решения. Особенно полезно правило a | b · c и НОД(a, b) = 1.

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

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