УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу НАЧАЛА ТЕОРИИ ЦЕЛЫХ ЧИСЕЛ.


Т

Теорема [Чезаро]. Обозначим P_N вероятность того, что два числа случайно выбранные из множества \{1,2,\dots, N \} взаимно просты. Тогда

\lim_{N\to \infty} P_N = \frac{6}{\pi^2} \approx 0.607927 \ .

Доказательство правдоподобия результата. Если дополнительно предположить, что указанный предел существует и равен P_{}, то тогда можно установить вероятность события, что произвольные два натуральных числа A_{} и B_{} имеют \operatorname{HOD} (A,B) равным произвольному числу d \in \mathbb N. Действительно, \operatorname{HOD} (A,B)=d тогда и только тогда, когда одновременно выполняются три события: A_{} делится на d_{}, B_{} делится на d_{} и \operatorname{HOD} (A/d,B/d)=1. Эти три события независимы, вероятность их совместного осуществления равна произведению их вероятностей (см. пункт УСЛОВНЫЕ ВЕРОЯТНОСТИ), т.е.

\frac{1}{d} \cdot \frac{1}{d} \cdot P = \frac{P}{d^2} \ .

Просуммировав эти вероятности по всем натуральным d_{}, мы должны получить 1_{} (абсолютно достоверное событие: два числа хоть какой-то \operatorname{HOD} имеют):

1=\sum_{d=1}^{\infty} \frac{P}{d^2}=P\left( 1+ \frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\dots \right) \ .

Из мат.анализа известна величина суммы полученного бесконечного ряда, она равна \pi^2/6.

Источники

Кнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. М. Мир. 1977, С.366-367.


2019/08/16 09:12 редактировал au