9

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!!

Mahdi Khosravi
  • 3,989
user93470
  • 241
  • 1
  • 3
  • 9
  • Hint: This $\gcd(a,b)=b$ if and only if $b\mid a$ – Thomas Andrews Sep 06 '13 at 16:33
  • How do I calculate O(sqrt(N))?? – user93470 Sep 06 '13 at 17:35
  • You don't - it is an error term. – Thomas Andrews Sep 06 '13 at 17:36
  • Andre's solution means that, if $P(N)$ is your probability, then there is some constant $C$ such that for all $N$, $$\left|P(N)-\frac{\log N + 2\gamma-1}{N}\right|< \frac{C}{N^{3/2}}$$ So for large enough $N$, your probability is close to $\frac{\log N+2\gamma -1}{N}$. But you'd have to ask Andre if he has any bound on that constant $C$. – Thomas Andrews Sep 06 '13 at 17:38
  • http://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant. Do I use this Euler's gamma value for my computation?? – user93470 Sep 06 '13 at 17:44
  • Yes, that's the $\gamma$ you want. It hardly adds anything to the value, since $2\gamma-1<0.2$ and that is dwarfed by $\log N$ for $N$ reasonably large. – Thomas Andrews Sep 06 '13 at 17:46
  • A terminology point: We either say "$a,b$ are relatively prime," or we say, "$a,b$ are co-prime." We do not say "$a,b$ are relatively co-prime." – Thomas Andrews Sep 06 '13 at 17:51
  • This problem looks similar to the one here: http://www.codechef.com/SEPT13/problems/COOLGUYS Expect in that case they want the probability expressed as an irreducible fraction, so approximations won't work. – AncientEgypt Sep 11 '13 at 04:58

3 Answers3

8

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.

André Nicolas
  • 507,029
3

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.

Michael Albanese
  • 99,526
2

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.

Mark Bennet
  • 100,194