It is currently 21 Oct 2017, 02:06

Close

GMAT Club Daily Prep

Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track
Your Progress

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.

Close

Request Expert Reply

Confirm Cancel

Events & Promotions

Events & Promotions in June
Open Detailed Calendar

What is the remainder when 8^643/132?

  new topic post reply Question banks Downloads My Bookmarks Reviews Important topics  
Author Message
TAGS:

Hide Tags

1 KUDOS received
Intern
Intern
avatar
Joined: 10 Oct 2012
Posts: 10

Kudos [?]: 28 [1], given: 13

What is the remainder when 8^643/132? [#permalink]

Show Tags

New post 16 Oct 2012, 14:20
1
This post received
KUDOS
25
This post was
BOOKMARKED
00:00
A
B
C
D
E

Difficulty:

  85% (hard)

Question Stats:

56% (02:06) correct 44% (02:19) wrong based on 242 sessions

HideShow timer Statistics

What is the remainder when 8^643/132?

A. 116
B. 117
C. 120
D. 109

[Reveal] Spoiler:
8^643 = (2^3)^643=2^1929

2^x has a cyclicity of 3 , 1929 is divisible by 3..

how to proceed please help..
[Reveal] Spoiler: OA

Last edited by Bunuel on 17 Oct 2012, 04:29, edited 1 time in total.
Renamed the topic and edited the question.

Kudos [?]: 28 [1], given: 13

1 KUDOS received
Director
Director
User avatar
Joined: 22 Mar 2011
Posts: 610

Kudos [?]: 1058 [1], given: 43

WE: Science (Education)
Re: Remainder problem. [#permalink]

Show Tags

New post 16 Oct 2012, 15:32
1
This post received
KUDOS
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=(33-1)^{385}\cdot{16}=(M33-1)\cdot{16}=M33-16=M33-33+17=M33+17\).
(\(M33\) designates multiple of \(33\).)

Hence, the remainder is \(17\).
_________________

PhD in Applied Mathematics
Love GMAT Quant questions and running.


Last edited by EvaJager on 16 Oct 2012, 15:39, edited 1 time in total.

Kudos [?]: 1058 [1], given: 43

Intern
Intern
avatar
Joined: 10 Oct 2012
Posts: 10

Kudos [?]: 28 [0], given: 13

Re: Remainder problem. [#permalink]

Show Tags

New post 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=(33-1)^{385}\cdot{4}=(M33-1)\cdot{4}=M33-4=M33-33+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?

Kudos [?]: 28 [0], given: 13

Director
Director
User avatar
Joined: 22 Mar 2011
Posts: 610

Kudos [?]: 1058 [0], given: 43

WE: Science (Education)
Re: Remainder problem. [#permalink]

Show Tags

New post 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=(33-1)^{385}\cdot{4}=(M33-1)\cdot{4}=M33-4=M33-33+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.

Kudos [?]: 1058 [0], given: 43

5 KUDOS received
Director
Director
User avatar
Joined: 22 Mar 2011
Posts: 610

Kudos [?]: 1058 [5], given: 43

WE: Science (Education)
Re: Remainder problem. [#permalink]

Show Tags

New post 16 Oct 2012, 15:51
5
This post received
KUDOS
4
This post was
BOOKMARKED
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=(33-1)^{385}\cdot{4}=(M33-1)\cdot{4}=M33-4=M33-33+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.

Kudos [?]: 1058 [5], given: 43

Intern
Intern
avatar
Joined: 10 Oct 2012
Posts: 10

Kudos [?]: 28 [0], given: 13

Re: Remainder problem. [#permalink]

Show Tags

New post 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=(33-1)^{385}\cdot{4}=(M33-1)\cdot{4}=M33-4=M33-33+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?

Kudos [?]: 28 [0], given: 13

Intern
Intern
avatar
Joined: 10 Oct 2012
Posts: 10

Kudos [?]: 28 [0], given: 13

Re: Remainder problem. [#permalink]

Show Tags

New post 16 Oct 2012, 17:22
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=(33-1)^{385}\cdot{4}=(M33-1)\cdot{4}=M33-4=M33-33+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.



Is there some other method of doing it?

Kudos [?]: 28 [0], given: 13

1 KUDOS received
Director
Director
User avatar
Status: Done with formalities.. and back..
Joined: 15 Sep 2012
Posts: 636

Kudos [?]: 653 [1], given: 23

Location: India
Concentration: Strategy, General Management
Schools: Olin - Wash U - Class of 2015
WE: Information Technology (Computer Software)
GMAT ToolKit User Premium Member Reviews Badge
Re: Remainder problem. [#permalink]

Show Tags

New post 16 Oct 2012, 18:51
1
This post received
KUDOS
1
This post was
BOOKMARKED
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=(33-1)^{385}\cdot{4}=(M33-1)\cdot{4}=M33-4=M33-33+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.
_________________

Lets Kudos!!! ;-)
Black Friday Debrief

Kudos [?]: 653 [1], given: 23

Intern
Intern
avatar
Joined: 10 Oct 2012
Posts: 10

Kudos [?]: 28 [0], given: 13

Re: Remainder problem. [#permalink]

Show Tags

New post 16 Oct 2012, 19:06
Thank you so much :)

Kudos [?]: 28 [0], given: 13

Director
Director
User avatar
Status: Done with formalities.. and back..
Joined: 15 Sep 2012
Posts: 636

Kudos [?]: 653 [0], given: 23

Location: India
Concentration: Strategy, General Management
Schools: Olin - Wash U - Class of 2015
WE: Information Technology (Computer Software)
GMAT ToolKit User Premium Member Reviews Badge
Re: Remainder problem. [#permalink]

Show Tags

New post 16 Oct 2012, 19:26
g3kr wrote:
Thank you so much :)

You are welcome. :)
_________________

Lets Kudos!!! ;-)
Black Friday Debrief

Kudos [?]: 653 [0], given: 23

Intern
Intern
avatar
Joined: 23 May 2012
Posts: 31

Kudos [?]: 43 [0], given: 11

Re: Remainder problem. [#permalink]

Show Tags

New post 16 Oct 2012, 20:39
1
This post was
BOOKMARKED
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 ?

Kudos [?]: 43 [0], given: 11

Expert Post
6 KUDOS received
Veritas Prep GMAT Instructor
User avatar
G
Joined: 16 Oct 2010
Posts: 7676

Kudos [?]: 17374 [6], given: 232

Location: Pune, India
Re: Remainder problem. [#permalink]

Show Tags

New post 16 Oct 2012, 21:33
6
This post received
KUDOS
Expert's post
8
This post was
BOOKMARKED
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 ... ek-in-you/ )
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
My Blog

Get started with Veritas Prep GMAT On Demand for $199

Veritas Prep Reviews

Kudos [?]: 17374 [6], given: 232

1 KUDOS received
Director
Director
User avatar
Status: Done with formalities.. and back..
Joined: 15 Sep 2012
Posts: 636

Kudos [?]: 653 [1], given: 23

Location: India
Concentration: Strategy, General Management
Schools: Olin - Wash U - Class of 2015
WE: Information Technology (Computer Software)
GMAT ToolKit User Premium Member Reviews Badge
Re: Remainder problem. [#permalink]

Show Tags

New post 16 Oct 2012, 21:45
1
This post received
KUDOS
1
This post was
BOOKMARKED
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 re-read 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.. ;)
_________________

Lets Kudos!!! ;-)
Black Friday Debrief

Kudos [?]: 653 [1], given: 23

GMAT Club Legend
GMAT Club Legend
User avatar
Joined: 09 Sep 2013
Posts: 16611

Kudos [?]: 273 [0], given: 0

Premium Member
Re: What is the remainder when 8^643/132? [#permalink]

Show Tags

New post 12 Feb 2014, 04: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

Kudos [?]: 273 [0], given: 0

Intern
Intern
avatar
Joined: 10 Jun 2014
Posts: 26

Kudos [?]: 8 [0], given: 4

GMAT ToolKit User
Re: What is the remainder when 8^643/132? [#permalink]

Show Tags

New post 27 Oct 2014, 12:26
Is there a trick to this question?

Kudos [?]: 8 [0], given: 4

GMAT Club Legend
GMAT Club Legend
User avatar
Joined: 09 Sep 2013
Posts: 16611

Kudos [?]: 273 [0], given: 0

Premium Member
Re: What is the remainder when 8^643/132? [#permalink]

Show Tags

New post 13 Feb 2016, 06:49
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

Kudos [?]: 273 [0], given: 0

Manager
Manager
avatar
Joined: 01 Mar 2014
Posts: 138

Kudos [?]: 10 [0], given: 616

Schools: Tepper '18
Re: What is the remainder when 8^643/132? [#permalink]

Show Tags

New post 18 Mar 2016, 00:06
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=(33-1)^{385}\cdot{4}=(M33-1)\cdot{4}=M33-4=M33-33+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.


I got the correct answer but took me very long to do it, which would be tricky in exam conditions. is this really a gmat question??

Kudos [?]: 10 [0], given: 616

Senior Manager
Senior Manager
avatar
B
Joined: 13 Oct 2016
Posts: 367

Kudos [?]: 395 [0], given: 40

GPA: 3.98
What is the remainder when 8^643/132? [#permalink]

Show Tags

New post 01 Dec 2016, 07:39
g3kr wrote:
What is the remainder when 8^643/132?

A. 116
B. 117
C. 120
D. 109

[Reveal] Spoiler:
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 co-prime.

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

Kudos [?]: 395 [0], given: 40

What is the remainder when 8^643/132?   [#permalink] 01 Dec 2016, 07:39
Display posts from previous: Sort by

What is the remainder when 8^643/132?

  new topic post reply Question banks Downloads My Bookmarks Reviews Important topics  


GMAT Club MBA Forum Home| About| Terms and Conditions| GMAT Club Rules| Contact| Sitemap

Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne

Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.