Взаимно простые целые числа

В теории чисел два целых числа $a$ и $b$ являются взаимно простыми , относительно простыми или взаимно простыми, если единственное положительное целое число, которое является делителем обоих из них, равно 1. ^[1] Следовательно, любое простое число , которое делит $a$ , не делит $b$ , и наоборот. Это эквивалентно тому, что их наибольший общий делитель (НОД) равен 1. ^[2] Говорят также, что $a$ является простым по отношению к $b$ или $a$ является взаимно простым с $b$ .

Числа 8 и 9 являются взаимно простыми, несмотря на то, что ни одно из них — рассматриваемое по отдельности — не является простым числом, поскольку их единственным общим делителем является 1. С другой стороны, 6 и 9 не являются взаимно простыми, поскольку они оба делятся на 3. Числитель и знаменатель сокращенной дроби являются взаимно простыми по определению.

Обозначение и тестирование

Когда целые числа $a$ и $b$ взаимно просты, стандартный способ выражения этого факта в математической нотации — указать, что их наибольший общий делитель равен единице, по формуле $gcd(a, b) = 1$ или $(a, b) = 1$ . В своем учебнике 1989 года Concrete Mathematics Рональд Грэм , Дональд Кнут и Орен Паташник предложили альтернативную нотацию , чтобы указать, что $a$ и $b$ являются взаимно простыми, и что термин «простой» следует использовать вместо термина «взаимно простой» (например, $a$ является простым по отношению к $b$ ). ^[3] $a\perp b$

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

Количество целых чисел, взаимно простых с положительным целым числом $n$ , от 1 до $n$ , задается функцией тотиента Эйлера , также известной как фи-функция Эйлера, $φ (n)$ .

Набор целых чисел также можно назвать взаимно простым, если его элементы не имеют общего положительного множителя, кроме 1. Более сильное условие для набора целых чисел — попарная взаимная простота, что означает, что $a$ и $b$ являются взаимно простыми для каждой пары $(a, b)$ различных целых чисел в наборе. Набор ${2, 3, 4}$ является взаимно простым, но он не является попарно взаимно простым, поскольку 2 и 4 не являются взаимно простыми.

Характеристики

Числа 1 и −1 являются единственными целыми числами, которые взаимно просты с каждым целым числом, и они являются единственными целыми числами, которые взаимно просты с 0.

Ряд условий эквивалентен тому, что числа $a$ и $b$ являются взаимно простыми:

Ни одно простое число не делит одновременно $a$ и $b$ .
Существуют целые числа $x, y,$ такие, что $ax + by = 1$ (см. тождество Безу ).
Число $b$ имеет мультипликативное обратное по модулю $a$ , что означает, что существует целое число $y,$ такое что $by \equiv 1 (mod a)$ . На языке теории колец $b$ является единицей в кольце целых чисел $\mathbb {Z} /a\mathbb {Z}$ по модулю $a$ .
Каждая пара соотношений конгруэнтности для неизвестного целого числа $x$ вида $x \equiv k (mod a)$ и $x \equiv m (mod b)$ имеет решение ( китайская теорема об остатках ); фактически решения описываются одним соотношением конгруэнтности по модулю $ab$ .
Наименьшее общее кратное a и $b$ равно их произведению $ab$ , то есть $lcm($ $a$ $,$ $b$ $)$ $=$ $ab$ . ^[4]

Как следствие третьего пункта, если $a$ и $b$ взаимно просты и $br \equiv bs (mod a)$ , то $r \equiv s (mod a)$ . ^[5] То есть, мы можем «делить на $b$ », работая по модулю $a$ . Кроме того, если $b 1, b 2$ оба взаимно просты с $a$ , то их произведение $b 1 b 2$ также является взаимно простым (т.е. по модулю $a$ оно является произведением обратимых элементов, и, следовательно, обратимо); ^[6] это также следует из первого пункта по лемме Евклида , которая гласит, что если простое число $p$ делит произведение $bc$ , то $p$ делит по крайней мере один из множителей $b, c$ .

Как следствие первого пункта, если $a$ и $b$ взаимно просты, то таковыми же являются любые степени $a k$ и $b m$ .

Если $a$ и $b$ взаимно просты и $a$ делит произведение $bc$ , то $a$ делит $c$ . ^[7] Это можно рассматривать как обобщение леммы Евклида.

Рисунок 1. Числа 4 и 9 взаимно просты. Поэтому диагональ решетки 4 × 9 не пересекает никаких других точек решетки.

Два целых числа $a$ и $b$ являются взаимно простыми тогда и только тогда, когда точка с координатами $(a, b)$ в декартовой системе координат будет «видима» через беспрепятственную линию зрения из начала координат $(0, 0) , в том смысле, что на отрезке прямой между началом координат и$ $(a, b)$ нет точки с целыми координатами . (См. рисунок 1.)

