E. E. Pyle

Maximum GCD Among Pairs of Random Integers

Fix $α>0$, and sample $N$ integers uniformly at random from $\{1,2,\ldots ,\lfloor e^{αN}\rfloor \}$. Given $η>0$, the probability that the maximum of the pairwise GCDs lies between $N^{2-η}$ and $N^{2+η}$ converges to 1 as $N\to \infty$. More precise estimates are obtained. This is a Birthday Problem: two of the random integers are likely to share some prime factor of order $N^2/\log [N]$. The proof generalizes to any arithmetical semigroup where a suitable form of the Prime Number Theorem is valid.