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?

  • 1
    Isn't it $\frac{1}{k^2\zeta(2)}$?2011-05-17
  • 0
    @lhf what do you mean with "it" and I don't get how you got there :-)2011-05-17
  • 0
    According to what distribution are we choosing "at random" here. There is no uniform distribution on the integers.2011-05-17
  • 0
    @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$2011-05-17
  • 0
    @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)}$.2011-05-17
  • 0
    @lhf I had this thought but doesn't dividing $k$ out of the integers change the probability distribution of the coordinates?2011-05-17
  • 0
    @user3123, I don't think so. Plus the result seems to be true empirically :-)2011-05-17
  • 0
    @lhf thank you so far I also think it is true, maybe someone can provide an argument why you can do it that way2011-05-17
  • 0
    @user3123: Insignificantly if $N$ is large, and not at all if $N$ is a large multiple of $k$.2011-05-17
  • 0
    You'd just have to show that the two probabilities are independent, right?2011-05-17
  • 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.