What is the probability that GCD of $(a,b)$ is $b$?

Question

My question is quite simple. I have been googling a lot lately trying to find a solution to this: Given a sequence of n integers $[1,2,...,n]$. If we pick two numbers randomly from the set say, a and b. The find the probability that GCD$(a,b)=b$?

For example:

If $N=1$, the probability is $1/1$.

If $N=2$, probability is $3/4$ $[(1,1),(2,1),(2,2)$ satisfy out $of (1,1),(2,1),(2,2), (1,2)$ total cases]

If $N=3$, the probability is $5/9$.

My searches on google show me pages where : probability of GCD$(a,b)=1$ (relative co-prime) are calculated using the zeta function. I don't really know how to use that in this case !! Or whether if that is applicable here!!

Answer 1

There are good estimates available. Let $d(n)$ be the number of divisors of $N$. By a result of Dirichlet, $$\sum_{n\le N} d(n)=N\log N+(2\gamma-1)N+O(\sqrt{N}),\tag{1}$$ where $\gamma$ is Euler's gamma. Divide by $N^2$ to get the probability, for "randomly" chosen pairs $(a,b)$ where $1\le a\le N$, $1\le b\le N$.

Remark: Since questions similar to this one have been asked many times, we make some additional comments. The "error term" is, for large $N$, very much smaller than the two "main" terms, but it still can be quite large for large $N$. There have been improvements on the exponent $1/2$ since the time of Dirichlet. However, one should not confuse the estimate on the right-hand side of (1) with a formula for the left-hand side.

Answer 2

Note that $\operatorname{gcd}(a, b) = b$ implies that $a$ is a multiple of $b$. There are $\left\lfloor\dfrac{N}{b}\right\rfloor$ multiples of $b$ in the set $\{1, \dots, N\}$.

Taking the sum over all the possible values of $b$, there are $\displaystyle\sum_{b=1}^N\left\lfloor\frac{N}{b}\right\rfloor$ pairs $(a, b)$ such that $\operatorname{gcd}(a, b) = b$.

Therefore the probability of selecting such a pair is $\dfrac{1}{N^2}\displaystyle\sum_{b=1}^N\left\lfloor\frac{N}{b}\right\rfloor$. I don't know if this sum can be simplified.

Answer 3

Note that if $(a,b)=b$ then $0\lt a=kb \le n$. The number of pairs $a,b$ with $(a,b)=b$ is therefore the same as the number of pairs $b,k$ with $0\lt kb \le n$.

This is the same as the number of integer points in the first quadrant between the axes $x=0$ and $y=0$ and the rectangular hyperbola $xy=n$ and this is also the sum of the arithmetical function $d(n)$ which is $$n\log n+(2\gamma-1)n+O(\sqrt n)$$

Divide this by the number of pairs to get the probability. Note that this includes the possibility $a=b$, which could easily be excluded if necessary. The precise calculation also depends on whether the order matters, but the principle is the same.