Взаимно простые числа: различия между версиями

дополнение
[отпатрулированная версия][отпатрулированная версия]
(дополнение)
[[Файл:coprime-lattice.svg|мини|В «лесу», составленном на координатной плоскости из точек с целочисленными координатами, из начала координат «видны» только «деревья» со взаимно простыми координатами.]]
'''Взаимно простые числа''' — [[Целое число|целые числа]], не имеющие никаких общих делителей, кроме ±1. Равносильное определение: целые числа '''взаимно просты''', если их [[наибольший общий делитель]] (НОД) равен [[1 (число)|1]]<ref name=ME>{{книга |часть=Взаимно простые числа. |заглавие=Математическая энциклопедия (в 5 томах) |место=М. |том=1 |год=1977 |издательство=[[Большая Российская энциклопедия (издательство)|Советская Энциклопедия]] |страницы=690}}</ref>.
 
Например, взаимно просты числа 14 и 25, так как у них нет общих делителей; но числа 15 и 25 не взаимно просты, так как у них имеется общий делитель 5. Для указания взаимной простоты чисел <math>m</math> и <math>n</math> иногда используется обозначение <math>m \perp n</math> (аналогия с [[перпендикуляр]]ными прямыми, не имеющими общих направлений — взаимно простые числа не имеют общих сомножителей<ref name="Concrete">{{книга
 
== Связанные определения ==
Если в наборе целых чисел любые два числа взаимно просты, то такие числа называются '''''попарно взаимно простыми'''''. Для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают. Попарно взаимно простые числа будут и взаимно простыми в совокупности, но обратное неверно. Примеры:
 
Свойство попарной взаимной простоты более сильно, чем ранее определённое свойство взаимной простыми (в совокупности) — попарно взаимно простые числа будут и взаимно простыми, но обратное неверно. Примеры:
* 8, 15 — не простые, но взаимно простые.
* 6, 8, 9 — взаимно простые (в совокупности) числа, но не попарно взаимно простые.
* 8, 15, 49 — попарно взаимно простые и взаимно простые (в совокупности).
 
Если числа <math>a_1, \ldots , a_n</math> — попарно взаимно простые числа, то их [[наименьшее общее кратное]] равно абсолютному значению их произведения: <math>|a_1 \cdot \ldots \cdot a_n|</math>.
 
Для определения того, являются ли два числа взаимно простыми, можно использовать [[алгоритм Евклида]].
 
Количество чисел, взаимно простых с натуральным числом n, задаётся [[Функция Эйлера|функцией Эйлера]] φ(n).
 
== Свойства ==
Все упомянутые в этом разделе числа подразумеваются целыми, если не оговорено иное.
 
Числа <math>a</math> и <math>b</math> взаимно просты [[тогда и только тогда]], когда существуют целые <math>x</math> и <math>y</math> такие, что <math>ax + by = 1</math> ([[соотношение Безу]])<ref name=ME/>. Если [[натуральные числа]] <math>a</math> и <math>b</math> взаимно просты, то числа <math>2^a-1</math> и <math>2^b-1</math> также взаимно просты, притом верно и обратное.
 
(''[[Лемма Евклида]]'') Если <math>a</math> — делитель произведения <math>bc</math>, и <math>a</math> взаимно просто с <math>b</math>, то <math>a</math> — делитель <math>c</math>.
Дробь является [[Несократимая дробь|несократимой]] тогда и только тогда, когда числитель и знаменатель взаимно просты.
 
([[Лемма Евклида]]) Если <math>ad=</math> — делитель произведения НОД<math>bc(a,b)</math>, ито числа <math>a\frac ad</math> — взаимно просто си <math>b</math>,\frac то <math>abd</math> — делительвзаимно <math>c</math>просты.
 
Дробь является [[Несократимая дробь|несократимой]] тогда и только тогда, когда числитель и знаменатель взаимно просты.
 
Если числа <math>a_1,a</math> \ldots ,и a_n<math>m</math> — попарно взаимно простые числапросты, то их [[наименьшеесравнение общеепо кратноемодулю|сравнение]] равно абсолютному значению их произведения: <math>|a_1 \cdot \ldots \cdot a_n|</math>.
: <math>ax \equiv b \pmod m .</math>
для любого <math>b</math> имеет единственное решение по модулю <math>m.</math> В частности, решение сравнение для <math>b=1</math> даёт [[обратный элемент]] для <math>a</math> в [[Кольцо вычетов по модулю m|кольце вычетов по модулю m]].
 
Вероятность того, что любые <math>k</math> случайным образом выбранных положительных целых чисел будут взаимно просты, равна <math>\dfrac{1} {\zeta(k)}</math>, в том смысле, что при <math>N\to\infty</math> вероятность того, что <math>k</math> положительных целых чисел, меньших, чем <math>{\textstyle{N}}</math> (и выбранных случайным образом) будут взаимно простыми, стремится к <math>\dfrac{1} {\zeta(k)}</math>. Здесь <math>\zeta(k)</math> — это [[дзета-функция Римана]].