# GCD of two large integers

For two random $d$ digit integers $a,b$, what is the probability $\gcd(a,b)<B$? Here $B$ is much much smaller than $a,b$.

-

The probability that two integers, chosen uniformly at random from $1,2,\dots,n$, have greatest common divisor $g$, is (for large $n$) $\displaystyle{6\over\pi^2g^2}$. So the probability that the gcd is less than $B$ is $\displaystyle{6\over\pi^2}\sum_{g=1}^{B-1}{1\over g^2}$.

A reference is J. Chidambaraswamy and R. Sitarmachandrarao, On the probability that the values of $m$ polynomials have a given g.c.d., Journal of Number Theory 26 (1987) 237–245.

There is a good exposition at http://aperiodical.com/2013/06/cushing-your-luck-properties-of-randomly-chosen-numbers/

Choosing from $1,2,\dots,n$ isn't quite the same as choosing among $d$-digit numbers, but I suspect that for large $d$ the answers come out the same.

-

Heuristically: For $k>B$, the probability that both $a$ is a multiple of $k$ is essentially $\frac1k$, hence that both $a$ and $b$ are multiples of $k$ it is $\frac1{k^2}$. Naively assuming independence (which gives an upper bound), the probability that $\gcd(a,b)>B$ is therefore at most $\le \sum_{k=B}^\infty \frac1{k^2}=\frac{\pi^2}6-\sum_{k=1}^B\frac1{k^2}$. For small $B$ this estimate is not very good.

-