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

В теории чисел два целых числа $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$ и $b$ являются относительно простыми и что термин «простые» следует использовать вместо взаимно простых (так как $a$ является простым с $b$ ). . ^[3] $а\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$ — это единица кольца целых чисел по модулю $a$ . $\mathbb {Z} /a\mathbb {Z}$
Каждая пара отношений сравнения для неизвестного целого числа $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$ взаимно просты, то взаимно простыми являются и любые $степени$ $ak$ и $bm$ .

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

if then является дочерним элементом ветви 3; $a>3b,$ $(a,b)$ $(m,n)=(a-2b,b)$
if then является дочерним элементом ветви 2; $2b<a<3b,$ $(a,b)$ $(m,n)=(b,a-2b)$
if then является дочерним элементом ветви 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]

Обобщения

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

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

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

Примечания

^ Итон, Джеймс С. (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 г.), «Единая конструкция некоторых бесконечных взаимно простых последовательностей», Mathematical Gazette , 92 : 66–70..