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

поменьше дидактики, попроще, взаимная простота естественным образом вводится не только в коммутативных кольцах, но и любых евклидовых (есть НОД)
[отпатрулированная версия][отпатрулированная версия]
м (откат правок 46.250.19.247 (обс.) к версии 146.120.58.227)
Метка: откат
(поменьше дидактики, попроще, взаимная простота естественным образом вводится не только в коммутативных кольцах, но и любых евклидовых (есть НОД))
[[Файл:coprime-lattice.svg|мини|В «лесу», составленном на координатной плоскости из точек с целочисленными координатами, из начала координат «видны» только «деревья» со взаимно простыми координатами.]]
[[Файл:coprime-lattice.svg|thumb|right|300px|Числа 4 и 9 взаимно простые, следовательно, диагональ решётки размером 4 на 9 не пересекает других точек решётки]]
'''Взаимно простые числа''' — пара [[Целое число|целых чисел]], [[наибольший общий делитель]] которых равен [[1]].
[[Целое число|Целые числа]] называются '''взаимно простыми''', если они не имеют никаких общих [[делитель|делителей]], кроме ±1.
 
Например, взаимно просты числа 14 и 25, так как у них нет общих делителей; но числа 15 и 25 не взаимно просты, так как у них имеется общий делитель 5. Для указания взаимной простоты чисел <math>m</math> и <math>n</math> иногда используется обозначение <math>m \perp n</math> (аналогия с [[перпендикуляр]]ными прямыми, не имеющими общих направлений — взаимно простые числа не имеют общих сомножителей<ref name="Concrete">{{книга
Примеры:
* 14 и 25 взаимно просты, так как у них нет общих делителей;
* 15 и 25 не взаимно просты, так как у них имеется общий делитель 5;
 
Наглядное представление: если на плоскости построить «лес», установив на точки с целыми координатами «деревья» нулевой толщины, то из начала координат видны только деревья, координаты которых взаимно просты, см. рисунок справа как пример видимости «дерева» с координатами (9, 4).
 
== Обозначения ==
Для указания взаимной простоты чисел <math>m</math> и <math>n</math> используется обозначение<ref name="Concrete">{{книга
|автор = Р. Грэхем, Д. Кнут, О. Паташник
|заглавие = Конкретная математика
|страниц = 703
|isbn = 5-03-001793-3
}}</ref>:).
: <math>m \perp n.</math>
 
* Если в наборе чисел '''любые''' два числа взаимно просты, то такие числа называются '''''попарно взаимно простыми'''''. ДляПонятие двухвзаимной чиселпростоты понятияестественным «взаимнообразом простые»обобщается идо «попарнолюбых взаимно[[Евклидово простые»кольцо|евклидовых совпадаютколец]].
{{цитата|Подобно тому, как [[перпендикуляр]]ные прямые не имеют общего направления, так и перпендикулярные числа не имеют общих сомножителей.<ref name="Concrete"/>}}
 
ОбычноСвойство взаимной простоты не только играет важную роль в [[Теория чисел|теории чисел]] и [[Коммутативная алгебра|коммутативной алгебре]], но имеет ряд важных практических приложений, в частности, число зубьев на [[Звёздочка (техника)|звёздочках]] и число звеньев цепи в [[цепная передача|цепной передаче]] стремятся делать взаимно простыми, что обеспечивает равномерность износа: каждый зуб звёздочки будет поочерёдно работать со всеми звеньями цепи.
Однако не все математики признают и используют это обозначение. Чаще всего используется словесная формулировка или эквивалентная запись <math>\gcd(a, b)=1</math>, что означает: «[[наибольший общий делитель]] чисел ''a'' и ''b'' равен 1».
 
== Связанные определения ==
* Если в наборе чисел '''любые''' два числа взаимно просты, то такие числа называются '''попарно взаимно простыми'''. Для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают.
 
=== Примеры ===
* 8, 15 — не простые, но взаимно простые.
* 6, 8, 9 — взаимно простые (в совокупности) числа, но не попарно взаимно простые.
* 8, 15, 49 — попарно взаимно простые.
 
== Свойства ==
* Числа <math>a</math> и <math>b</math> взаимно просты [[тогда и только тогда]], когда выполняетсясуществуют одноцелые из<math>x</math> эквивалентныхи <math>y</math> такие, что <math>ax + by = 1</math> ([[соотношение Безу]]). Если [[натуральные числа]] <math>a</math> и <math>b</math> взаимно просты, то числа <math>2^a-1</math> и <math>2^b-1</math> также взаимно просты, притом верно и условий:обратное.
** [[наибольший общий делитель]] <math>a</math> и <math>b</math> равен [[1 (число)|единице]];
** существуют целые <math>x</math> и <math>y</math> такие, что <math>ax + by = 1</math> ([[соотношение Безу]]).
* Любые два (различные) [[простые числа]] взаимно просты.
* Если <math>a</math> — делитель произведения <math>bc</math>, и <math>a</math> взаимно просто с <math>b</math>, то <math>a</math> — делитель <math>c</math>.
* Если числа <math>a_1, \ldots , a_n</math> — попарно взаимно простые числа, то '''[[Наименьшее общее кратное|НОК]]'''<math>(a_1, \ldots , a_n) = |a_1 \cdot \ldots \cdot a_n|</math>. Например, НОК <math>(9, 11) = 9 \cdot 11 = 99</math>.
* Вероятность того, что любые <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> — это [[дзета-функция Римана]].
* Дробь является [[Несократимая дробь|несократимой]] тогда и только тогда, когда числитель и знаменатель взаимно просты.
 
*Дробь является [[Несократимая дробь|несократимой]] тогда и только тогда, когда числитель и знаменатель взаимно просты. Если <math>a</math> — делитель произведения <math>bc</math>, и <math>a</math> — взаимно просто с <math>b</math>, то <math>a</math> — делитель <math>c</math>.
== Обобщения ==
Понятия простого числа и взаимно простых чисел естественно обобщаются на произвольные [[коммутативность|коммутативные]] [[кольцо (алгебра)|кольца]], например, на кольцо [[многочлен]]ов или [[гауссовы целые числа]]. Обобщением понятия простого числа является «[[неприводимый элемент]]». Два элемента кольца называются взаимно простыми, если они не имеют никаких общих [[делитель|делителей]], кроме [[Делитель единицы|делителей единицы]]. При этом аналог [[Основная теорема арифметики|основной теоремы арифметики]] выполняется не во всех, а только в [[факториальное кольцо|факториальных кольцах]].
 
* Если числа <math>a_1, \ldots , a_n</math> — попарно взаимно простые числа, то '''их [[Наименьшеенаименьшее общее кратное|НОК]]'''<math>(a_1, \ldotsравно ,абсолютному a_n)значению =их произведения: <math>|a_1 \cdot \ldots \cdot a_n|</math>. Например, НОК <math>(9, 11) = 9 \cdot 11 = 99</math>.
== Применение ==
Обычно число зубьев на [[Звёздочка (техника)|звёздочках]] и число звеньев цепи в [[цепная передача|цепной передаче]] стремятся делать взаимно простыми, что обеспечивает равномерность износа: каждый зуб звёздочки будет поочерёдно работать со всеми звеньями цепи.
 
* Вероятность того, что любые <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> — это [[дзета-функция Римана]].
== См. также ==
* [[Простое число]]
* [[Наибольший общий делитель]]
* [[Наименьшее общее кратное]]
* [[Неприводимый элемент]]
* [[Распределённые вычисления]]
 
== Примечания ==
{{примечания}}
 
== Ссылки ==
 
* [http://habrahabr.ru/sandbox/68846/ Фракталы во взаимно простых числах]
 
== Литература ==