Dado $2$ elegido al azar de números enteros $x,y$ lo $P(k=gcd(x,y))$?

Question

Dado $2$ elegido al azar de números enteros $x,y$ ¿cuál es la probabilidad de que un entero $k$ es el máximo común divisor de a$x$$y$?

Yo sé que la probabilidad de $x,y$ coprime es $\frac{1}{\zeta(2)} = \frac{6}{\pi^2}$ esto podría ser un punto de partida. Creo que uno podría tratar de analizar $P(x/k $ $ y/k$ coprime $| k$ divide $x$ $y)$ Pero, a continuación, la distribución de $x$ $y$ es no uniforme. Tal vez hay alguna mano aquí?

Answer 1

Lo que vamos a ser la informática no es técnicamente una probabilidad. La mayoría de los que uno puede decir es que es un límite de probabilidades.

Deje $k$ ser un fijo entero positivo. Para cualquier entero positivo $N$, vamos a $f_k(N)$ el número de pares ordenados $(x,y)$ tal que $1 \le x \le N$, $1 \le y \le N$, y $\gcd(x,y)=k$. (Con la ayuda de un gran resultado y que es sólo la cita) muestran que $$\lim_{N\to\infty} \frac{f_k(N)}{N^2}=\frac{6}{k^2\pi^2}$$

La prueba es fácil, pero por el bien de la integridad nos hacemos todos los detalles. Deje $r(N)$ el resto al $N$ se divide por $k$. A continuación, $N=kM(N)+r(N)$ para algunos cociente $M(N)$. Para simplificar, podemos escribir la $r$$r(N)$, e $M$$M(N)$, sin olvidar su dependencia de $N$.

Tenga en cuenta que $f_k(N)=f_k(kM)$. Esto es debido a que si en el par ordenado $(x,y)$, uno o ambos de $x$ $y$ está en el intervalo de $[kM+1, N]$, luego de que $x$ (o $y$) no es divisible por $k$.

Tenga en cuenta también que si cada uno de $x$, $y$ es en el intervalo de $[1,kM]$, $\gcd(x,y)=k$ si y sólo si $x=ku$, $y=kv$, donde $\gcd(u,v)=1$.
De ello se sigue que $$f_k(N)=f_k(kM)=f_1(M)$$ En menos de fantasía idioma, el número de pares ordenados contado por $f_k(N)$ es el mismo que el número de pares ordenados $(u,v)$ tal que $1 \le u\le M$, $1 \le v \le M$, y $\gcd(u,v)=1$.

Llegamos a la conclusión de que $$\frac{f_k(N)}{N^2}=\frac{f_1(M)}{N^2}=\frac{f_1(M)}{(kM+r)^2}$$

Un poco de manipulación de la muestra que la cantidad de la derecha es igual a $$\frac{f_1(M)}{M^2}\left(\frac{1}{k^2}\right)\left(\frac{1}{1+\frac{2r}{kM}+\frac{r^2}{k^2M^2}}\right)$$

Ahora vamos a $N \to \infty$. A continuación,$M=M(N)\to\infty$. Por un estándar de resultados sobre el número de pares ordenados de enteros primos relativos a $M$, $$\lim_{M\to\infty}\frac{f_1(M)}{M^2}=\frac{6}{\pi^2}$$

Tenga en cuenta que como $M\to\infty$, $$1 +\frac{2r}{kM}+\frac{r^2}{k^2M^2} \to 1$$

y el resultado de la siguiente manera.

Answer 2

Sólo una copia...

Otro enfoque que es más fácil y es más probabilístico desde el principio...

Uno puede utilizar el honesto probabilidad de $P(X=n)=n^{-s}/\zeta(s)$$s>1$. De esto podemos demostrar que:

Eventos 1 $E_{p}=\{X$ es divisible por $p\}$ son independientes.

2 $P(gcd(X,Y)=n)=n^{-2s}/\zeta(2s)$ independientes $X$$Y$. Si $s\to 1$ $n=1$ obtenemos la demanda.

Ver ex. 4.2. en Probabilidad con martingales por Williams.