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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.