Problem Solving

What is the remainder when (63)^53 is divided by 64.

A) 1
B) 2
C) 16
D) 63
E) cannot be determined

ziyuenlau wrote:What is the remainder when (63)^53 is divided by 64.

A) 1
B) 2
C) 16
D) 63
E) cannot be determined

Question stem, rephrased:
If x=63, what is the remainder when x^(odd power) is divided by x+1?

Test EASY CASES for x.

x=2:
2¹/3 = 2/3 = 0 R2.
2³/3 = 8/3 = 2 R2.
2�/3 = 32/3 = 10 R2.

x=3:
3¹/4 = 3/4 = 0 R3.
3³/4 = 27/4 = 6 R3.
3�/4 = 243/4 = 60 R3.

In every case, the remainder is equal to the value of x.
Thus, when x=63, the remainder will be equal to 63.

The correct answer is D.

It's easier than that, I think, if we use negative remainders.

63 / 64 = 0, remainder 63, but we could also think of this as remainder -1.

With that in mind, since 63 has a remainder of -1 when divided by 64, we can replace 63 with -1:

63�³ =>

(-1)�³ =>

-1

So our remainder TO ANY ODD POWER will be -1.

Since -1 is the same as +63, we're back where we started, and the answer is D.

This is more of an Indian CAT question than a GMAT question, though: the GMAT doesn't (as far as I know) require you to know very much about remainders and modular arithmetic. A shame, because it's such a great topic!

If you're more comfortable with polynomials than remainders, another way to approach this problem is as follows:

63�³ =

(64 - 1)�³ =>

64�³ ± (lots of terms with 64 as a coefficient) - 1�³

Since the only term that WON'T divide by 64 (= won't have 64 as a coefficient) is the last one, our remainder is only in that last term: -1�³. So our remainder is -1, or +63.

Jay@ManhattanReview wrote: Since 64 is divisible by the divisor 64, we are left with (-1)^53 = -1 ['-1' raised to the power of an odd number is '-1.].

But (64 - 1)�³ ≠ 64�³ - 1�³. Taken mod 64, we are left with -1�³, but reiterating that it's because of polynomial expansion (as I've done above) is important.

Matt@VeritasPrep wrote:If you're more comfortable with polynomials than remainders, another way to approach this problem is as follows:

63�³ =

(64 - 1)�³ =>

64�³ ± (lots of terms with 64 as a coefficient) - 1�³

Since the only term that WON'T divide by 64 (= won't have 64 as a coefficient) is the last one, our remainder is only in that last term: -1�³. So our remainder is -1, or +63.

Dear @Matt, Could you help to elaborate the polynomial or binomial expansion in general? I am confused with that. (64 - 1)�³ => (a - b)�³?

ziyuenlau wrote:Dear @Matt, Could you help to elaborate the polynomial or binomial expansion in general? I am confused with that. (64 - 1)�³ => (a - b)�³?

Sure, but let me just go with the parts that are relevant to this problem.

Suppose we have (3 - x)�. Unpacking this, we get (3 - x) * (3 - x) * (3 - x) * (3 - x), and we can see that every term will be multiplied by 3 at least once except for the very last part, -x * -x * -x * -x. (If we use Pascal's Triangle - not necessary for or even really relevant to the GMAT - we can expand easily enough: x� - 12x³ + 54x² - 108x + 81.)

So everything is divisible by 3 except the last term.

(64 - 1)�³ would expand in much the last way, every term in the expansion will have been multiplied by 64 at least once and hence be divisible by 64 EXCEPT for the very last one, (-1)�³.

ziyuenlau wrote: Dear @Matt, Could you help to elaborate the polynomial or binomial expansion in general? I am confused with that. (64 - 1)�³ => (a - b)�³?

(a - b)�³ works too, in the abstract: every term will be divisible by a except for the product of all the b's, (-b)�³.