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

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

Числитель и знаменатель сокращенной дроби взаимно просты. Числа 14 и 25 взаимно просты, так как 1 - их единственный общий делитель. С другой стороны, 14 и 21 не взаимно просты, потому что они оба делятся на 7.

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

Стандартные обозначения для относительно простых целых чисел $a$ и $b$ : $gcd (a, b) = 1$ и $(a, b) = 1$ . В статье 1989 года Грэм , Кнут и Паташник предложили, чтобы обозначение ${\ Displaystyle а \ перп б}$ использоваться для обозначения того, что $a$ и $b$ взаимно просты и что термин «простой» используется вместо взаимно простого (как в случае $a$ является простым с $b$ ). ^[3]

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

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

Множество целых чисел можно также назвать взаимно просты , если ее элементы не разделяют никакого общего положительного множителя 1. сильное условие на множестве целых чисел попарно взаимно просты , что означает , что и $Ь$ взаимно просты для каждой пары $($ $,$ $б$ $)$ различных целые числа в наборе. Множество ${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)$ . В кольцевом теоретико-языке, $б$ представляет собой блок в кольце $Z / Z$ из целых чисел по модулю .
Каждая пара соотношений сравнения для неизвестного целого числа $x$ вида $x \equiv k (mod a)$ и $x \equiv m (mod b)$ имеет решение ( китайская теорема об остатках ); фактически решения описываются одним соотношением сравнения по модулю $ab$ .
Наименьшее общее кратное из и $б$ равна их произведению $аб$ , т.е. $LCM ($ $,$ $б$ $) =$ $AB$ . ^[4]

Как следствие третьего пункта, если a и b взаимно просты и br ≡ bs ( mod a ), то r ≡ s (mod a ). ^[5] То есть мы можем «разделить на b », работая по модулю a . Более того, если b ₁ и b ₂ оба взаимно просты с a , то их произведение b ₁b _{2 также} является произведением b ₁b ₂ (т. Е. По модулю 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 / π ² (см. Pi ), что составляет около 61%. См. ниже.

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

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

Совместимость в наборах

Множество целых чисел S = { в ₁ , ₂ , .... _п } также можно назвать взаимно простыми или setwise взаимно просты , если наибольший общий делитель всех элементов набора равен 1. Так , например, целые числа 6, 10, 15 взаимно просты, потому что 1 - единственное положительное целое число, которое их все делит.

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

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

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

Сочетание в кольцевых идеалах

Два идеала A и B в коммутативном кольце R называются взаимно простым (или comaximal ) , если + B = R . Это обобщает тождество Безу : согласно этому определению два главных идеала ( a ) и ( b ) в кольце целых чисел Z взаимно просты тогда и только тогда, когда a и b взаимно просты. Если идеалы A и B из R взаимно просты, то АВ = ∩ B ; Кроме того, если С является третьим идеал, что содержит BC , то содержит С . Китайская теорема об остатках может быть обобщена на любое коммутативное кольцо, используя копервичную идеалы.

Вероятность копримальности

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

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

{\ displaystyle \ 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}}} \ приблизительно 0.607927102 \ приблизительно 61 \%.}

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

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

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

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

Порядок генерации взаимно простых пар этим алгоритмом. Первый узел (2,1) отмечен красным, три его дочерних узла показаны оранжевым, третье поколение - желтым, и так далее в радужном порядке.

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

Филиал 1: ${\ displaystyle (2m-n, m)}$
Филиал 2: ${\ displaystyle (2m + n, m)}$
Филиал 3: ${\ Displaystyle (м + 2n, п)}$

Эта схема является исчерпывающей и неизбыточной, без недопустимых членов.

Приложения

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

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

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

Суперчастный номер

Заметки

^ Итон, Джеймс С. Трактат по арифметике. 1872. Можно загрузить с: https://archive.org/details/atreatiseonarit05eatogoog.
^ Харди и Райт 2008 , стр. 6
^ Грэм, RL; Knuth, DE; Паташник, О. (1989), Concrete Mathematics / A Foundation for Computer Science , Addison-Wesley, p. 115, ISBN 0-201-14236-8
Перейти ↑ Ore 1988 , p. 47
Перейти ↑ Niven & Zuckerman 1966 , p. 22, теорема 2.3 (б)
Перейти ↑ Niven & Zuckerman 1966 , p. 6, теорема 1.8
^ Нивен и Цукерман 1966 , стр.7, теорема 1.10
Перейти ↑ Rosen 1992 , p. 140
^ Эта теорема была доказана Эрнесто Чезаро в 1881 году. Доказательство см. В Hardy & Wright 2008 , теорема 332.
^ Сондерс, Роберт и Рэндалл, Тревор (июль 1994 г.), « Возвращение к генеалогическому древу пифагорейских троек», Mathematical Gazette , 78 : 190–193, doi : 10.2307 / 3618576.
^ Митчелл, Douglas W. (июль 2001), "Альтернативная характеристика всех примитивных троек Пифагора", Математический вестник , 85 : 273-275, DOI : 10,2307 / 3622017.
↑ Клаус Поммеренинг. «Криптология: генераторы ключей с длительными периодами» .
^ Дэвид Моури. «Немецкие шифровальные машины Второй мировой войны» . 2014. с. 16; п. 22.
^ Кортик Rijmenants. «Истоки одноразового блокнота» .
^ Густав Дж. Симмонс. "Шифр Вернама-Виженера" .

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

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

[1] Итон, Джеймс С. Трактат по арифметике. 1872. Можно загрузить с: https://archive.org/details/atreatiseonarit05eatogoog.

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

[3] Грэм, RL; Knuth, DE; Паташник, О. (1989), Concrete Mathematics / A Foundation for Computer Science , Addison-Wesley, p. 115, ISBN 0-201-14236-8

[4] Перейти ↑ Ore 1988 , p. 47

[5] Перейти ↑ Niven & Zuckerman 1966 , p. 22, теорема 2.3 (б)

[6] Перейти ↑ Niven & Zuckerman 1966 , p. 6, теорема 1.8

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

[8] Перейти ↑ Rosen 1992 , p. 140

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

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

[11] Митчелл, Douglas W. (июль 2001), "Альтернативная характеристика всех примитивных троек Пифагора", Математический вестник , 85 : 273-275, DOI : 10,2307 / 3622017.

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

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

[14] Кортик Rijmenants. «Истоки одноразового блокнота» .

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

[1]