Введение
Два числа без общих простых делителей
В теории чисел два целых числа a и b называются взаимно простыми, копримами или относительно простыми, если единственным положительным целым числом, являющимся делителем обоих, является 1. Следовательно, любое простое число, делящее a, не делит b, и наоборот. Это эквивалентно тому, что их наибольший общий делитель (НОД) равен 1. Также говорят, что a простое к b или a и b взаимно просты. Числа 8 и 9 являются взаимно простыми, несмотря на то, что ни одно из них по отдельности не является простым числом, поскольку 1 — их единственный общий делитель. С другой стороны, 6 и 9 не являются взаимно простыми, так как оба делятся на 3. Числитель и знаменатель несократимой дроби по определению взаимно просты.
Нотация и испытания
Когда целые числа a и b взаимно просты, стандартный способ выражения этого факта в математической нотации – указать, что их наибольший общий делитель равен 1, с помощью формулы gcd(a, b) = 1 или (a, b) = 1. В своем учебнике «Конкретная математика», опубликованном в 1989 году, Рональд Грэм, Дональд Кнут и Орен Паташник предложили альтернативную нотацию для обозначения того, что a и b взаимно просты, и использовать термин «простые» вместо «взаимно простые» (например, a простое к b). Быстрый способ определения того, являются ли два числа взаимно простыми, предоставляет алгоритм Евклида и его более быстрые варианты, такие как бинарный алгоритм НОД или алгоритм НОД Лемера. Количество целых чисел, взаимно простых с положительным целым числом n, в диапазоне от 1 до n, задается функцией Эйлера, также известной как фи-функция Эйлера, φ(n). Множество целых чисел также можно назвать взаимно простым, если его элементы не имеют общих положительных делителей, кроме 1. Более строгим условием для множества целых чисел является попарная взаимная простота, что означает, что для каждой пары (a, b) различных целых чисел в множестве a и b взаимно просты. Множество {2, 3, 4} является взаимно простым, но не является попарно взаимно простым, поскольку 2 и 4 не являются взаимно простыми.
Копримальность в множествах
Множество целых чисел также может называться взаимно простыми или взаимно простыми по множеству, если наибольший общий делитель всех элементов множества равен 1. Например, целые числа 6, 10, 15 являются взаимно простыми, потому что 1 — единственное положительное целое число, которое делит все из них. Если каждая пара в множестве целых чисел взаимно проста, то множество называется попарно взаимно простым (или попарно взаимно простыми, взаимно простыми попарно или взаимно относительно простыми попарно). Попарная взаимная простота является более сильным условием, чем взаимная простота по множеству; каждое попарно взаимно простое конечное множество также является взаимно простым по множеству, но обратное неверно. Например, целые числа 4, 5, 6 являются (взаимно простыми по множеству) (поскольку единственное положительное целое число, делящее все из них, — 1), но они не являются попарно взаимно простыми (поскольку НОД(4, 6) = 2). Понятие попарной взаимной простоты важно как предпосылка во многих результатах теории чисел, таких как китайская теорема об остатках. Бесконечное множество целых чисел может быть попарно взаимно простым. Примечательные примеры включают множество всех простых чисел, множество элементов в последовательности Сильвестра и множество всех чисел Ферма.
Копримальность в кольцевых идеалах
Два идеала A и B в коммутативном кольце R называются копримами (или комаксимальными), если Это обобщает тождество Безу: с этим определением два главных идеала (a) и (b) в кольце целых чисел \Z являются копримами тогда и только тогда, когда a и b являются копримами. Если идеалы A и B кольца R копримы, то, кроме того, если C – третий идеал, такой что A содержит BC, то A содержит C. Китайская теорема об остатках может быть обобщена на любое коммутативное кольцо, используя копримы идеалы.
Вероятность сопричастия
При наличии двух случайно выбранных целых чисел a и b разумно спросить, какова вероятность того, что a и b взаимно просты. При этом определении удобно использовать характеристику, что a и b взаимно просты тогда и только тогда, когда ни одно простое число не делит их обоих (см. Основную теорему арифметики). Неформально, вероятность того, что любое число делится на простое (или, фактически, на любое целое число) p, равна \tfrac{1}{p}; например, каждое седьмое целое число делится на 7. Следовательно, вероятность того, что два числа делятся на p, равна \tfrac{1}{p^2}, а вероятность того, что хотя бы одно из них не делится на p, равна 1 – \tfrac{1}{p^2}. Любая конечная коллекция событий делимости, связанных с различными простыми числами, является взаимно независимой. Например, в случае двух событий, число делится на простые числа p и q, если и только если оно делится на pq; последнее событие имеет вероятность \tfrac{1}{pq}. Если сделать эвристическое предположение, что такое рассуждение можно распространить на бесконечно много событий делимости, то можно предположить, что вероятность того, что два числа взаимно просты, задается произведением по всем простым числам.
Здесь ζ относится к функции Римана-дзета, тождество, связывающее произведение по простым числам с ζ(2), является примером эйлерова произведения, а вычисление ζ(2) как π^(2)/6 – это Базельская задача, решенная Леонардом Эйлером в 1735 году. Не существует способа выбрать положительное целое число случайным образом так, чтобы каждое положительное целое число имело одинаковую вероятность, но утверждения о «случайно выбранных целых числах», подобные приведенным выше, могут быть формализованы с использованием понятия естественной плотности. Для каждого положительного целого числа N пусть – вероятность того, что два случайно выбранных числа в взаимно просты. Хотя никогда не будет точно равно 6/π^(2), при определенных вычислениях можно показать, что в пределе, когда стремится к бесконечности, вероятность стремится к 6/π^(2). В более общем случае, вероятность того, что k случайно выбранных целых чисел попарно взаимно просты, равна \tfrac{1}{\zeta(k)}.
Приложения
В машиностроении равномерный износ зубьев шестерен достигается путем выбора количества зубьев двух взаимодействующих шестерен так, чтобы они были взаимно простыми. Если требуется передаточное отношение 1:1, между двумя шестернями одинакового размера можно установить шестерню, взаимно простую по отношению к обеим. В докомпьютерной криптографии некоторые машины Вернама использовали несколько петель ключевой ленты различной длины. Многие роторные шифровальные машины комбинируют роторы с разным количеством зубьев. Такие комбинации наиболее эффективны, когда все длины в наборе попарно взаимно просты.
Обобщения
Это понятие можно распространить на другие алгебраические структуры, отличные от \Z; например, полиномы, наибольший общий делитель которых равен 1, называются взаимно простыми полиномами.