Инструменты сайта


§

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


Т

Теорема [Чезаро]. Обозначим $ 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.

numtheory/cesaro.txt · Последние изменения: 2023/11/29 20:55 — au