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

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.

You can find a similar sum here

find-the-remainder-when-the-sum-of-140784.html#p1131797

\((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\).

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\).
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\).

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.[/quote]

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\).[/quote]

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.

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\).[/quote]

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.[/quote]

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.

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.[/quote]

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.[/quote]


Yes.. I was referring to 3.. and not the remainder 4..
But I got your point.. thanks..

Another approach is the Theorem of Remainder
2^200 = 4*(2^3)^66;7 = 2^3 -1
Theorem of Remainder of f(X)/X-a is f(a)
2^200 = 4*f(X)/X-a X=2^3 a = 1 ==> Remainder of f(X)/X-a = 1
Remainder of 2^200 divided by7 is 4*1 = 4
Brother Karamazov

Easiest and the smallest possible solution ever:

Keep your mind open while dealing with such question.It is not that you have to be math pro for that.

REM(2^200/7) [ REM(x/y) means remainder when x is divided by y]

We know that : Rem when 8 is divided by 7 is '1'.

Also by powers of 2 we can reach to 8.Using this concept:

[ (2^3)^198 * 2^2] /7

[ (8)^198 * 2^2] /7

Since REM(8/7) =1

We are left with REM(4/7) = 4

...
2^200 = (2^3)^66 × 2^2 = (7+1)^66 × 4
1^66 × 4 = 4 (Answer)

The taste of your own medicine ???????

We can use the binomial approach here => 4*2^198 => 4* (7P+1) => 7Q+4 => remainder => 4

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

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/

thanks, It was indeed a good learning. I never paid attention i was solving only 2,5, 10 divisor problems .I think for other divisors i need to follow split method, not cyclicity to find remainders

2^1, when divided by 7, will give the remainder 2.
2^2, when divided by 7, will give the remainder 4.
2^3, when divided by 7, will give the remainder 1.
2^4, when divided by 7, will give the remainder 2.
2^5, when divided by 7, will give the remainder 4.

Thus, we can see that in a cycle of 3, every remainder repeats itself.

Thus, 2^(3x) will give a remainder of 1 when divided by 7 for all the values of x(natural number).

For x = 66, 3x = 198.
Thus, 2^198, the remainder will be 1.
Now for 2^200, the remainder will be 4.

Thus, the correct option is D.

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

2ˆ3 = 8
2ˆ200 = 2ˆ{3*66 + 2} = 8ˆ66 * 4

Remainder when 2ˆ200 is divided by 7
= Remainder when 8ˆ66*4 is divided by 7
= Remainder when 4 is divided by 7 since remainder when 8ˆ66 is divided by 7 is 1.
=4

IMO D