7
$\begingroup$

Given $2$ randomly chosen integers $x,y$ what is the probability that a integer $k$ is the greatest common divisor of $x$ and $y$?

I know that the probability of $x,y$ being coprime is $\frac{1}{\zeta(2)} = \frac{6}{\pi^2}$ this could be a starting point. I think one could try to analyse $P(x/k $ and $ y/k$ coprime $| k$ divides $x$ and $y)$ But then the distribution of $x$ and $y$ is no longer uniform. Maybe there is some helping hand here?

  • 0
    Depends on which probabilities you mean2011-05-17

2 Answers 2

9

What we will be computing is technically not a probability. The most one can say is that it is a limit of probabilities.

Let $k$ be a fixed positive integer. For any positive integer $N$, let $f_k(N)$ be the number of ordered pairs $(x,y)$ such that $1 \le x \le N$, $1 \le y \le N$, and $\gcd(x,y)=k$. We will (with the help of a major result that we only quote) show that $\lim_{N\to\infty} \frac{f_k(N)}{N^2}=\frac{6}{k^2\pi^2}$

The proof is easy, but for the sake of completeness we do all the details. Let $r(N)$ be the remainder when $N$ is divided by $k$. Then $N=kM(N)+r(N)$ for some quotient $M(N)$. For simplicity, we write $r$ for $r(N)$, and $M$ for $M(N)$, without forgetting their dependence on $N$.

Note that $f_k(N)=f_k(kM)$. This is because if in the ordered pair $(x,y)$, one or both of $x$ and $y$ is in the interval $[kM+1, N]$, then that $x$ (or $y$) is not divisible by $k$.

Note also that if each of $x$, $y$ is in the interval $[1,kM]$, then $\gcd(x,y)=k$ if and only if $x=ku$, $y=kv$, where $\gcd(u,v)=1$.
It follows that $f_k(N)=f_k(kM)=f_1(M)$ In less fancy language, the number of ordered pairs counted by $f_k(N)$ is the same as the number of ordered pairs $(u,v)$ such that $1 \le u\le M$, $1 \le v \le M$, and $\gcd(u,v)=1$.

We conclude that $\frac{f_k(N)}{N^2}=\frac{f_1(M)}{N^2}=\frac{f_1(M)}{(kM+r)^2}$

A little manipulation shows that the quantity on the right is equal to $\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)$

Now let $N \to \infty$. Then $M=M(N)\to\infty$. By a standard result about the number of ordered pairs of relatively prime integers up to $M$, $\lim_{M\to\infty}\frac{f_1(M)}{M^2}=\frac{6}{\pi^2}$

Note that as $M\to\infty$, $1 +\frac{2r}{kM}+\frac{r^2}{k^2M^2} \to 1$

and the result follows.

0

Just a copy...

Another approach which is easier and is more probabilistic from the beginning...

One may use the honest probability $P(X=n)=n^{-s}/\zeta(s)$ for $s>1$. From this we may prove that:

1 Events $E_{p}=\{X$ is divisible by $p\}$ are independent.

2 $P(gcd(X,Y)=n)=n^{-2s}/\zeta(2s)$ for independent $X$ and $Y$. If $s\to 1$ for $n=1$ we obtain the claim.

See ex. 4.2. in Probability with martingales by Williams.