# Show that there exists $s, t \in S$ such that $\gcd(s, t)$ is a prime

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.

• What's the source of this question? – Bart Michels Aug 25 '15 at 15:17
• It's a problem from my teacher. Of course he didn't reveal the source. – primitiveroot Aug 25 '15 at 15:27
• It could be interesting to investigate $\{s\in S:(\exists\text{ square-free }n\in\mathbb N:s\mid n\wedge\gcd(n,t)>1\;\forall t\in S)\}$. It looks like this set inherits that property of $S$, reducing the problem to a (usually) smaller set (consisting of square-free numbers only)... – Bart Michels Aug 26 '15 at 18:00
• Why can't $S$ be just the set containing a prime? For example, $S = \{2\}$? Here, for all even numbers, $(s, n) = s = 2$, and for all odd numbers, $(s, n) = 1$. Then $(s, s) = s$, as in the question. And if it works for $S$ with only one element, then all $S$ would have at least one element and the property would hold. – shardulc says Reinstate Monica Aug 28 '15 at 13:31
• @shardulc $S$ can be a singleton, but this isn't quite the most interesting case. In response to your last claim, consider $S=\{2\cdot3,3\cdot5,5\cdot2\}$. – Bart Michels Aug 28 '15 at 13:53

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$.
• I'm not sure. But it's always a good idea to minimalise or maximize something when you make a choice. Because the size of the primes doesn't really have a significance in this problem, I chose not to minimize $n$, but the number of prime divisors of $n$, which seemed a more natural choice. – Bart Michels Sep 3 '15 at 8:17
• A friend of mine tried to show that there exists a prime number $s \in S$ so that $gcd(s, s) = s \in \mathbb{P}$ like @shardulc . My teacher doubted this, but when we asked for the solution it turned out that he didn't have one :( – primitiveroot Sep 3 '15 at 8:34
• Such prime number need not exist; take for example $S=\{2\cdot3,3\cdot5,5\cdot2\}$: this set satisfies the condition, but does not contain a prime. – Bart Michels Sep 3 '15 at 10:07