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

В теории чисел два целых числа $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 года Рональд Грэм , Дональд Кнут и Орен Паташник предложили альтернативное обозначение. $a\perp b$ чтобы указать, что $a$ и $b$ относительно просты и что термин «простой» используется вместо взаимно простого (так как $a$ является простым с $b$ ). ^[3]

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

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

Набор a целых чисел также можно назвать взаимно простым, если его элементы не имеют общего положительного фактора, кроме 1. Более сильное условие для набора целых чисел является попарно взаимно простым, что означает, что $и$ 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. к$ и $б м$ .

Если $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 а - 1$ и $2 б - 1$ взаимно простые. ^[8] В качестве обобщения этого легко следует из алгоритма Евклида в базе $n > 1$ :

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

Копримальность в множествах

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

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

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

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

Копримальности в кольцевых идеалах

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

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

Учитывая два случайно выбранных целых числа $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$ будет вероятностью того, что два случайно выбранных числа в $\{1,2,\ldots ,N\}$ взаимнопросты. Хотя $P N$ никогда не будет равен $6/ π 2$ именно, с работой ^[9] можно показать это в пределе как $N\to \infty ,$ вероятность $P N$ приближается к $6/ π 2$ .

В более общем смысле, вероятность того, что $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,$ затем

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

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

Приложения

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

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

Обобщения

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

См. также

Примечания

^ Итон, Джеймс С. (1872). Трактат по арифметике . Бостон: Томпсон, Бигелоу и Браун. п. 49 . Проверено 10 января 2022 г. Два числа являются взаимно не целое число, кроме одного . простыми, если каждое из них делится
^ Харди и Райт 2008 , с. 6
^ Грэм, РЛ; Кнут, Делавэр; Паташник, О. (1989), Конкретная математика / Фонд компьютерных наук , Аддисон-Уэсли, с. 115, ISBN 0-201-14236-8
^ Руда 1988 , с. 47
^ Нивен и Цукерман 1966 , с. 22, теорема 2.3(б)
^ Нивен и Цукерман 1966 , с. 6, теорема 1.8
^ Нивен и Цукерман, 1966 , стр.7, теорема 1.10.
^ Розен 1992 , с. 140
^ Эта теорема была доказана Эрнесто Чезаро в 1881 году. Доказательство см. в Hardy & Wright 2008 , теорема 332.
^ Сондерс, Роберт и Рэндалл, Тревор (июль 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-е изд.), Аддисон-Уэсли, ISBN 978-0-201-57889-8

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

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

[1] Итон, Джеймс С. (1872). Трактат по арифметике . Бостон: Томпсон, Бигелоу и Браун. п. 49 . Проверено 10 января 2022 г. Два числа являются взаимно не целое число, кроме одного . простыми, если каждое из них делится

[2] Харди и Райт 2008 , с. 6

[3] Грэм, РЛ; Кнут, Делавэр; Паташник, О. (1989), Конкретная математика / Фонд компьютерных наук , Аддисон-Уэсли, с. 115, ISBN 0-201-14236-8

[4] Руда 1988 , с. 47

[5] Нивен и Цукерман 1966 , с. 22, теорема 2.3(б)

[6] Нивен и Цукерман 1966 , с. 6, теорема 1.8

[7] Нивен и Цукерман, 1966 , стр.7, теорема 1.10.

[8] Розен 1992 , с. 140

[9] Эта теорема была доказана Эрнесто Чезаро в 1881 году. Доказательство см. в Hardy & Wright 2008 , теорема 332.

[10] Сондерс, Роберт и Рэндалл, Тревор (июль 1994 г.), «Возвращение к генеалогическому древу пифагорейских троек», Mathematical Gazette , 78 : 190–193, doi : 10.2307/3618576 .

[11] Митчелл, Дуглас В. (июль 2001 г.), «Альтернативная характеристика всех примитивных пифагорейских троек», Mathematical Gazette , 85 : 273–275, doi : 10.2307/3622017 .

[12] Клаус Поммеренинг. «Криптология: генераторы ключей с длинными периодами» .

[13] Дэвид Моури. «Немецкие шифровальные машины Второй мировой войны» .2014.п. 16; п. 22.

[14] Дирк Рейменанц. «Истоки одноразового блокнота» .

[15] Густав Дж. Симмонс. «Шифр Вернама-Виженера» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]