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
Remainder
This topic has expert replies

 Master  Next Rank: 500 Posts
 Posts: 231
 Joined: 12 Apr 2007
 Thanked: 5 times
 Followed by:1 members
 nithi_mystics
 Senior  Next Rank: 100 Posts
 Posts: 55
 Joined: 07 Sep 2009
 Location: California
 Thanked: 4 times

 Master  Next Rank: 500 Posts
 Posts: 161
 Joined: 05 Apr 2010
 Location: Mumbai
 Thanked: 37 times
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 (x1), 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]
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 (x1), 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
4GMAT, Dadar(W) & Ghatkopar(W), Mumbai
GMAT/MBA Expert
 Rahul@gurome
 GMAT Instructor
 Posts: 1179
 Joined: 11 Apr 2010
 Location: Milpitas, CA
 Thanked: 447 times
 Followed by:88 members
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.
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 201112  will stay active as time permits
18005664043 (USA)
+9199201 32411 (India)
Quant Expert
Gurome, Inc.
https://www.GuroMe.com
On MBA sabbatical (at ISB) for 201112  will stay active as time permits
18005664043 (USA)
+9199201 32411 (India)

 Master  Next Rank: 500 Posts
 Posts: 231
 Joined: 12 Apr 2007
 Thanked: 5 times
 Followed by:1 members
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.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]
Thanks for your help friend

 Master  Next Rank: 500 Posts
 Posts: 231
 Joined: 12 Apr 2007
 Thanked: 5 times
 Followed by:1 members
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,
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,
 pradeepkaushal9518
 Legendary Member
 Posts: 1309
 Joined: 17 Mar 2010
 Thanked: 33 times
 Followed by:5 members

 Master  Next Rank: 500 Posts
 Posts: 231
 Joined: 12 Apr 2007
 Thanked: 5 times
 Followed by:1 members
dont panic guys.This question was not taken from a GMAT source
Sorry if I had caused a confusion
Sorry if I had caused a confusion