A finite set S satisfying $\forall n \in \mathbb{N}: \exists a \in S: \gcd(n,a)=1 \lor a | n$ I'd like some help with this question. 
Suppose we have some finite set S satisfying $\forall n \in \mathbb{N}: \exists a \in S: \gcd(n,a)=1 \lor a | n$,
 and $1 \notin S$. 
Then we're asked to prove that $S$ contains elements $a,b$ (not necessarily distinct) such that $\gcd(a,b)$ is prime.
I've shown that, assuming $S$ contains no primes, $S$ contains a squarefree element. I've found some things but nothing conclusive. Any help?
 A: Let $P= \forall n \in \mathbb{N}: \exists a \in S: \gcd(n,a)=1 \lor a | n$
We prove the contrapositive:  If there are no two elements $a,b$ of $S$ such that $\gcd(a,b)$ is prime, $P$ is false.
We can assume that no element in $S$ divides any other because we can remove all that are multiples of any other without affecting the truth of $P$ and without removing one of the pair that has $\gcd(a,b)$ prime.
$S$ cannot contain a prime $p$ because $\gcd(p,p)=p$ is prime
If $S$ contains a prime power $p^n$ for $n \gt 1$, $P$ fails for $p$ unless $S$ also contains $p$, for which see above.
If $S$ contains a number coprime to all other members of $S$, it must have at least two prime factors $p$ and $q$.  Then $p$ violates $P$.
If $S$ contains a number $a$ with only two distinct prime factors, $p,q$, either every element of $S$ has a factor $pq$, in which case $p$ violates $P$, or some number $b$ has no factor $p$.  In that case $a$ and $b$ must both have a factor $q^2$.  Then $pq$ makes $P$ false.
If a number $a$ in $S$ is divisible by $p^2$ for some prime $p$, every other number in $S$ must share at least one prime factor with $a/p$ making $P$ false.
Every number in $S$ has at least three prime factors and shares at least two with every other element of $S$.  Take an element of $S$ and divide it by one of the primes in its factorization.  It still shares at least one prime factor with all other elements of $S$, so $P$ fails.
