## 0568 Q21 (alternative methods)

Forum for the GRE subject test in mathematics.
yoyobarn
Posts: 80
Joined: Sun Dec 19, 2010 7:01 am

### 0568 Q21 (alternative methods)

21. Let P1 be the set of all primes, 2, 3, 5, 7, . . . , and for each integer n, let Pn be the set of all prime multiples
of n, 2n, 3n, 5n, 7n, . . . . Which of the following intersections is nonempty?
(A) P1 P23 (B) P7 P21 (C) P12 P20 (D) P20 P24 (E) P5 P25

Hi,

Is there a number-theory method to do this question?

My method was to note that P_12 and P_20 both contain 60=5*12=3*20.

Thank you very much.

owlpride
Posts: 204
Joined: Fri Jan 29, 2010 2:01 am

### Re: 0568 Q21 (alternative methods)

I think the problem is completely solved by the uniqueness of prime factorization. The intersection of P_m and P_n is non-empty if and only if m and n have the same prime factors except for one extra term in each; in which case the intersection contains precisely one number. For example, 12 = 2*2*3 and 20 = 2*2*5. The intersection of P_12 and P_20 is {2*2*3*5}. (Common factors in regular font, extra ones in bold.)

yoyobarn
Posts: 80
Joined: Sun Dec 19, 2010 7:01 am

Thanks!