|
Author |
Message |
|
TAGS:
|
|
|
Intern
Joined: 10 Oct 2012
Posts: 10
Followers: 0
Kudos [?]:
1
[0], given: 13
|
What is the remainder when you divide 2^200 by 7? [#permalink]
 16 Oct 2012, 20:42
Question Stats:
45% (01:50) correct
54% (00:40) wrong based on 2 sessions
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
Last edited by Bunuel on 17 Oct 2012, 04:22, edited 1 time in total.
Renamed the topic and edited the question.
|
|
|
|
|
|
|
Intern
Joined: 23 May 2012
Posts: 33
Followers: 0
Kudos [?]:
5
[3] , given: 11
|
Re: Remainder problem. [#permalink]
16 Oct 2012, 21:18
3
This post received
KUDOS
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.
|
|
|
|
|
|
Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 3113
Location: Pune, India
Followers: 572
Kudos [?]:
2015
[1] , given: 92
|
Re: Remainder problem. [#permalink]
16 Oct 2012, 21:46
1
This post received
KUDOS
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 ... ek-in-you/)
_________________
Karishma
Veritas Prep | GMAT Instructor
My Blog
Save 10% on Veritas Prep GMAT Courses And Admissions Consulting
Enroll now. Pay later. Take advantage of Veritas Prep's flexible payment plan options.
Veritas Prep Reviews
|
|
|
|
|
|
Director
Joined: 22 Mar 2011
Posts: 608
WE: Science (Education)
Followers: 43
Kudos [?]:
267
[1] , given: 43
|
Re: Remainder problem. [#permalink]
17 Oct 2012, 03:29
1
This post received
KUDOS
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=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.
_________________
PhD in Applied Mathematics
Love GMAT Quant questions and running.
Last edited by EvaJager on 17 Oct 2012, 03:48, edited 1 time in total.
|
|
|
|
|
|
Intern
Joined: 24 May 2012
Posts: 2
Concentration: Technology, Entrepreneurship
Followers: 0
Kudos [?]:
0
[0], given: 1
|
Re: Remainder problem. [#permalink]
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: 33
Followers: 0
Kudos [?]:
5
[0], given: 11
|
Re: Remainder problem. [#permalink]
16 Oct 2012, 21:19
|
|
|
|
|
|
Director
Joined: 22 Mar 2011
Posts: 608
WE: Science (Education)
Followers: 43
Kudos [?]:
267
[0], given: 43
|
Re: Remainder problem. [#permalink]
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: 33
Followers: 0
Kudos [?]:
5
[0], given: 11
|
Re: Remainder problem. [#permalink]
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.
|
|
|
|
|
|
Intern
Joined: 23 May 2012
Posts: 33
Followers: 0
Kudos [?]:
5
[0], given: 11
|
Re: Remainder problem. [#permalink]
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=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.
|
|
|
|
|
|
Director
Joined: 22 Mar 2011
Posts: 608
WE: Science (Education)
Followers: 43
Kudos [?]:
267
[0], given: 43
|
Re: Remainder problem. [#permalink]
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=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.
_________________
PhD in Applied Mathematics
Love GMAT Quant questions and running.
|
|
|
|
|
|
Intern
Joined: 23 May 2012
Posts: 33
Followers: 0
Kudos [?]:
5
[0], given: 11
|
Re: Remainder problem. [#permalink]
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=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.[/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: 46
Followers: 0
Kudos [?]:
0
[0], given: 0
|
Re: What is the remainder when you divide 2^200 by 7? [#permalink]
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)/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
|
|
|
|
|
|
|
Re: What is the remainder when you divide 2^200 by 7?
[#permalink]
26 Oct 2012, 11:34
|
|
|
|
|
|
|
|
|
|
|
close
