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

Consider the following exercise:

Let $P_1$ be the set of all primes, $\{2,3,5,7,\cdots\}$, and for each integer $n$, let $P_n$ be the set of all prime multiples of $n$, $\{2n,3n,5n,7n,\cdots\}$. Which of the following intersections is nonempty?

A $P_{1}\cap P_{23}$
B $P_{7}\cap P_{21}$
C $P_{12}\cap P_{20}$
D $P_{20}\cap P_{24}$
E $P_{5}\cap P_{25}$

Here are my questions:

  • When are the integer $m$ and $n$ such that $P_m\cap P_n\neq\emptyset $?

  • Are there any other methods to the solve the question in the exercise except than "trial and error"?

share|cite|improve this question
up vote 8 down vote accepted

Consider $P_m \cap P_n$ where $m \neq n$

If $x \in P_m \cap P_n$, then be definition, $x = mp_m$ and $x = np_n$ for some prime $p_m$ and $p_n$.

Hence, we get that $\frac{m}{n} = \frac{p_n}{p_m}$

So the intersection of $P_m$ and $P_n$ is non-trivial iff the $\frac{m}{n}$ in the reduced form is a ratio of two primes.

In fact, if $\frac{m}{n}$ in the reduced form is a ratio of two primes, then the intersection has only one element namely $\{\text{lcm}(m,n)\}$

In your case, the intersection is non-trivial only for the case $P_{12} \cap P_{20}$ which is nothing but $\{60\}$

share|cite|improve this answer

Some hint:

Suppose $x\in P_m\cap P_n$ that means that there are two prime numbers $p,q$ such that $x=pm=qn$.

  • If $p=q$ then clearly $m=n$.
  • Otherwise $p\mid qn$ therefore $p\mid n$, and just as well $q\mid m$. When does that happen?
share|cite|improve this answer

HINT $\rm\ k\in P_m\cap P_n\iff k = p\:m = q\:n\ \Rightarrow\ m,\:n\ $ have the same number of prime factors - which is true for only one of the choices.

The general question is easily answered for any $\rm\:P_1\:$ whose elements are pairwise coprime, viz. $\rm\ p\:m = q\:n \ \iff\ n/m = p/q\:,\ $ so $\rm\:P_m\cap P_n \neq \emptyset\ \iff$ the reduced form of $\rm\:n/m\:$ has both numerator and denominator in $\rm\:P_1\:$ (no cancellation is possible due to the coprimality hypothesis). For example one could take $\rm\:P_1\:$ to be the sequence of prime-indexed Fibonacci numbers.

share|cite|improve this answer

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.