If I sample $N+1$ integers $x, x_1, \ldots, x_N$ uniformly and independently from $\{1, \ldots, M=2^k\}$, what is the probability that $x$ contains a prime divisor that does not divide any of the $\{x_i\}$? Upper/lower bounds and/or asymptotic approximations would also be of interest.
For prime $p$ and $x, x_1, \ldots, x_N$ as above, say $x$ is $p$-unique if $p | x$ and $p \nmid x_1, \ldots, p \nmid x_N$. For any fixed and sufficiently small prime $p$ (say, $p \leq \sqrt{M}$), the probability that $x$ is $p$-unique is $\frac{1}{p} \cdot \left(1-\frac{1}{p}\right)^N$. One can try to lower bound $\Pr[\vee_p \hspace{2pt} \mbox{$x$ is $p$-unique}]$ using the inclusion-exclusion principle and treating the events that $x$ is $p_1$-unique and $p_2$-unique as independent when $p_1, p_2$ are both sufficiently small (and distinct). Doing so gives a lower bound of $\sum_{p} \frac{1}{p} \left(1-\frac{1}{p}\right)^N - \sum_{p_1 \neq p_2} \frac{1}{p_1p_2} \left(1-\frac{1}{p_1}\right)^N \left(1-\frac{1}{p_2}\right)^N$ (where the sums are over sufficiently small primes). But I didn't know where to go from there.
This seems like a problem that would have been studied before in the context of multiplicative number theory but I have not managed to find any references.