Author 
Message 
TAGS:

Hide Tags

Intern
Joined: 10 Oct 2012
Posts: 8

What is the remainder when you divide 2^200 by 7?
[#permalink]
Show Tags
Updated on: 17 Oct 2012, 04:22
Question Stats:
58% (00:52) correct 42% (00:49) wrong based on 381 sessions
HideShow timer Statistics
What is the remainder when you divide 2^200 by 7? (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
Official Answer and Stats are available only to registered users. Register/ Login.
Originally posted by g3kr on 16 Oct 2012, 20:42.
Last edited by Bunuel on 17 Oct 2012, 04:22, edited 1 time in total.
Renamed the topic and edited the question.




Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 8288
Location: Pune, India

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 21:46
g3kr wrote: I am confused . Please help!
What is the remainder when you divide 2^200 by 7?
(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 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: http://www.veritasprep.com/blog/2011/05 ... ekinyou/)
_________________
Karishma Veritas Prep GMAT Instructor
Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >
GMAT selfstudy has never been more personalized or more fun. Try ORION Free!




Intern
Joined: 23 May 2012
Posts: 30

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 21:18
\(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.




Intern
Joined: 24 May 2012
Posts: 6
Concentration: Technology, Entrepreneurship

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 21:11
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.



Intern
Joined: 23 May 2012
Posts: 30

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 21:19



Director
Joined: 22 Mar 2011
Posts: 604
WE: Science (Education)

Re: Remainder problem.
[#permalink]
Show Tags
17 Oct 2012, 01:17
mindmind wrote: \(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. \((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\).
_________________
PhD in Applied Mathematics Love GMAT Quant questions and running.



Intern
Joined: 23 May 2012
Posts: 30

Re: Remainder problem.
[#permalink]
Show Tags
17 Oct 2012, 01:29
EvaJager wrote: mindmind wrote: \(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. \((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.



Director
Joined: 22 Mar 2011
Posts: 604
WE: Science (Education)

Re: Remainder problem.
[#permalink]
Show Tags
Updated on: 17 Oct 2012, 03:48
mindmind wrote: EvaJager wrote: mindmind wrote: \(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. \((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=1261=7\cdot{18}1=M71=M7+6\). \(5^{40}=(5^3)^{13}\cdot{5}=(M71)^{13}\cdot{5}=(M71)\cdot{5}=M75=M7+2\) and not \(M7+5\).
_________________
PhD in Applied Mathematics Love GMAT Quant questions and running.
Originally posted by EvaJager on 17 Oct 2012, 03:29.
Last edited by EvaJager on 17 Oct 2012, 03:48, edited 1 time in total.



Intern
Joined: 23 May 2012
Posts: 30

Re: Remainder problem.
[#permalink]
Show Tags
17 Oct 2012, 03:43
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=1261=7\cdot{18}1=M71=M7+6\). \(5^{40}=(5^3)^{13}\cdot{5}=(M71)^{13}\cdot{5}=(M71)\cdot{5}=M75=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.



Director
Joined: 22 Mar 2011
Posts: 604
WE: Science (Education)

Re: Remainder problem.
[#permalink]
Show Tags
17 Oct 2012, 04:01
mindmind wrote: 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=1261=7\cdot{18}1=M71=M7+6\). \(5^{40}=(5^3)^{13}\cdot{5}=(M71)^{13}\cdot{5}=(M71)\cdot{5}=M75=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.
_________________
PhD in Applied Mathematics Love GMAT Quant questions and running.



Intern
Joined: 23 May 2012
Posts: 30

Re: Remainder problem.
[#permalink]
Show Tags
17 Oct 2012, 04:09
EvaJager wrote: mindmind wrote: 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=1261=7\cdot{18}1=M71=M7+6\). \(5^{40}=(5^3)^{13}\cdot{5}=(M71)^{13}\cdot{5}=(M71)\cdot{5}=M75=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.[/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..



Intern
Joined: 11 Jul 2012
Posts: 41

Re: What is the remainder when you divide 2^200 by 7?
[#permalink]
Show Tags
26 Oct 2012, 11:34
Another approach is the Theorem of Remainder 2^200 = 4*(2^3)^66;7 = 2^3 1 Theorem of Remainder of f(X)/Xa is f(a) 2^200 = 4*f(X)/Xa X=2^3 a = 1 ==> Remainder of f(X)/Xa = 1 Remainder of 2^200 divided by7 is 4*1 = 4 Brother Karamazov



Director
Joined: 03 Aug 2012
Posts: 807
Concentration: General Management, General Management
GMAT 1: 630 Q47 V29 GMAT 2: 680 Q50 V32
GPA: 3.7
WE: Information Technology (Investment Banking)

Re: What is the remainder when you divide 2^200 by 7?
[#permalink]
Show Tags
08 Aug 2013, 23:39
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
_________________
Rgds, TGC! _____________________________________________________________________ I Assisted You => KUDOS Please _____________________________________________________________________________



Senior Manager
Joined: 10 Jul 2013
Posts: 315

Re: Remainder problem.
[#permalink]
Show Tags
09 Aug 2013, 02:56
VeritasPrepKarishma wrote: g3kr wrote: I am confused . Please help!
What is the remainder when you divide 2^200 by 7?
(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 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: http://www.veritasprep.com/blog/2011/05 ... ekinyou/) ... 2^200 = (2^3)^66 × 2^2 = (7+1)^66 × 4 1^66 × 4 = 4 (Answer) The taste of your own medicine ???????
_________________
Asif vai.....



Current Student
Joined: 12 Aug 2015
Posts: 2648

Re: What is the remainder when you divide 2^200 by 7?
[#permalink]
Show Tags
21 Mar 2016, 09:37



NonHuman User
Joined: 09 Sep 2013
Posts: 8157

Re: What is the remainder when you divide 2^200 by 7?
[#permalink]
Show Tags
10 Jul 2018, 10:29
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.
_________________
GMAT Books  GMAT Club Tests  Best Prices on GMAT Courses  GMAT Mobile App  Math Resources  Verbal Resources




Re: What is the remainder when you divide 2^200 by 7? &nbs
[#permalink]
10 Jul 2018, 10:29






