Есть два числа, целых, желательно (но не обязательно) натуральных, то есть, таких, которые больше 0. Моя задача в том чтобы определить, какая вероятность того, что два случайно взятых числа будут взаимно простые. Что такое взаимно простые? Это означает что ни первое, ни второе число не делятся нацело на какое-то число, отличное от единицы. Это означает то, что их НОД (наибольший общий делитель) равен 1.
Например: числа 8 и 15 – взаимнопростые, потому что ни 8, ни 15 не имеют общих делителей, кроме 1. То есть их НОД(8,15)=1.
§ Вероятность
Допустим есть число, от 1 до бесконечности, то есть, грубо говоря, любое. Какая вероятность того что это число делиться на 2? Ясное дело что каждое второе (2) число делится на два, иначе, вероятность того что мы взяли и раздели любое случайно взятое число, равно 50% или P=0.5, иными словами. Вероятность же того, что число не делится на 2, тоже составляет 50%.
А если на 3? То вероятность уже уменьшается и равна , и вероятность того что число не делится на 3, равна .
Но а что если взять два числа и проверить, с какой вероятностью они оба поделятся на 2 или 3? Для этого надо вероятности умножить. Обозначу только через p некоторое значение, которое будет равно одному и простых чисел (2,3,5,7 и так далее). Почему именно простых? Потому что если бы мы брали составное число, то получили бы все равно разделение на два простых, потому что они составные! Так что берем только простые в p.
Вероятность того что любое число n делится на p, равна . Например p=5, вероятность деления на 5 будет 20%, потому что 100%/5=20%. И вот из этой вероятности надо еще умножить на точно такую же, но деления второго числа. То есть, да, ладно бы еще выпало один из пяти раз, так надо чтобы и второе число выпало раз из раз тоже! То есть 20% еще умножаем на 20% и получается вообще 4% шанса, что выпадут именно 2 числа, которые оба делятся на 5. Это как если подбрасывать кубики с 5-ю гранями и в 4% случаев эти обе грани выпадут на число 5.
Собственно, вероятность деления любых двух натуральных чисел на p будет такой:
Теперь вот важное дело. Вероятность того что хотя бы одно число не делится на p, равна . Это и является ключевым моментом для того чтобы определить, что всё множество чисел вообще не будет делиться ни на одно из p одновременно.
§ Индукция
Теперь проверим по шагам.
Какова вероятность того что два числа не делятся на 2? Эта вероятность 75%, так как одно из чисел делится на 2 с вероятностью 50%, а второе число тоже с 50%, что дает в сумме 25% – что два числа одновременно поделятся на одно и то же число 2, а то что два числа не поделятся на одно и то же число 2, будет равно 100%-25%=75%.
Что значит что два числа одновременно не делятся на число p? Это значит что у них нет общего делителя p!
Однако, одной двойкой сыт не будешь, переходим к p=3. Мы знаем что вероятность того что одновременно числа, которые делятся одновременно на 3, будет равна , и вероятность же того, что хоть одно число не поделится будет равна = 88%.
И так надо взять абсолютно все простые числа и для каждого из них вычислить такую вероятность. Подсчитав итоговую вероятность этих множителей, получаем тот самый процент взаимнопростых чисел.
Почему так? Потому что, пересчитывая вероятность одного, второго, третьего, десятого простого числа, мы даем общую вероятность НОД(a,b)=1 для любого отдельно взятого случайного числа.
В общем и целом эта вот вся выше формула записывается как:
и это приблизительно равно 0.607927 или около 61% случаев.
Число пи здесь не является случайным и появляется по разным причинам. Дело в том что это площадь окружности, и геометрически это можно доказать. Но я пока не буду.
Проще говоря, если бы мы стояли в лесу из точек, стоящих по целым координатами, то лес бы просвечивал примерно на 39% во все стороны.