vinnik wrote:
Hi guys,
Following is a remainder question (conceptual). Please help me in understanding its concept.
Find the remainder when 12^190 is divided by 1729 ?
A. 12
B. 1
C. 1728
D. 1717
E. 4
Answer is 1717
Looking forward to your replies.
Regards
Vinni
Dear
Vinni,
I'm happy to respond.
The first thing I'll say --- this is a couple notches harder than what the GMAT will expect you to know about remainders. For example, here are a couple blogs that covers what the GMAT does expect you to know:
http://magoosh.com/gmat/2012/gmat-quant ... emainders/http://magoosh.com/gmat/2013/gmat-quant ... questions/Also, as it turns out, this divisor, 1729, is a number with a famous history in mathematics:
https://en.wikipedia.org/wiki/1729_(number)
Here's how I would approach it.
Notice that 12^3 = 1728, so this divisor is 1729 = ((12^3) + 1). We will use that to our advantage.
12^190 = (12^3)*(12^187) = (12^3)*(12^187) + (12^187) - (12^187)
12^190 = [(12^3)+1]*(12^187) - (12^187)
12^190 = [(12^3)+1]*(12^187) - (12^3)*(12^184)
12^190 = [(12^3)+1]*(12^187) - (12^3)*(12^184) - (12^184) + (12^184)
12^190 = [(12^3)+1]*(12^187) - [(12^3)+1]*(12^184) + (12^184)
12^190 =
(1729)*(12^187) -
(1729)*(12^184) +
(12^184)The two purple terms are divisible by 1729, so when divided by 1729, they will have a remainder of zero. The green term, when divided by 1729, will have the same remainder as does 12^190 when divided by 1729. That's interesting --- we can use this trick to create a smaller number with the same remainder.
Notice, we could repeat this trick, and bring the number down by a factor of 12^6 again and again. The number 180 is certainly divisible by 6, so 186 must be----- we could drop the power of 12 from 12^190 all the way down to 12^4, that is, 186 powers lower, and we would still have the same remainder when divided by 1729. So, now the whole problem reduces to --- what is the remainder when 12^4 is divided by 1729?
12^4 = (12^3)*(12) = (12^3)*(12) + 12 - 12 =
[(12^3)+1]*(12) - 12So, when 12^4 is divided by 1729, we get the same remainder as when -12 is divided by 1729. OK, that's a little confusing, to have a negative dividend, but when we have one number with a certain remainder, all we have to do is add or subtract the divisor (or a multiple of the divisor) to get other numbers with t the same remainder. Here, I will just add 1729
(-12) + 1729 = 1717
Of course, 1717 < 1729, so when 1717 is divided by 1729, 1729 goes into it zero times with a remainder of 1717. That's the answer.
Does all this make sense?
Mike
_________________
Mike McGarry
Magoosh Test PrepEducation is not the filling of a pail, but the lighting of a fire. — William Butler Yeats (1865 – 1939)