Find the remainder when 12^190 is divided by 1729 ?

Question

A. 12
B. 1
C. 1728
D. 1717
E. 4

Hi guys,

Following is a remainder question (conceptual). Please help me in understanding its concept.

Looking forward to your replies.

Regards
Vinni

mikemcgarry · Answer

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: https://magoosh.com/gmat/2012/gmat-quant ... emainders/ https://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^187) - (12^187) 12^190 = *(12^187) - (12^3)*(12^184) 12^190 = *(12^187) - (12^3)*(12^184) - (12^184) + (12^184) 12^190 = *(12^187) - *(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) - 12 So, 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 :-)

vinnik · Answer

Mike,

Thanks for your reply and for posting the following links:-

https://magoosh.com/gmat/2013/gmat-quant ... questions/

https://magoosh.com/gmat/2012/gmat-quant ... emainders/

The first link is really harder (800+ practice questions), but if anyone understands these kinds of questions, then it becomes a lot easier to solve anything of this type.

Above all, one must be familiar with the concept of cyclicity to solve these.

Appreciate it.

Regards
Vinni

clearwater · Answer

Hi vinnik, This problem can be solved using remainder theorm. https://www.pagalguy.com/news/cat-2012-q ... -a-8795953. Here's the explanation for the remainder theorm 12^(190) can be written as. ((12^3)^63)* 12. 12^3 when divided by 1729 gives a remainder -1. so in the numerator we have -12. Now acccording to remainder theorm the answer will be 1729-12=1717.

sagiyer · Answer

Yes, this problem can be solved by utilizing the remainder theorem. To apply the remainder theorem, attempt to express the numerator such that it the remainder when divided by the denominator is +1 or -1.

So, in this case, we will express 12^190 as (12^3)^63X12. That is because we know 12^3 = 1728 (which is 1 less than the denominator). So now the expression becomes

((12^3)^63x12)/1728 = (-1)^63x12

-1^ odd number = -1. Therefore the expression becomes = -12.

Hence remainder = 1729-12 = 1717.

shameekv · Answer

2 things to keep in mind while solving these type of questions

1) The remainder of the form  \frac{(a*b*c)}{d}  is the product of their individual remainders.

i.e.  Remainder of \frac{a}{d} * Remainder of \frac{b}{d} * Remainder of \frac{c}{d}

2) Remainder can be expressed in either positive or negative form for eg.  Remainder of \frac{1728}{1729}  can be 1728 or -1 (i.e. 1728 - 1729)

Now here the Remainder of expression (12^190)/1729 = Remainder of (((12^3)^ 63) * 12)/1729

= Remainder of (12^3)^63/1729 * Remainder of 12/1729

That will be (Remainder of (1728^63)/1729) * (Remainder of 12/1729)

i.e.  (-1)^63 * 12 = -12

Again negative remainder here so a positive remainder will be  1729-12 = 1717

Kudo if the post helps!!!

Find the remainder when 12^190 is divided by 1729 ?

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

Find the remainder when 12^190 is divided by 1729 ?

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards