What is the remainder when (63)^53 is divided by 64.
A) 1
B) 2
C) 16
D) 63
E) cannot be determined
What is the remainder when (63)^53 is divided by 64. A) 1 B
This topic has expert replies
-
- Master | Next Rank: 500 Posts
- Posts: 157
- Joined: Sat Nov 19, 2016 5:34 am
- Thanked: 2 times
- Followed by:4 members
GMAT/MBA Expert
- Jay@ManhattanReview
- GMAT Instructor
- Posts: 3008
- Joined: Mon Aug 22, 2016 6:19 am
- Location: Grand Central / New York
- Thanked: 470 times
- Followed by:34 members
Hi ziyuenlau,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
(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
- 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
Question stem, rephrased: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
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
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
-
- 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
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.
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.
-
- 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
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!
-
- 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
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.
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.
-
- 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
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.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.].
-
- Master | Next Rank: 500 Posts
- Posts: 157
- Joined: Sat Nov 19, 2016 5:34 am
- Thanked: 2 times
- Followed by:4 members
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 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.
-
- 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
Sure, but let me just go with the parts that are relevant to this problem.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)�³?
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)�³.
-
- 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
(a - b)�³ works too, in the abstract: every term will be divisible by a except for the product of all the b's, (-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)�³?