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.

  • 1
    $\begingroup$ What's the source of this question? $\endgroup$ – Bart Michels Aug 25 '15 at 15:17
  • $\begingroup$ It's a problem from my teacher. Of course he didn't reveal the source. $\endgroup$ – primitiveroot Aug 25 '15 at 15:27
  • 1
    $\begingroup$ 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)... $\endgroup$ – Bart Michels Aug 26 '15 at 18:00
  • $\begingroup$ 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. $\endgroup$ – shardulc says Reinstate Monica Aug 28 '15 at 13:31
  • $\begingroup$ @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\}$. $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ That's brilliant! Can you tell me how could you come up with the idea considering the number of prime divisors? $\endgroup$ – primitiveroot Sep 3 '15 at 3:06
  • $\begingroup$ 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. $\endgroup$ – Bart Michels Sep 3 '15 at 8:17
  • $\begingroup$ 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 :( $\endgroup$ – primitiveroot Sep 3 '15 at 8:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Bart Michels Sep 3 '15 at 10:07

Your Answer

