Fix $n$ and $k$. I want a set $S\subseteq\{1,\ldots,n\}$ with the property that for every $x\in S$,

$$\mathrm{gcd}\bigg(x,\prod_{y\in A\setminus\{x\}}y\bigg)<\frac{x}{k}.$$

How small should a random $S$ be to have this property with high probability? More importantly, what sort of math is this, and where can I learn more? (I only guessed in my tags.)