Взаимно простые числа: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
LGB (обсуждение | вклад) оформление |
LGB (обсуждение | вклад) дополнение, источники |
||
Строка 15:
Для определения того, являются ли два числа взаимно простыми, можно использовать [[алгоритм Евклида]].
Понятие взаимной простоты естественным образом обобщается
Свойство взаимной простоты не только играет важную роль в [[Теория чисел|теории чисел]] и [[Коммутативная алгебра|коммутативной алгебре]], но имеет ряд важных практических приложений, в частности, число зубьев на [[Звёздочка (техника)|звёздочках]] и число звеньев цепи в [[цепная передача|цепной передаче]] стремятся делать взаимно простыми, что обеспечивает равномерность износа: каждый зуб звёздочки будет поочерёдно работать со всеми звеньями цепи.
== Попарно взаимно простые числа ==
Если в наборе целых чисел любые два числа взаимно просты, то такие числа называются '''''попарно взаимно простыми''''' (или просто '''''попарно простыми'''''{{sfn |Михелович|1967||с=28|name=MICH28}}). Для двух чисел понятия «взаимно простые» и «попарно
* 8, 15 — не простые, но взаимно простые.
* 6, 8, 9 — взаимно простые (в совокупности) числа, но не попарно
* 8, 15, 49 — попарно
Если числа <math>a_1, \ldots , a_n</math> — попарно
: НОД<math>(a_1, a_2,\dots, b) = </math> НОД<math>(a_1, b)</math> НОД<math>(a_2, b)\dots</math> НОД<math>(a_n, b)</math>
== Свойства ==
Строка 42 ⟶ 43 :
Если числа <math>a</math> и <math>m</math> взаимно просты, то [[сравнение по модулю|сравнение]]:
: <math>ax \equiv b \pmod m .</math>
для любого <math>b</math> имеет единственное решение{{sfn |Михелович|1967||с=64|name=MICH28}} по модулю <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> — это [[дзета-функция Римана]].
Строка 62 ⟶ 63 :
== Литература ==
* {{ВТ-БСЭ1|Взаимно простые числа}}
* {{книга |автор=Михелович Ш. Х. |ref=Михелович |заглавие=Теория чисел |издание=2-е изд |место=М.
|издательство=Высшая школа |год=1967 |страниц=336}}
[[Категория:Теория чисел]]
| |||