Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.