Manhattan GMAT Challenge Problem of the Week – 25 Jan 2011

by Manhattan Prep, Jan 25, 2011

Here is a new Challenge Problem! If you want to win prizes, try entering our Challenge Problem Showdown. The more people enter our challenge, the better the prizes.

Question

If x, n, and y are all positive integers, is [pmath]x^n[/pmath] divisible by y?

(1) x is divisible by [pmath]y^n[/pmath]

(2) [pmath]x^y[/pmath] is divisible by y

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(C) BOTH statements TOGETHER are sufficient, but NEITHER statement ALONE is sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient to answer the question asked, and additional data are needed.

Answer

The problem tells us that x, n, and y are all positive integers. We are asked whether [pmath]x^n[/pmath] is divisible by y. For this to be true, all of ys prime factors (counting repeats) must be contained in [pmath]x^n[/pmath], or in n copies of x.

Statement 1: SUFFICIENT. We are told that x is divisible by [pmath]y^n[/pmath]. In other words, n copies of ys prime factors are all contained in x. Since n is 1, 2, 3, etc., this means that at least one copy of ys prime factors must be contained in x, and therefore in n copies of x.

For example, take y = 3 and n = 2. Then x must be divisible by [pmath]3^2[/pmath], or 9. The question is [pmath]x^n[/pmath] divisible by y" becomes is [pmath]x^2[/pmath] divisible by 3?. Since x itself already contains at least two 3s as prime factors, we know for a fact that [pmath]x^2[/pmath] contains a 3 (in fact, we know it contains at least four 3s).

Statement 2: INSUFFICIENT. This is a tricky statement (in fact, the author initially tripped up on it himself!). If [pmath]x^y[/pmath] is divisible by y, then for a number of cases, the question can be answered Yes. For instance, if we take x = 4 and y = 2, with [pmath]4^2[/pmath] divisible by 2 (as the statement requires), then we also know that [pmath]4^n[/pmath] is divisible by 2.

However, one exception is that y might itself be a power of x. For instance, take x = 2 and y = 4. Then the statement holds ([pmath]2^4[/pmath] is divisible by 4), but we cant say that [pmath]2^n[/pmath] is divisible by 4 for all positive integers n.

The correct answer is A: Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

Special Announcement: If you want to win prizes for answering our Challenge Problems, try entering our Challenge Problem Showdown. Each week, we draw a winner from all the correct answers. The winner receives a number of our our Strategy Guides. The more people enter, the better the prize. Provided the winner gives consent, we will post his or her name on our Facebook page.