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

[hazelnut01]

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

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

[Jay@ManhattanReview]

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

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

Hi ziyuenlau,

(63)^53 can be written as (64 - 1)^53. 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.]. Thus the question becomes: what is the remainder upon the division of -1 by 64? The answer to this question is [spoiler]64 - 1 = 63[/spoiler]

The correct answer: D

Hope this helps!

Relevant book: Manhattan Review GMAT Math Essentials Guide

-Jay
_________________
Manhattan Review GMAT Prep

Locations: New York | Bangalore | Guangzhou | Buenos Aires | and many more...

Schedule your free consultation with an experienced GMAT Prep Advisor! Click here.

[GMATGuruNY]

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.

[Matt@VeritasPrep]

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.

[Matt@VeritasPrep]

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!

[Matt@VeritasPrep]

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.

[Matt@VeritasPrep]

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.

[hazelnut01]

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)�³?

[Matt@VeritasPrep]

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)�³.

[Matt@VeritasPrep]

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)�³.