Jul 20 07:00 AM PDT  09:00 AM PDT Attend this webinar and master GMAT SC in 10 days by learning how meaning and logic can help you tackle 700+ level SC questions with ease. Jul 21 07:00 AM PDT  09:00 AM PDT Attend this webinar to learn a structured approach to solve 700+ Number Properties question in less than 2 minutes Jul 26 08:00 AM PDT  09:00 AM PDT The Competition Continues  Game of Timers is a teambased competition based on solving GMAT questions to win epic prizes! Starting July 1st, compete to win prep materials while studying for GMAT! Registration is Open! Ends July 26th Jul 27 07:00 AM PDT  09:00 AM PDT Learn reading strategies that can help even nonvoracious reader to master GMAT RC
Author 
Message 
TAGS:

Hide Tags

Intern
Joined: 10 Oct 2012
Posts: 8

What is the remainder when 8^643/132?
[#permalink]
Show Tags
Updated on: 17 Oct 2012, 04:29
Question Stats:
52% (02:37) correct 48% (02:49) wrong based on 215 sessions
HideShow timer Statistics
What is the remainder when 8^643/132? A. 116 B. 117 C. 120 D. 109 8^643 = (2^3)^643=2^1929
2^x has a cyclicity of 3 , 1929 is divisible by 3..
how to proceed please help..
Official Answer and Stats are available only to registered users. Register/ Login.
Originally posted by g3kr on 16 Oct 2012, 14:20.
Last edited by Bunuel on 17 Oct 2012, 04:29, edited 1 time in total.
Renamed the topic and edited the question.




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

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 21:33
mindmind wrote: Even I had the same ambiguity.. But just to be sure.. there wont be both options in the answer : 29 & 116 ? Both 29 and 116 can be in the options because the answer is only 116. In fact, it is quite likely that both will be there since if there is a way to trip you, GMAT will not let it go. You can choose to cancel off terms in the numerator and denominator or you can choose to keep them as it is. In either case, answer will be 116. \(\frac{8^{643}}{132} = \frac{8*8^{642}}{132}\) We get \(2*\frac{8^{642}}{33} = 2*\frac{2^{1926}}{33}\) Now, notice that \(2^5 = 32\) is 1 less than 33 so we use it. Why? (Check out this post: http://www.veritasprep.com/blog/2011/05 ... ekinyou/ ) 1926 is 1 more than a multiple of 5 so we keep aside a 2. \(2*2*\frac{2^{1925}}{33} = 4*\frac{32^{385}}{33}\) We get \(4*\frac{(33  1)^{385}}{33}\) Using binomial theorem (discussed in the link given above), we see that the remainder is 4 i.e. 29. Recall that we cancelled off 4 from the numerator in the beginning. We need to multiply it back so actual remainder is 29*4 = 116
_________________
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 >




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

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 15:51
g3kr wrote: Please help to solve.
what is the remainder when 8^643/132?
8^643 = (2^3)^643=2^1929
2^x has a cyclicity of 3 , 1929 is divisible by 3..
how to proceed please help.. \(8^{643}=(2^3)^{643}=2^{1929}\) \(132=2^2\cdot{3}\cdot{11}\) \(33=32+1=2^5+1\) \(2^{1927}=(2^5)^{385}\cdot2^2=(331)^{385}\cdot{4}=(M331)\cdot{4}=M334=M3333+29=M33+29\). (\(M33\) designates multiple of \(33\).) \(2^{1929}=2^{1927}\cdot2^2=(M33+29)\cdot{4}=M132+29\cdot{4}=M132+116\). \(M33+29\) means \(33n+29\), for some integer \(n\). Then \((M33+29)\cdot{4}=132n+29\cdot{4}=M132+116\). Hence, the remainder is 116.
_________________
PhD in Applied Mathematics Love GMAT Quant questions and running.




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

Re: Remainder problem.
[#permalink]
Show Tags
Updated on: 16 Oct 2012, 15:39
g3kr wrote: Please help to solve.
what is the remainder when 8^643/132?
8^643 = (2^3)^643=2^1929
2^x has a cyclicity of 3 , 1929 is divisible by 3..
how to proceed please help.. \(8^{643}=(2^3)^{643}=2^{1929}\) \(33=32+1=2^5+1\) \(2^{1929}=(2^5)^{385}\cdot2^4=(331)^{385}\cdot{16}=(M331)\cdot{16}=M3316=M3333+17=M33+17\). (\(M33\) designates multiple of \(33\).) Hence, the remainder is \(17\).
_________________
PhD in Applied Mathematics Love GMAT Quant questions and running.
Originally posted by EvaJager on 16 Oct 2012, 15:32.
Last edited by EvaJager on 16 Oct 2012, 15:39, edited 1 time in total.



Intern
Joined: 10 Oct 2012
Posts: 8

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 15:38
EvaJager wrote: g3kr wrote: Please help to solve.
what is the remainder when 8^643/132?
8^643 = (2^3)^643=2^1929
2^x has a cyclicity of 3 , 1929 is divisible by 3..
how to proceed please help.. \(8^{643}=(2^3)^{643}=2^{1929}\) \(132=2^2\cdot{3}\cdot{11}\) \(\frac{2^{1929}}{2^2\cdot{3}\cdot{11}}=\frac{2^{1927}}{3\cdot{11}}\) So, we have to find the remainder when \(2^{1927}\) is divided by \(33\). \(33=32+1=2^5+1\) \(2^{1927}=(2^5)^{385}\cdot2^2=(331)^{385}\cdot{4}=(M331)\cdot{4}=M334=M3333+29=M33+29\). (\(M33\) designates multiple of \(33\).) Hence, the remainder is 29. Thanks EvaJager. The options were a. 116 b. 117 c. 120 d. 109 116 is highlighed as the answer. How to arrive at this?



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

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 15:41
g3kr wrote: EvaJager wrote: g3kr wrote: Please help to solve.
what is the remainder when 8^643/132?
8^643 = (2^3)^643=2^1929
2^x has a cyclicity of 3 , 1929 is divisible by 3..
how to proceed please help.. \(8^{643}=(2^3)^{643}=2^{1929}\) \(132=2^2\cdot{3}\cdot{11}\) \(\frac{2^{1929}}{2^2\cdot{3}\cdot{11}}=\frac{2^{1927}}{3\cdot{11}}\) So, we have to find the remainder when \(2^{1927}\) is divided by \(33\). \(33=32+1=2^5+1\) \(2^{1927}=(2^5)^{385}\cdot2^2=(331)^{385}\cdot{4}=(M331)\cdot{4}=M334=M3333+29=M33+29\). (\(M33\) designates multiple of \(33\).) Hence, the remainder is 29. Thanks EvaJager. The options were a. 116 b. 117 c. 120 d. 109 116 is highlighed as the answer. How to arrive at this? My previous posts are not correct...
_________________
PhD in Applied Mathematics Love GMAT Quant questions and running.



Intern
Joined: 10 Oct 2012
Posts: 8

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 16:54
EvaJager wrote: g3kr wrote: Please help to solve.
what is the remainder when 8^643/132?
8^643 = (2^3)^643=2^1929
2^x has a cyclicity of 3 , 1929 is divisible by 3..
how to proceed please help.. \(8^{643}=(2^3)^{643}=2^{1929}\) \(132=2^2\cdot{3}\cdot{11}\) \(33=32+1=2^5+1\) \(2^{1927}=(2^5)^{385}\cdot2^2=(331)^{385}\cdot{4}=(M331)\cdot{4}=M334=M3333+29=M33+29\). (\(M33\) designates multiple of \(33\).) \(2^{1929}=2^{1927}\cdot2^2=(M33+29)\cdot{4}=M132+29\cdot{4}=M132+116\). \(M33+29\) means \(33n+29\), for some integer \(n\). Then \((M33+29)\cdot{4}=132n+29\cdot{4}=M132+116\). Hence, the remainder is 116. What is wrong if i cancel out 2^2 in the numerator and divide by 33 . I still have to get the same reminder right?



Director
Status: Done with formalities.. and back..
Joined: 15 Sep 2012
Posts: 583
Location: India
Concentration: Strategy, General Management
Schools: Olin  Wash U  Class of 2015
WE: Information Technology (Computer Software)

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 18:51
g3kr wrote: EvaJager wrote: g3kr wrote: Please help to solve.
what is the remainder when 8^643/132?
8^643 = (2^3)^643=2^1929
2^x has a cyclicity of 3 , 1929 is divisible by 3..
how to proceed please help.. \(8^{643}=(2^3)^{643}=2^{1929}\) \(132=2^2\cdot{3}\cdot{11}\) \(33=32+1=2^5+1\) \(2^{1927}=(2^5)^{385}\cdot2^2=(331)^{385}\cdot{4}=(M331)\cdot{4}=M334=M3333+29=M33+29\). (\(M33\) designates multiple of \(33\).) \(2^{1929}=2^{1927}\cdot2^2=(M33+29)\cdot{4}=M132+29\cdot{4}=M132+116\). \(M33+29\) means \(33n+29\), for some integer \(n\). Then \((M33+29)\cdot{4}=132n+29\cdot{4}=M132+116\). Hence, the remainder is 116. What is wrong if i cancel out 2^2 in the numerator and divide by 33 . I still have to get the same reminder right? Hi g3kr, Both of the last 2 solutions fetching 29 and 116 are correct processwise, but for a logical mistake in former. Consider the case, 16/10 will have a remainder of 6, but its not same as 8/5 which has a remainder of 3 only. The difference? notice that for any y/x remainder can not be greater than x, hence if you have factored out a number from numerator and denominator, you have reduced remainder by that times. In our example of 16/10: if we make it 8/5 by dividing each term by 2 and get 3 as remainder. we should multiply result by 2 to get correct ans 6. hence, once you arrived in first solution (M33+29) you should remember to multiply it by 4, the one which was factored out earlier. Or better dont factor out and cancel a term in a remainder problem. Hope it helps.
_________________



Intern
Joined: 23 May 2012
Posts: 28

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 20:39
What is wrong if i cancel out 2^2 in the numerator and divide by 33 . I still have to get the same reminder right?[/quote]
Hi g3kr,
Both of the last 2 solutions fetching 29 and 116 are correct processwise, but for a logical mistake in former.
Consider the case, 16/10 will have a remainder of 6, but its not same as 8/5 which has a remainder of 3 only.
The difference? notice that for any y/x remainder can not be greater than x, hence if you have factored out a number from numerator and denominator, you have reduced remainder by that times. In our example of 16/10: if we make it 8/5 by dividing each term by 2 and get 3 as remainder. we should multiply result by 2 to get correct ans 6.
hence, once you arrived in first solution (M33+29)
you should remember to multiply it by 4, the one which was factored out earlier. Or better dont factor out and cancel a term in a remainder problem.
Hope it helps.[/quote]
Thanks,
Even I had the same ambiguity.. But just to be sure.. there wont be both options in the answer : 29 & 116 ?



Director
Status: Done with formalities.. and back..
Joined: 15 Sep 2012
Posts: 583
Location: India
Concentration: Strategy, General Management
Schools: Olin  Wash U  Class of 2015
WE: Information Technology (Computer Software)

Re: Remainder problem.
[#permalink]
Show Tags
16 Oct 2012, 21:45
mindmind wrote: What is wrong if i cancel out 2^2 in the numerator and divide by 33 . I still have to get the same reminder right?
Hi g3kr,
Both of the last 2 solutions fetching 29 and 116 are correct processwise, but for a logical mistake in former.
Consider the case, 16/10 will have a remainder of 6, but its not same as 8/5 which has a remainder of 3 only.
The difference? notice that for any y/x remainder can not be greater than x, hence if you have factored out a number from numerator and denominator, you have reduced remainder by that times. In our example of 16/10: if we make it 8/5 by dividing each term by 2 and get 3 as remainder. we should multiply result by 2 to get correct ans 6.
hence, once you arrived in first solution (M33+29)
you should remember to multiply it by 4, the one which was factored out earlier. Or better dont factor out and cancel a term in a remainder problem.
Hope it helps.
Thanks,
Even I had the same ambiguity.. But just to be sure.. there wont be both options in the answer : 29 & 116 ? Hi mindmind (too many minds :D), Exactly what I explained with example of 16/10 and 8/5. if i ask you remainder of 16/10 and give u option of 6 and 3, will you be confused? I dont think so If u factor out a number, the "fraction" remains same but "remainder" does not. please reread the post. Also this is why it is important not to factor out in remainder problem. Also try to check one more way of understanding it: a remainder is shown as below: if n = qm +r then kn = kqm +kr where Kn is a multiple of n and km is multiple of m. But this changes remainder from r to kr. Hope it is clear..
_________________



Senior Manager
Joined: 13 Oct 2016
Posts: 363
GPA: 3.98

What is the remainder when 8^643/132?
[#permalink]
Show Tags
01 Dec 2016, 07:39
g3kr wrote: What is the remainder when 8^643/132? A. 116 B. 117 C. 120 D. 109 8^643 = (2^3)^643=2^1929
2^x has a cyclicity of 3 , 1929 is divisible by 3..
how to proceed please help.. We can solve this question very quickly if we apply Euler’s theorem. \(132 = 2^2*3*11\) We can't apply theorem yet, because 8 and 132 are not coprime. \(\frac{8^{642}*2^3}{2^2*33} = \frac{8^{642}*2}{33}\) \(Ɵ(33) = 33 * \frac{2}{3} * \frac{10}{11} = 20\) Hence: \(8^{20} = 1 (mod 33)\) \(\frac{8^{640}*8^2*2}{33} = \frac{(8^{20})^{32}*64*2}{33} = \frac{1 * (2)*2}{33} = 4 (mod 33) = 29 mod (33)\) Now we multiply by cancelled factor \(4\) \(29*4 (mod 33*4) = 116 (mod 132)\) Our remainder is \(116\). Answer A.



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

Re: What is the remainder when 8^643/132?
[#permalink]
Show Tags
12 Mar 2019, 04:57
VeritasKarishma wrote: mindmind wrote: Even I had the same ambiguity.. But just to be sure.. there wont be both options in the answer : 29 & 116 ? Both 29 and 116 can be in the options because the answer is only 116. In fact, it is quite likely that both will be there since if there is a way to trip you, GMAT will not let it go. You can choose to cancel off terms in the numerator and denominator or you can choose to keep them as it is. In either case, answer will be 116. \(\frac{8^{643}}{132} = \frac{8*8^{642}}{132}\) We get \(2*\frac{8^{642}}{33} = 2*\frac{2^{1926}}{33}\) Now, notice that \(2^5 = 32\) is 1 less than 33 so we use it. Why? (Check out this post: http://www.veritasprep.com/blog/2011/05 ... ekinyou/ ) 1926 is 1 more than a multiple of 5 so we keep aside a 2. \(2*2*\frac{2^{1925}}{33} = 4*\frac{32^{385}}{33}\) We get \(4*\frac{(33  1)^{385}}{33}\) Using binomial theorem (discussed in the link given above), we see that the remainder is 4 i.e. 29. Recall that we cancelled off 4 from the numerator in the beginning. We need to multiply it back so actual remainder is 29*4 = 116 Responding to a pm: Quote: As per the solution =>
We get 4∗(33−1)385 ______________ 33
Using binomial theorem (discussed in the link given above), we see that the remainder is 4 i.e. 29.
Recall that we cancelled off 4 from the numerator in the beginning. We need to multiply it back so actual remainder is 29*4 = 116
But why 4 is again multiplied with 29? 4 was already considered in the binomial expression above. So answer should be 29 right ? What is the remainder when 12 is divided by 8? 12/8 quotient 1 and remainder 4. But when we divide both numerator and denominator by 4, we get 3/2. What is the remainder when 3 is divided by 2? It is 1. It is not the same as the remainder when 12 is divided by 8. To get the actual remainder, you need to multiply 1 by 4 back to get 4 as remainder.
_________________
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 >



Intern
Joined: 27 Sep 2017
Posts: 5

Re: What is the remainder when 8^643/132?
[#permalink]
Show Tags
12 Mar 2019, 08:42
we can rewrite 8^643 as 8^640 * 8 * 8 * 8, or 8^640 * 512. So as we get to this point we can rewrite the problem the following way: (8^640 * 512) / 132. From here we just need 512 to divide on 132: 512/132 = 132 * 3 + 116. the latter one will be our remainder.




Re: What is the remainder when 8^643/132?
[#permalink]
12 Mar 2019, 08:42






