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 Prep