Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was wondering if anybody here might provide me with a hint for this rather innocuous-looking problem:

If $X:= \{pq: p, q \mbox{ are prime numbers and } p\neq q\}.$ In addition, let us suppose that $A\subseteq X$ and $B=X\setminus A.$ Prove that there is an infinite set $P$ of prime numbers such that $Y:= \{pq: p, q \in P \mbox{ and } p \neq q\}$ is contained in $A$ or $B$.

Thank you!

share|cite|improve this question
I have added the ramsey-theory tag, since what I think is the natural answer is an application of Ramsey's theorem. – Andrés E. Caicedo Jan 27 '13 at 2:21
up vote 5 down vote accepted

This is an application of Ramsey's theorem. One way to state the relevant version in the language of graphs is:

Suppose an infinite set $X$ of vertices is given, and each edge between two distinct vertices is colored either red or blue. Then there is an infinite subset $H$ of vertices with all edges between them of the same color.

Apply the result here with the set of prime numbers playing the role of $X$. Color an edge between $p$ and $q$ red iff $pq\in A$ and blue otherwise (that is, iff $pq\in B$). The infinite $H$ the theorem guarantees has the property that $\{pq\mid p,q\in H,p\ne q\}$ is a subset of $A$ or of $B$; the first case corresponds to edges between vertices in $H$ being red, the second corresponds to them being blue.

share|cite|improve this answer
For other interesting applications of Ramsey's theorem, see:… – Andrés E. Caicedo Jan 27 '13 at 2:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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