¿Cuál es la probabilidad de que el GCD de $n$ naturales $\le m$ es 1?

Question

¿Cuál es la probabilidad de que el GCD de $n$ naturales $\le m$ es 1?

Por ejemplo, si hay $n=2$ números menores o iguales a $m=2$ Hay cuatro combinaciones - {1,1},{1,2},{2,1},{2,2}. Sólo la última combinación, {2,2}, tiene un GCD mayor que 1. Así que con $n=2, m=2$ la probabilidad es de 3/4.

Answer 1

( Nota : parece que he utilizado $k$ en lugar de $n$ .)

Esta probabilidad viene dada por la función

$$C_k(m):=\frac1{m^k}\sum_{\substack{a_1,\dots,a_k\leq m\\\gcd(a_1,\dots,a_k)=1}}1$$

donde la suma se extiende a todas las tuplas $(a_1,\dots,a_k)$ con $a_i\leq m$ ( $i=1,\dots,n$ ) que son relativamente primos. Se puede demostrar que

$$C_k(m)\sim\frac1{\zeta(k)};$$

es decir, esta probabilidad tiende a $1/\zeta(k)$ como $k\to\infty$ (donde $\zeta(k)$ es el Función zeta de Riemann .) En particular, para $k=2$ la "probabilidad" (más exactamente, la densidad asintótica) de que dos enteros elegidos al azar sean primos relativos es $6/\pi^2$ . La prueba de este resultado sería la siguiente:

$$\begin{align*} C_2(m)&=\frac1{m^2}\sum_{a\leq m}\sum_{\substack{b\leq m\\(a,b)=1}}1 =\frac2{m^2}\left(\sum_{a\leq m}\sum_{\substack{b\leq a\\(a,b)=1}}1\right)-1 =\frac2{m^2}\sum_{a\leq m}\varphi(a)-1, \end{align*}$$

donde $\varphi(a)$ es la función totiente de Euler, que cuenta el número de primos relativos a $a$ que son $\leq a$ . En la segunda igualdad, hemos hecho uso de la simetría: sumando los pares $(a,b)$ de la plaza $a,b\leq m$ tal que $\gcd(a,b)=1$ es lo mismo que sumar los pares dentro del triángulo inferior $a\leq m,b\leq a$ y los pares dentro del triángulo superior $b\leq m,a\leq b$ que satisface $\gcd(a,b)=1$ (menos la intersección, que consiste en un solo punto.) Ambas cantidades resultan ser iguales porque $(a,b)=1$ si $(b,a)=1$ .

Ahora bien, como $\varphi=\mu*N$ tenemos (si escribimos $a=dq$ )

$$\begin{align*} \sum_{a\leq m}\sum_{d|a}\mu(a)\frac ad&=\sum_{d\leq m}\mu(d)\sum_{q\leq m/d}q\\ &=\sum_{d\leq m}\left(\frac{m^2\mu(d)}{2d^2}+O(m/d)\right)\\ &=\frac{m^2}{2}\sum_{d\geq1}\frac{\mu(d)}{d^2}+O\left(\sum_{d>m}\frac{m^2}{d^2}\right)+O(m\log(m)) \end{align*}$$

así que $\sum_{a\leq k}\varphi(a)\sim Am^2/2$ , donde $A=\sum_{d\geq1}\mu(d)/d^2$ . Por lo tanto,

$$\lim_{m\to\infty}C_2(m)=\lim_{m\to\infty}\frac2{m^2}\frac{m^2}{2}A=A.$$

Ahora nos queda encontrar $A$ . Observamos que

$$\sum_{d\geq1}\frac{\mu(d)}{d^2}\sum_{q\geq1}\frac1{q^2} =\sum_{d,q\geq1}\frac{\mu(d)}{(dq)^2},$$

por lo que si escribimos $n=dq$ podemos reescribirlo como

$$\sum_{n\geq1}\frac1{n^2}\sum_{dq=n}\mu(d) =\sum_{n\geq1}\frac1{n^2}\sum_{d|n}\mu(d) =\sum_{n\geq1}\frac1{n^2}I(n)$$

donde $I(n)$ es la identidad bajo la convolución de Dirchlet (es decir, $I(1)=1$ y $I(n)=0$ de lo contrario). Por lo tanto,

$$A\sum_{n\geq1}\frac1{n^2}=1$$

así que $A=1/\zeta(2)=6/\pi^2$ . Un argumento similar (pero más largo) muestra que $C_k$ converge a $1/\zeta(k)$ .