BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

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

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Source: — Problem Solving |

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 3008
Joined: Mon Aug 22, 2016 6:19 am
Location: Grand Central / New York
Thanked: 470 times
Followed by:34 members

by Jay@ManhattanReview » Tue Mar 14, 2017 1:00 am
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
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.
Top
User avatar
GMAT Instructor
Posts: 15539
Joined: Tue May 25, 2010 12:04 pm
Location: New York, NY
Thanked: 13060 times
Followed by:1906 members
GMAT Score:790

by GMATGuruNY » Tue Mar 14, 2017 12:13 pm
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.
Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.

As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.

For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Wed Mar 15, 2017 5:15 pm
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.
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Wed Mar 15, 2017 5:17 pm
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!
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Wed Mar 15, 2017 5:19 pm
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.
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Wed Mar 15, 2017 5:22 pm
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.
Top
Master | Next Rank: 500 Posts
Posts: 157
Joined: Sat Nov 19, 2016 5:34 am
Thanked: 2 times
Followed by:4 members

by hazelnut01 » Wed Mar 15, 2017 5:34 pm
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)�³?
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Thu Mar 16, 2017 8:08 pm
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)�³.
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Thu Mar 16, 2017 8:09 pm
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)�³.
Top
Post new topic Post Reply
• Page 1 of 1