  Fix $\alpha >0$, and sample $N$ integers uniformly at random from
$\{1,2,\ldots ,\lfloor e^{\alpha N}\rfloor \}$. Given $\eta >0$, the
probability that the maximum of the pairwise GCDs lies between $N^{2-\eta }$
and $N^{2+\eta}$ 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.