В определенном смысле вероятность того, что два случайно выбранных целых числа являются взаимно простыми, равна $6/ π 2$ , что составляет около 61% (см. § Вероятность взаимной простоты ниже).

Два натуральных числа $a$ и $b$ взаимно просты тогда и только тогда, когда числа $2 a - 1$ и $2 b - 1$ взаимно просты. ^[8] В качестве обобщения этого, легко вытекающего из алгоритма Евклида в основании $n > 1$ :

\gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1.

Взаимная простота в множествах

Множество целых чисел также можно назвать взаимно простым или взаимно простым, если наибольший общий делитель всех элементов множества равен 1. Например, целые числа 6, 10, 15 являются взаимно простыми, поскольку 1 — единственное положительное целое число, которое делит их все. $S=\{a_{1},a_{2},\dots ,a_{n}\}$

Если каждая пара в наборе целых чисел является взаимно простой, то набор называется попарно взаимно простой (или попарно относительно простой , взаимно взаимно простой или взаимно относительно простой ). Попарная взаимно простая является более сильным условием, чем попарно взаимно простая; каждое попарно взаимно простое конечное множество также является попарно взаимно простым, но обратное неверно. Например, целые числа 4, 5, 6 являются (попарно) взаимно простыми (потому что единственное положительное целое число, делящее их все , равно 1), но они не являются попарно взаимно простыми (потому что $gcd(4, 6) = 2$ ).

Концепция попарной взаимной простоты важна как гипотеза во многих результатах теории чисел, таких как китайская теорема об остатках .

Бесконечное множество целых чисел может быть попарно взаимно простым. Известными примерами являются множество всех простых чисел, множество элементов в последовательности Сильвестра и множество всех чисел Ферма .

Взаимная простота в идеалах колец

Два идеала $A$ и $B$ в коммутативном кольце $R$ называются взаимно простыми (или комаксимальными ), если Это обобщает тождество Безу : с этим определением два главных идеала ( $a$ ) и ( $b$ ) в кольце целых чисел ⁠ ⁠ являются взаимно простыми тогда и только тогда, когда $a$ и $b$ являются взаимно простыми. Если идеалы $A$ и $B$ кольца $R$ являются взаимно простыми, то , кроме того, если $C$ — третий идеал, такой что $A$ содержит $BC$ , то $A$ содержит $C$ . Китайскую теорему об остатках можно обобщить на любое коммутативное кольцо, используя взаимно простые идеалы. $A+B=R.$ $\mathbb {Z}$ $AB=A\cap B;$

Вероятность взаимной простоты

При наличии двух случайно выбранных целых чисел $a$ и $b$ разумно задать вопрос, насколько вероятно, что $a$ и $b$ являются взаимно простыми. При этом определении удобно использовать характеристику, что $a$ и $b$ являются взаимно простыми тогда и только тогда, когда никакое простое число не делит их оба (см. Основная теорема арифметики ).

Неформально, вероятность того, что любое число делится на простое число (или на любое целое число) $p$ , равна ⁠ ⁠ ${\tfrac {1}{p}};$ например, каждое 7-е целое число делится на 7. Следовательно, вероятность того, что два числа оба делятся на $p,$ равна ⁠ ⁠ ${\tfrac {1}{p^{2}}},$ и вероятность того, что хотя бы одно из них не делится, равна ⁠ ⁠ $1-{\tfrac {1}{p^{2}}}.$ Любой конечный набор событий делимости, связанных с различными простыми числами, является взаимно независимым. Например, в случае двух событий число делится на простые числа $p$ и $q$ тогда и только тогда, когда оно делится на $pq$ ; последнее событие имеет вероятность ⁠ ⁠ ${\tfrac {1}{pq}}.$ Если сделать эвристическое предположение, что такое рассуждение можно распространить на бесконечное множество событий делимости, можно предположить, что вероятность того, что два числа являются взаимно простыми, задается произведением по всем простым числам,

\prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{{\text{prime }}p}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.607927102\approx 61\%.

Здесь $ζ$ относится к дзета-функции Римана , тождество, связывающее произведение простых чисел с $ζ (2)$ , является примером произведения Эйлера , а оценка $ζ (2)$ как $π 2 /6$ является Базельской проблемой , решенной Леонардом Эйлером в 1735 году.

Не существует способа выбрать положительное целое число случайным образом так, чтобы каждое положительное целое число встречалось с равной вероятностью, но утверждения о «случайно выбранных целых числах», такие как приведенные выше, можно формализовать, используя понятие естественной плотности . Для каждого положительного целого числа $N$ пусть $P N$ будет вероятностью того, что два случайно выбранных числа из являются взаимно простыми. Хотя $P$ $N$ никогда не будет равен $6/$ $π$ $2$ в точности, с помощью работы ^[9] можно показать, что в пределе, когда вероятность $P$ $N$ стремится к $6/$ $π$ $2$ . $\{1,2,\ldots ,N\}$ $N\to \infty ,$

