# Given $2$ randomly chosen integers $x,y$ what is $P(k=gcd(x,y))$?

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?

-
Isn't it $\frac{1}{k^2\zeta(2)}$? –  lhf May 17 '11 at 17:37
@lhf what do you mean with "it" and I don't get how you got there :-) –  Listing May 17 '11 at 17:48
According to what distribution are we choosing "at random" here. There is no uniform distribution on the integers. –  ncmathsadist May 17 '11 at 17:48
@ncmathsadist what was in my mind is that you expect an uniform distribution in an interval $1$ and $N$ and then let $N \rightarrow \infty$ –  Listing May 17 '11 at 17:50
@user3123, exactly. Then in the integer square $[1,N]\times[1,N]$ the probability of a point having both coordinates a multiple of $k$ is $\frac{1}{k^2}$, right? Dividing both coordinates by $k$ leaves you with a coprime pair with probability $\frac1{\zeta(2)}$. –  lhf May 17 '11 at 18:03

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.

-

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.

-