Page 1 of 1

0568 Q21 (alternative methods)

Posted: Sun Jan 15, 2012 4:16 am
by yoyobarn
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.

Re: 0568 Q21 (alternative methods)

Posted: Sun Jan 15, 2012 11:17 am
by owlpride
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.)

Re: 0568 Q21 (alternative methods)

Posted: Sun Jan 15, 2012 9:50 pm
by yoyobarn
Thanks!