What is the remainder when you divide 2^200 by 7?

Question

(A) 1
(B) 2
(C) 3
(D) 4
(E) 5

my approach :

2^x has a cyclicity of 4 
Therefore, Rem(200/4) = 0

Rem(2^0/7) =1

Am i missing something here?

OA is D

KarishmaB · Accepted Answer

I think you are getting confused between cyclicity of last digit and cyclicity of remainders. 2^1 = 2 2^2 = 4 2^3 = 8 2^4 = 16 2^5 = 32 2^6 = 64 If you see, the last digits are 2, 4, 8, 6 i.e. cyclicity of 4. On the other hand, 2^1/7 Rem = 2 2^2/7 Rem = 4 2^3/7 Rem = 1 2^4/7 Rem = 2 2^5 / 7 Rem = 4 2^6/7 Rem = 1 Here the cyclicity is 3. 2^{198} will give a remainder of 1. 2^{200} gives a remainder of 4. Or, you can easily use binomial theorem here. \frac{2^{200}}{7} = 2*2*\frac{2^{198}}{7} = 4*\frac{8^{66}}{7} = 4*\frac{(7 + 1)^{66}}{7} Remainder must be 4. (Check out this link: https://www.gmatclub.com/forum/veritas-prep-resource-links-no-longer-available-399979.html#/2011/0 ... ek-in-you/)

mindmind · Answer

2^{200} = (2^{5})^{40} 32 =28 +4 = (M7+4)^{40} ; M7 is a multiple of 7 = M7+4 so the remainder is 4. Hope it helps. You can find a similar sum here https://gmatclub.com/forum/find-the-rem ... 40784.html

lajulajay · Answer

Actually the cyclicity is 3:

(2^0)/7 = 0 R 1
(2^1)/7 = 0 R 2
(2^2)/7 = 0 R 4
(2^3)/7 = 1 R 1
(2^4)/7 = 2 R 2
(2^5)/7 = 4 R 4
...

The pattern is such that the remainder is 4 for every third one and we know there are 201 numbers between 0 and 200. Since 201 is a multiple of 3, D is in fact correct.

EvaJager · Answer

(M7+4)^{40}=M7+4^{40}  then you have to find the remainder of  4^{40}  when divided by 7.

Instead of taking  32 = 28 +4 , look for a power of 2 which gives a remainder of 1 when divided by 7.
The smallest one is  8 = 7 + 1 .

Therefore,  2^{200}=(2^3)^{66}\cdot{2^2}=8^{66}\cdot{4}=(7+1)^{66}\cdot{4}=(M7+1)\cdot4=M7+4 .

mindmind · Answer

Please help me understand better :

The remainder of 4^40 would be same as that of 4 . 
 Is my approach wrong? Can you provide similar examples, where it is not.

EvaJager · Answer

In this case,  4^{40}  is a  M7+4  :  \,\,4^{40}=2^{80}  and  80=M3+2  (the cycle is 3, because  2^{3}=8=M7+1 ). 
 4^{40}=2^{80}=(2^3)^{26}\cdot{2^2}=(M7+1)\cdot{4}=M7+4 .
Or -  4^3=64=M7+1 , therefore  4^{40}=(4^3)^{13}\cdot{4}=(M7+1)^{13}\cdot{4}=(M7+1)\cdot{4}=M7+4 .

Consider for example  5^{40} :  5=7\cdot{0}+5=M7+5  and  5^3=125=126-1=7\cdot{18}-1=M7-1=M7+6 .
 5^{40}=(5^3)^{13}\cdot{5}=(M7-1)^{13}\cdot{5}=(M7-1)\cdot{5}=M7-5=M7+2  and not  M7+5 .

mindmind · Answer

Please help me understand better :

The remainder of 4^40 would be same as that of 4 . 
 Is my approach wrong? Can you provide similar examples, where it is not.

In this case,  4^{40}  is a  M7+4  :  \,\,4^{40}=2^{80}  and  80=M3+2  (the cycle is 3, because  2^{3}=8=M7+1 ). 
 4^{40}=2^{80}=(2^3)^{26}\cdot{2^2}=(M7+1)\cdot{4}=M7+4 .

Consider for example  5^{40} :  5=7\cdot{0}+5=M7+5  and  5^3=125=126-1=7\cdot{18}-1=M7-1=M7+6 .
 5^{40}=(5^3)^{13}\cdot{5}=(M7-1)^{13}\cdot{5}=(M7-1)\cdot{5}=M7-5=M7+2  and not  M7+5 .

Yes, Agreed
So I should consider : Something near to Remainder 1

Any Trend where, (number or prime )^n divided by (other no, prime) gives the same remainder as the original no. or prime
eg : 4^40 divided by 7 give a remainder of 4.

EvaJager · Answer

In this case,  4^{40}  is a  M7+4  :  \,\,4^{40}=2^{80}  and  80=M3+2  (the cycle is 3, because  2^{3}=8=M7+1 ). 
 4^{40}=2^{80}=(2^3)^{26}\cdot{2^2}=(M7+1)\cdot{4}=M7+4 .

Consider for example  5^{40} :  5=7\cdot{0}+5=M7+5  and  5^3=125=126-1=7\cdot{18}-1=M7-1=M7+6 .
 5^{40}=(5^3)^{13}\cdot{5}=(M7-1)^{13}\cdot{5}=(M7-1)\cdot{5}=M7-5=M7+2  and not  M7+5 .

Yes, Agreed
So I should consider : Something near to Remainder 1

Any Trend where, (number or prime )^n divided by (other no, prime) gives the same remainder as the original no. or prime
eg : 4^40 divided by 7 give a remainder of 4.

I am not sure what you mean here:
 Any Trend where, (number or prime )^n divided by (other no, prime) gives the same remainder as the original no. or prime
eg : 4^40 divided by 7 give a remainder of 4.

3^4=81=11\cdot{7}+4 .  7  is prime, but the remainder is neither  3 , nor a prime.

rishab0507 · Answer

VeritasKarishma : why this question can't be solved with cyclicity approach, here is similar question thread i am copying, and is solved by cylicity. why e need to bring remainder cylicity. https://gmatclub.com/forum/what-is-the- ... l#p2066643

KarishmaB · Answer

Cyclicity tells you the units digit of exponential expressions. Now think about this - if you know the units digit of a number, can you say what the remainder is upon division by say 7? e.g. What is the remainder when 792947 is divided by 7? Would you say the remainder here is 0? It is not. The remainder depends on what the actual number is, not just the units digit. Only in case of division by 2, 5 or 10 does the units digit give us the remainder. Check out these two posts: https://www.gmatclub.com/forum/veritas-prep-resource-links-no-longer-available-399979.html#/2015/1 ... questions/ https://www.gmatclub.com/forum/veritas-prep-resource-links-no-longer-available-399979.html#/2015/1 ... ns-part-2/

egmat · Answer

This is a classic  remainder cyclicity  problem. The trick is to find the repeating pattern of remainders.

Let's divide powers of  2  by  7  and track the remainders:

-  2 ^ 1  =  2  → remainder  2 
-  2 ^ 2  =  4  → remainder  4 
-  2 ^ 3  =  8  → remainder  1 
-  2 ^ 4  =  16  → remainder  2 
-  2 ^ 5  =  32  → remainder  4 
-  2 ^ 6  =  64  → remainder  1

See the pattern? The remainders repeat every  3  powers:  2 ,  4 ,  1 ,  2 ,  4 ,  1 , ...

Now the question becomes: where does  2 ^ 200  fall in this cycle of  3 ?

Step 1:  Divide  200  by  3 :
 200  ÷  3  =  66  with a remainder of  2

This remainder of  2  tells us that  2 ^ 200  lands on the same position in the cycle as  2 ^ 2 . And the remainder of  2 ^ 2  divided by  7  is  4 .

So the remainder when  2 ^ 200  is divided by  7  is  4 .

Answer: D

Key principle:  For any remainder problem with large exponents, always find the  cyclicity pattern  first. Divide the exponent by the cycle length, and use that remainder to locate your position in the cycle.

Common mistake:  Students might try dividing  200  by  7  instead of finding the cycle length of  3 . The cycle length comes from the pattern of remainders, not from the divisor itself.

Adit_ · Answer

12 seconds.
2^3 mod 7 = 1
2^198 mod 7= 1
2^200 mod 7 = 2^2 mod 7 = 4

Answer:  Option D

What is the remainder when you divide 2^200 by 7?

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

What is the remainder when you divide 2^200 by 7?

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