Probabilidad de una fracción$a/b$ que no se puede simplificar

Question

Sean ayb números enteros positivos independientes aleatorios que siguen la distribución uniforme. ¿Cuál es la probabilidad de que la fracción:

$\frac{a}{b}$

no se puede simplificar?

Answer 1

La respuesta de pedro llega al corazón de la materia de forma relativamente rápida, pero creo que también sería mejor para demostrar donde la $6/\pi^2$ proviene, aparentemente de la nada a los no iniciados.

Así, debería ser obvio que $a/b$ es en la forma más simple si y sólo si $a,b$ son coprime, es decir, $\gcd(a,b) = 1$. Bien, ¿qué significa eso? Esto significa que $a,b$ no compartan el primer número de factores.

En particular, esto significa $a,b$ no comparten un factor de $2$. Para (uniformemente elegidos al azar) distinto de cero enteros $a,b$ (menos que el de algunos otros número $x$), hay un $1/2$ oportunidad (en el límite de $x \to \infty$) cada uno tiene un factor de $2$. Por lo tanto,

$$P(\text{a,b do not have a mutual factor of 2}) = 1 - \left(\frac 1 2 \right)^2$$

Del mismo modo, esto significa que ellos no comparten un factor de $3$. Hay un $1/3$ probabilidad de cada uno de ellos tendrá un factor de tres, y por lo tanto,

$$P(\text{a,b do not have a mutual factor of 3}) = 1 - \left(\frac 1 3 \right)^2$$

Esto claramente se generaliza. Considere la posibilidad de un primer número $p$. Hay un $1/p$ de probabilidad de que $a,b$ cada uno tiene, y a su vez

$$P(\text{a,b do not have a mutual factor of p}) = 1 - \left(\frac 1 p \right)^2$$

Para $a,b$ a ser coprime esto debe ser cierto de todos los números primos $p$. Los eventos son independientes, y nosotros, en consecuencia, pueden multiplicar las respectivas probabilidades para cada uno de los prime $p$, la obtención de

$$P(\text{a,b are coprime}) = \prod_{\text{p prime}} 1 - \left(\frac 1 p \right)^2 = \prod_{\text{p prime}} 1 - \frac 1 {p^2}$$

Este ahora los lazos en algo que se conoce como la de Riemann zeta función. Hay dos fórmulas típicamente asociados con ella: una suma y un producto de fórmula. A menudo nos centramos en la suma de fórmula, pero se puede derivar la segunda; una prueba de dicha derivación se puede encontrar aquí. En cualquier caso, nos centramos en el primer producto de la siguiente fórmula:

$$\zeta(s) = \prod_{\text{p prime}} \frac{1}{1-p^{-s}}$$

Teniendo en cuenta que esta es un producto, podemos hacer una manipulación:

$$\frac{1}{\zeta(s)} = \prod_{\text{p prime}} 1-\frac 1 {p^{s}}$$

Esto se ve precisamente como la fórmula para nuestra probabilidad de $a,b$ siendo coprime pero con $s$ en lugar de $2$. De hecho, dejando $s=2$,

$$P(\text{a,b are coprime}) = \prod_{\text{p prime}} 1 - \frac{1}{p^2} = \frac{1}{\zeta(2)}$$

$\zeta(2)$ es un valor conocido que el de Euler, calculado en $\pi^2/6$; la búsqueda de este valor se refiere a menudo como el problema de Basilea. En consecuencia,

$$P(\text{a,b are coprime}) = \frac{1}{\pi^2/6} = \frac{6}{\pi^2}$$

La idea también se generaliza aún más. Dicen que usted tiene algún grupo de $n$ enteros ($n$ un entero positivo). Entonces la probabilidad de que todos los $n$ son coprime está dada por

$$P(\text{all n numbers are coprime}) = \frac{1}{\zeta(n)}$$

Answer 2

Esta pregunta es equivalente a preguntar por la probabilidad de que $a$ e $b$ son coprime. Si $a$ e $b$ son aleatorios enteros por debajo de $x$, entonces la probabilidad de a$P(x)$ que $a$ e $b$ son coprime , satisface $$\lim_{x\rightarrow\infty} P(x)=\frac{6}{\pi^2}\approx0.6079$$