В более общем случае вероятность того, что $k$ случайно выбранных целых чисел будут взаимно простыми, равна ⁠ ⁠ ${\tfrac {1}{\zeta (k)}}.$

Генерация всех взаимно простых пар

Дерево с корнем (2, 1). Корень (2, 1) отмечен красным, его три потомка показаны оранжевым, третье поколение — желтым и так далее в радужном порядке.

Все пары положительных взаимно простых чисел $(m, n)$ (при $m > n$ ) можно расположить в двух непересекающихся полных тернарных деревьях , одно дерево начинается с $(2, 1)$ (для пар чет–нечет и нечет–чет), ^[10] а другое дерево начинается с $(3, 1)$ (для пар нечет–нечет). ^[11] Потомки каждой вершины $(m, n)$ генерируются следующим образом:

Филиал 1: $(2m-n,m)$
Филиал 2: $(2m+n,m)$
Филиал 3: $(m+2n,n)$

Эта схема является исчерпывающей и не избыточной, без недействительных членов. Это можно доказать, заметив, что если является взаимно простой парой с то $(a,b)$ $a>b,$

если то является потомком ветви 3; $a>3b,$ $(a,b)$ $(m,n)=(a-2b,b)$
если то является потомком ветви 2; $2b<a<3b,$ $(a,b)$ $(m,n)=(b,a-2b)$
если то является потомком ветви 1. $b<a<2b,$ $(a,b)$ $(m,n)=(b,2b-a)$

Во всех случаях это «меньшая» взаимно простая пара с Этот процесс «вычисления отца» может остановиться только если либо или В этих случаях взаимно простая пара подразумевает, что пара является либо или $(m,n)$ $m>n.$ $a=2b$ $a=3b.$ $(2,1)$ $(3,1).$

Приложения

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

В докомпьютерной криптографии некоторые шифровальные машины Вернама объединяли несколько петель ключевой ленты разной длины. Многие роторные машины объединяют роторы с разным количеством зубцов. Такие комбинации работают лучше всего, когда весь набор длин попарно взаимно прост. ^[12]^[13]^[14]^[15]

Обобщения

Эту концепцию можно распространить и на другие алгебраические структуры , например $\mathbb {Z} ;$ , многочлены, наибольший общий делитель которых равен 1, называются взаимно простыми многочленами .

Смотрите также

Найдите значение слова coprime в Викисловаре, бесплатном словаре.

Примечания

^ Eaton, James S. (1872). Трактат об арифметике. Бостон: Thompson, Bigelow & Brown. стр. 49. Получено 10 января 2022 г. Два числа являются взаимно простыми, когда ни одно целое число, кроме одного, не делит каждое из них.
^ Харди и Райт 2008, стр. 6
^ Грэм, Р. Л.; Кнут, Д. Э.; Паташник, О. (1989), Конкретная математика / Основы компьютерной науки , Addison-Wesley, стр. 115, ISBN 0-201-14236-8
^ Оре 1988, стр. 47
^ Нивен и Цукерман 1966, стр. 22, Теорема 2.3(b)
^ Нивен и Цукерман 1966, стр. 6, Теорема 1.8
^ Нивен и Цукерман 1966, стр.7, Теорема 1.10
^ Розен 1992, стр. 140
^ Эта теорема была доказана Эрнесто Чезаро в 1881 году. Доказательство см. в Hardy & Wright 2008, Theorem 332.
↑ Saunders, Robert & Randall, Trevor (июль 1994), «Повторный взгляд на генеалогическое древо пифагорейских триплетов», Mathematical Gazette , 78 : 190–193, doi : 10.2307/3618576.
^ Митчелл, Дуглас В. (июль 2001 г.), «Альтернативная характеристика всех примитивных пифагорейских троек», Mathematical Gazette , 85 : 273–275, doi :10.2307/3622017.
^ Клаус Поммеренинг. «Криптология: Генераторы ключей с длинными периодами».
^ Дэвид Моури. «Немецкие шифровальные машины Второй мировой войны». 2014. стр. 16; стр. 22.
^ Дирк Райменантс. «Истоки одноразового блокнота».
^ Густав Дж. Симмонс. «Шифр Вернама-Виженера».

Ссылки

Харди, Г. Х.; Райт , Э. М. (2008), Введение в теорию чисел (6-е изд.), Oxford University Press , ISBN 978-0-19-921986-5
Нивен, Иван; Цукерман, Герберт С. (1966), Введение в теорию чисел (2-е изд.), John Wiley & Sons
Оре, Эйстейн (1988) [1948], Теория чисел и ее история , Довер, ISBN 978-0-486-65620-5
Розен, Кеннет Х. (1992), Элементарная теория чисел и ее приложения (3-е изд.), Addison-Wesley, ISBN 978-0-201-57889-8

Дальнейшее чтение

Лорд, Ник (март 2008 г.), «Единообразное построение некоторых бесконечных взаимно простых последовательностей», Mathematical Gazette , 92 : 66–70.