Which of the following must be subtracted from 2^526 so that the resul

Question

Which of the following must be subtracted from 2^526 so that the resulting integer will be a multiple of 3?

A. 1 
B. 2 
C. 3 
D. 5 
E. 6

chetan2u · Accepted Answer

Hi,
this is not correct..
 2^{11} or 2^{254312} will have ONLY 2 as prime factor

A simple way would be  2^1 =2  , which requires 1 to be added for it to be div by 3..
 2^2 = 4  requires 1 to be subtracted ..
and so on..
 basically an ODD power of 2 requires 1 to be added to the number to be div by 3..
and any EVEN power would require 1 to be subtracted.. 
here 256 is EVEN, so it requires 1 to be subtracted 
so  2^{256} - 1  is div by 3
ans A

ENGRTOMBA2018 · Answer

Your statement above (in red) is NOT correct.

Important point, 2^number where number >11 can not be a FACTOR of 3 but will be a MULTIPLE of 3.

2^12 is definitely NOT a multiple of 3 as 2^12 will only have 2s in it.

Coming back to the question,

2^1 leaves a remainder of 2 when divided by 3
2^2 leaves a remainder of 1 when divided by 3
2^3 leaves a remainder of 2 when divided by 3
2^4 leaves a remainder of 1 when divided by 3... etc. and the cyclicity continues.

Thus,  2^{526}  will leave a remainder of 1 when divided by 3. Thus you must subtract 1 from  2^{526}  to make it divisible by 3.

A is thus the correct answer.

Hope this helps.

stonecold · Answer

Here 2^(any power ≥ 11) is a factor of three.
Hence using the rule => Multiple - multiple is always a multiple
We must subtract a multiple of 3
I.e we must subtract 3
Smash that C for me.

I hope i am not missing anything

ncoppernoll · Answer

I may be missing something here, but are you certain that your power of 2 rule checks out? I tried 2^15 and others. Unless I'm missing something, I don't think this would give the correct answer.

stonecold · Answer

I made a HUGE error.!!!!!!!! What was i thinking...!!!!!!!! offcourse 2^anything can never be divisible by 3..!!! I think i need a break

Thanks chetan2 and Engr2012 Regards StoneCold

rahulkashyap · Answer

Anyway binomial expansion would help solve this? Basically upon opening the binomial expansion, everything but the last digit would be divisible by 3. (3-1)^n

Posted from my mobile device

stonecold · Answer

Hey  rahulkashyap 
Yes I think we can use that here 
2^526 = (3-1)^526 => expanding using (a-b)^n => all terms will have 3 but the last 
Expanding the same => 3^526 * .........(-1)^526 => 3p+1 for some integer p
hence the remainder will be 1

P.S => Thank you for reminding me that Binomial can be a Saviour on the GMAT find the remainder Question..!!

ENGRTOMBA2018 · Answer

Most, if not all, remainder questions in GMAT can be solved by cyclicity. So, yes, use Binomial theorem if you are comfortable with it but do not forget about cyclicity (I did not use Binomial Theorem but used cyclicity instead).

Abhishek009 · Answer

No need to go till the fourth power of 2 ; second power of 2 is sufficient

2^{526}  =  {2}^{2*128}

{2}^{2*128}  =  4^{128}

4/3 will produce 1 as remainder

1^128 = 1

Hence remainder will be 1

PS : Binomial Theorem is not in GMAT Syllabus , however if one is through with it , its his/her choice - Objective is to get the answer correct in whatever method you are confident with in least amount of time...

Abhishek

stonecold · Answer

Hey Just one doubt i have => when you say 4/3 gives one as the remainder ; you are essentially writing 4 as 3P+1 so (3p+1)^128 
Isn't that binomial ??
Clearly that isnt cyclicity

Regards
Stonecold

Abhishek009 · Answer

Hey Just one doubt i have => when you say 4/3 gives one as the remainder ; you are essentially writing 4 as 3P+1 so (3p+1)^128 
Isn't that binomial ??
Clearly that isnt cyclicity

Regards
Stonecold

{4^1} / 3 =4/3 remainder 1
{4^2} / 3 = 16/3 remainder 1
{4^3} / 3 = 64/3 remainder 1
{4^4} / 3 = 256/3 remainder 1

Actually the same remainder keeps repeating .....

Try with a diff no, say 2

{2^1}/3 = remainder 2
{2^2}/3 = remainder 1
{2^3}/3 = remainder 2
{2^4}/3 = remainder 1

Se there is a cyclic pattern....

Hope this helps , we are using this logic to solve the problem and/ or any other problem involving remainder.

PhilSad92 · Answer

The Answer is A) as a lot of people have written before me. But what I want to add about this question, is that if you don't have an approach on how to solve it, it is very easy to see that only option A) and B) could be true. If it would be C, well then the resulting integer would already be a multiple of 3. If it would be D), then it would also be true for B) since 5-2=3. The same counts for E) 6-3=3 which is C).

JSS16 · Answer

Just follow the pattern:

2^2 = 4 (-1 to be multiple of 3)
2^3 = 8 (-2 to be multiple of 3)
2^4 = 16 (-1 to be multiple of 3)
2^5 = 32 (-2 to be multiple of 3)

The pattern is subtracting 1 or 2. 2^256 is even, thus you must subtract 1 for a multiple of 3.

SchruteDwight · Answer

stonecold ,  chetan2u ,  Abhishek009

Thank you for the binomial method, indeed very helpful. I was just wondering what happens if the last term in the binomial is not even, e.g. if it would be xp-1, would the remainder then be x-1? Or can we only use the binomial method if the last term is positive (hence with even exponents)?

chetan2u · Answer

The xp-1 not understood. Please give some values ..

SchruteDwight · Answer

Thanks for the quick reply, so assuming the value would have been  4^{525}  and we want to know the remainder when divided by 3, we could then say  (4-1)^{525} , and the remainder would be (3-1)=2, is that correct? And can we do that in any such case?

chetan2u · Answer

If it is  4^{525} , we can write it as  (3+1)^{525} ... so the remainder will be  1^{525} , which is 1..
But If it is  2^{525} , we can write it as  (3-1)^{525} ... so the remainder will be  (-1)^{525} , which is -1. But the remainder cannot be negative, so remainder will be 3-1 or 2.

This would be the case even when  4^{525}  is divided by 5, we can write it as  (5-1)^{525} ... so the remainder will be  (-1)^{525} , which is -1. Thus the remainder here will be 5-1 or 4.

bumpbot · Answer

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.

Which of the following must be subtracted from 2^526 so that the resul

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

Which of the following must be subtracted from 2^526 so that the resul

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