MAXIMUM GCD AMONG PAIRS OF RANDOM INTEGERS

摘要

Fix α > 0, and sample N integers uniformly at random from ! 1, 2, . . . , " eαN #$ . Given η > 0, the probability that the maximum of the pairwise GCDs lies between N2?η and N2+η converges to 1 as N → ∞. More precise estimates are obtained. This is a Birthday Problem: two of the random integers are likely to share some prime factor of order N2% log(N). The proof generalizes to any arithmetical semigroup where a suitable form of the Prime Number Theorem is valid.