Remainder

Expert replies

winnerhere: Master | Next Rank: 500 Posts; Posts: 231; Joined: Thu Apr 12, 2007 2:45 amFollowed by: 1 member; Thanked: 5 times

by winnerhere » Wed Jul 28, 2010 9:47 am

Find the remainder of 2^133 divided by 133

1) 1

2)2

3)128

4)131

Not sure if it is GMAT type sum. Still, any help is appreciated

Thanks,
Sai

Like this post

Source: Beat The GMAT — Problem Solving | Wed Jul 28, 2010 9:47 am

nithi_mystics: Senior | Next Rank: 100 Posts; Posts: 55; Joined: Mon Sep 07, 2009 9:11 pm; Location: California; Thanked: 4 times

by nithi_mystics » Thu Jul 29, 2010 2:25 pm

how do we solve this?

Thanks
Nithi

Like this post

4GMAT_Mumbai: Master | Next Rank: 500 Posts; Posts: 161; Joined: Mon Apr 05, 2010 9:06 am; Location: Mumbai; Thanked: 37 times

by 4GMAT_Mumbai » Thu Jul 29, 2010 11:11 pm

Hi,

This seems too tough for GMAT level. Not to say that such types of sums cannot be asked. It could be asked with easier numbers.

a. Instead of 133, the question could have asked for the reminder when 2 ^ 127 is divided by 127.

Here, one could use remainder theorem.

The denominator 127 = 2^7 - 1.

127 = 126 + 1 = (7 times 18) + 1

So, 2 ^ 127 = 2 ^ ((7 times 18) + 1)

= ((2^7) ^ 18 ) times 2.

This is the equivalent of finding the remainder when P(x) = 2 * (x ^ 18) is divided by (x-1), where x = 2^7.

The remainder in this case will be P(1) = 2 times (1 ^ 18) = 2.

b. Anyways, in this question, when 2^p is divided by 133, the remainders repeat with a cyclicality of 18.

Mod (133, 18) = 7.

Hence, the remainder when 2^133 is divided by 133 is same as the remainder when 2^7 is divided by 133. Hence, answer = 128.

Hope this helps. Thanks.[/spoiler]

Naveenan Ramachandran
4GMAT, Dadar(W) & Ghatkopar(W), Mumbai

Like this post

GMAT/MBA Expert

Rahul@gurome: GMAT Instructor; Posts: 1179; Joined: Sun Apr 11, 2010 9:07 pmFollowed by: 88 members; Location: Milpitas, CA; Thanked: 447 times

by Rahul@gurome » Fri Jul 30, 2010 7:11 pm

Solution:
2^133 = 2^(7*19) = (2^7)^19 = (128)^19 = (133 - 5)^19.
Now (133 - 5)^19 = 133^19 - 19C1*(133^18)*(5^1) + 19C2*(133^17)*(5^2) .............+19C18*(133^1)*(5^18) - 5^19.

In the above binomial expansion all the terms except -5^19 is divisible by 133.
So what we need to do is to find the remainder when 5^19 is divided by 133 and subtract that from 133.

Proceed to find the remainder when 5^19 is divided by 133.
Now 5^19 = (5^18)*5 = (125^6)*5 = {(133 - 8)^6}*5.
Now on expanding {(133 - 8)^6}*5 all other terms are divisible by 133 except for the last term which is (8^6)*5 = {(512)^2}*5 = {(532 - 20)^2}*5.
Now on expanding {(532 - 20)^2}*5 , since 532 is 133*4, all other terms are divisible by 133 except for last term which is (20^2)*5 = 2000.
On dividing 2000 by 133, the remainder is 5.
On subtracting 5 from 133, we have 133 - 5 = 128 as remainder.

Rahul Lakhani
Quant Expert
Gurome, Inc.
https://www.GuroMe.com
On MBA sabbatical (at ISB) for 2011-12 - will stay active as time permits
1-800-566-4043 (USA)
+91-99201 32411 (India)

Like this post

winnerhere: Master | Next Rank: 500 Posts; Posts: 231; Joined: Thu Apr 12, 2007 2:45 amFollowed by: 1 member; Thanked: 5 times

by winnerhere » Sun Aug 01, 2010 7:11 am

4GMAT_Mumbai wrote:Anyways, in this question, when 2^p is divided by 133, the remainders repeat with a cyclicality of 18.
Mod (133, 18) = 7.

Hence, the remainder when 2^133 is divided by 133 is same as the remainder when 2^7 is divided by 133. Hence, answer = 128.

Hope this helps. Thanks.[/spoiler]

how did you get to this step.Did you divide from 2^1 to 2^18 manually to find if the reminders repeat? or is there any oher way to find the number of powers after which the remaindr will repeat.

Thanks for your help friend

Like this post

winnerhere: Master | Next Rank: 500 Posts; Posts: 231; Joined: Thu Apr 12, 2007 2:45 amFollowed by: 1 member; Thanked: 5 times

by winnerhere » Sun Aug 01, 2010 8:11 am

Thank you so much rahul.But isnt it time consuming to convert into polynomials at every step.

Is there is a way , that we can split the 2^133 and 133 into diferent groups and then finding the remainder individualy? Just curious..Dont mind if I sound foolish

Thanks,

Like this post

pradeepkaushal9518: Legendary Member; Posts: 1309; Joined: Wed Mar 17, 2010 11:41 pmFollowed by: 5 members; Thanked: 33 times

by pradeepkaushal9518 » Mon Aug 02, 2010 4:12 am

is it a gmat question what is source?

Like this post

selango: Legendary Member; Posts: 1460; Joined: Tue Dec 29, 2009 1:28 amFollowed by: 7 members; Thanked: 135 times

by selango » Mon Aug 02, 2010 4:16 am

IMO this is not a GMAT question..

--Anand--

Like this post

winnerhere: Master | Next Rank: 500 Posts; Posts: 231; Joined: Thu Apr 12, 2007 2:45 amFollowed by: 1 member; Thanked: 5 times

by winnerhere » Mon Aug 02, 2010 7:20 pm

dont panic guys.This question was not taken from a GMAT source

Sorry if I had caused a confusion

Like this post

Post new topic Post Reply

• Page 1 of 1

GMAT Course Reviews

559 reviews

1168 reviews

431 reviews

359 reviews

147 reviews

5/5

5 Star (560 Reviews)

"Target Test Prep is the closest to the official version of the GMAT exam, about 99% accuracy in terms of the quality and quantity of information. The course has excellently created singular sets of focused lessons and tests for every possible topic that one could come across in the official GMAT exam."

"The TTP course maximizes the efficiency of the time you spend studying. It will take time and effort but I could almost guarantee that if you complete the course exactly as it is laid out you will get an amazing score. They also have a very responsive team willing to help with any questions you might have."

"TTP has two things that I think no other test prep company offers: A teaching approach that reinforces understanding and an attitude that will give you the mental preparedness needed to succeed on the test. TTP gives you a deep understanding of the concept you need to know while teaching you how to think."

Write a Review