Let $S$ be a set containing finitely many positive integers greater than 1 with property: for all $n \in \mathbb{Z_+}$, there exist $s \in S$ such that $\gcd(s, n) = 1$ or $\gcd(s,n) = s$.
Show that that there exists $s, t \in S$ such that $\gcd(s, t)$ is a prime number.
Let $n$ be a square-free integer with a minimal number of prime divisors such that $\gcd(n,s)>1$ for all $s\in S$. By the hypothesis, there exists a divisor $d$ of $n$ in $S$. Suppose $d=p_1\cdots p_k$ ($p_1,\ldots,p_k$ are distinct primes). Consider the multiples of $p_1$ that are contained in $S$; call this set $T$. If $\gcd(d,t)>p_1$ for all $t\in T$, then we would have $\gcd(\frac n{p_1},s)>1$ for all $s\in S$, contradicting the minimality of the number of prime divisors of $n$. Hence there exists $t\in T\subseteq S$ such that $\gcd(d,t)=p_1$.