Take the 2-minute tour ×

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|improve this question

3 Answers 3

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|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|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|improve this answer

Your Answer


