Find all School-related info fast with the new School-Specific MBA Forum

It is currently 30 Aug 2014, 10:56

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.

Events & Promotions

Events & Promotions in June
Open Detailed Calendar

what is the remainder of 49^1000 divided by 23? 1) 9 2) 8 3)

  Question banks Downloads My Bookmarks Reviews Important topics  
Author Message
TAGS:
Current Student
avatar
Joined: 28 Dec 2004
Posts: 3405
Location: New York City
Schools: Wharton'11 HBS'12
Followers: 13

Kudos [?]: 158 [0], given: 2

GMAT Tests User
what is the remainder of 49^1000 divided by 23? 1) 9 2) 8 3) [#permalink] New post 22 Aug 2007, 12:25
what is the remainder of 49^1000 divided by 23?

1) 9
2) 8
3) 7
4) 6
5) 1
Senior Manager
Senior Manager
User avatar
Joined: 13 May 2007
Posts: 252
Followers: 1

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

GMAT Tests User
 [#permalink] New post 22 Aug 2007, 12:47
ok i calculated the answer as 8 but its too complex to be termed as "fastest" way :(
Manager
Manager
User avatar
Joined: 15 Aug 2007
Posts: 70
Followers: 2

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

 [#permalink] New post 22 Aug 2007, 13:08
empty_spaces wrote:
ok i calculated the answer as 8 but its too complex to be termed as "fastest" way :(

Yeah its 8... I know the method but its very long....

1. Refine it: 49 = 23*2+3. 3 is the remainder of 49 divided by 23 => 49^1000 has the same remainder, when divided by 23, as 3^1000!

2. Find the CYCLE:

Start with small powers of 3 and find remainders:

3^0 = 1. Remainder = 1.

3^1 = 3. Remainder = 3.

3^2 = 9. Remainder = 9.

3^3 = 27. Remainder = 4.

Then, you should find the remainder of 3^5 by 23. But that number is big... What to do? You should do the following: take previous remainder of 3^4 by 23 (=12), multiply it by 3, and get the new remainder! Which is, it is easy to see, 13!

To get a remainder of 3^6 by 23, you need to multiply previous remainder (=13) by 3 and get the new remainder: 39. This number is greater that 23. So, divide it by 23 again, and get the new remainder: 16!


3^4 = 81. Remainder = 12.

3^5 = 243. Remainder = 13.

3^6 = ...{something you can't calculate}. Remainder = 13*3 mod 23 = 16!

3^7 = ...{something you can't calculate}. Remainder = 16*3 mod 23 = 2!

3^8 = ...{something you can't calculate}. Remainder = 2*3 = 6!

3^9 = ...{something you can't calculate}. Remainder = 6*3 mod 23 = 18!

3^10 = ...{something you can't calculate}. Remainder = 18*3 mod 23 = 8!

3^11 = ...{something you can't calculate}. Remainder = 8*3 = 1!

So, 3^11 mod 23 = 1. Then, it is not surprising, 3^12 mod 23 = 3... and the CYCLE starts AGAIN.

What you need to do at this stage, is to find a minimum duration of CYCLE.

In our case, duration of CYCLE is 11 - 0 = 11.

3. Once you have found the PERIOD of the CYCLE, you can easily compute the remainder of 3^1000 mod 23. 1000 = 11{=PERIOD}*90 + 10. => the remainder of 1000 by PERIOD{=11} is 10! => 49^1000 mod 23 = 3^1000 mod 23 = 3^10 mod 23 = 8, which was previously calculated!
Senior Manager
Senior Manager
User avatar
Joined: 13 May 2007
Posts: 252
Followers: 1

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

GMAT Tests User
 [#permalink] New post 22 Aug 2007, 13:13
thats pretty much what i did..

whats the source of this question? unless there is a really clever trick to do this...one cannot solve this in under 4 mins .
VP
VP
avatar
Joined: 10 Jun 2007
Posts: 1467
Followers: 5

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

GMAT Tests User
Re: Remainder: quickest way...tough one [#permalink] New post 22 Aug 2007, 16:12
fresinha12 wrote:
what is the remainder of 49^1000 divided by 23?

1) 9
2) 8
3) 7
4) 6
5) 1


I am not sure if you will see something like this in GMAT either, but here it goes my fastest method...

49^1000 / 23, you know that 23*2=46; thus, use the remainder of 3 and replace 49 with 3, you get:
3^1000 / 23
Now, work out some numbers...you know that 3^5 = 81*3 = 243. If 243/23, you get remainder of 13 since 243-230 = 13. Plug that back in just like the one above, you get something like this:
((3^5)^200) / 23 => plug in => (13^200)/23 = ((13^2)^100)/23
You know that 13^2 = 26, so it will have remainder of 3 when divide by 26. Plug in back in the same way...
3^100 / 23
Keep using the same method, you get:
3^100 / 23 = ((3^5)^20)/23 => (13^20)/23 = ((13^2)^10)/23
=> (3^10) / 23 = ((3^5)^2) / 23 => (13^2) / 23 = 169/23
Find the remainder for the final number: 23*7 = 161
169-161 = 8
Current Student
avatar
Joined: 28 Dec 2004
Posts: 3405
Location: New York City
Schools: Wharton'11 HBS'12
Followers: 13

Kudos [?]: 158 [0], given: 2

GMAT Tests User
 [#permalink] New post 22 Aug 2007, 16:33
OA is 8 :)
CEO
CEO
User avatar
Joined: 21 Jan 2007
Posts: 2770
Location: New York City
Followers: 6

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

GMAT Tests User
 [#permalink] New post 26 Dec 2007, 12:26
this question is insane. i would just take 20 seconds and reasonably guess
Director
Director
User avatar
Joined: 08 Jun 2007
Posts: 583
Followers: 1

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

GMAT Tests User
 [#permalink] New post 26 Dec 2007, 12:34
chiya wrote:
empty_spaces wrote:
ok i calculated the answer as 8 but its too complex to be termed as "fastest" way :(

Yeah its 8... I know the method but its very long....

1. Refine it: 49 = 23*2+3. 3 is the remainder of 49 divided by 23 => 49^1000 has the same remainder, when divided by 23, as 3^1000!

2. Find the CYCLE:

Start with small powers of 3 and find remainders:

3^0 = 1. Remainder = 1.

3^1 = 3. Remainder = 3.

3^2 = 9. Remainder = 9.

3^3 = 27. Remainder = 4.

Then, you should find the remainder of 3^5 by 23. But that number is big... What to do? You should do the following: take previous remainder of 3^4 by 23 (=12), multiply it by 3, and get the new remainder! Which is, it is easy to see, 13!

To get a remainder of 3^6 by 23, you need to multiply previous remainder (=13) by 3 and get the new remainder: 39. This number is greater that 23. So, divide it by 23 again, and get the new remainder: 16!


3^4 = 81. Remainder = 12.

3^5 = 243. Remainder = 13.

3^6 = ...{something you can't calculate}. Remainder = 13*3 mod 23 = 16!

3^7 = ...{something you can't calculate}. Remainder = 16*3 mod 23 = 2!

3^8 = ...{something you can't calculate}. Remainder = 2*3 = 6!

3^9 = ...{something you can't calculate}. Remainder = 6*3 mod 23 = 18!

3^10 = ...{something you can't calculate}. Remainder = 18*3 mod 23 = 8!

3^11 = ...{something you can't calculate}. Remainder = 8*3 = 1!

So, 3^11 mod 23 = 1. Then, it is not surprising, 3^12 mod 23 = 3... and the CYCLE starts AGAIN.

What you need to do at this stage, is to find a minimum duration of CYCLE.

In our case, duration of CYCLE is 11 - 0 = 11.

3. Once you have found the PERIOD of the CYCLE, you can easily compute the remainder of 3^1000 mod 23. 1000 = 11{=PERIOD}*90 + 10. => the remainder of 1000 by PERIOD{=11} is 10! => 49^1000 mod 23 = 3^1000 mod 23 = 3^10 mod 23 = 8, which was previously calculated!


nice copy and paste.... :lol:
just kidding...
but yeah this is a lengthy approach...best would be make an educated guess.
Manager
Manager
User avatar
Joined: 11 Nov 2007
Posts: 62
Followers: 1

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

Re: Remainder: quickest way...tough one [#permalink] New post 11 Jan 2008, 01:21
Its a easy question actually.

Here is how I approached it:

9^2= 1
9^3 = 9
9^4= 1
9^5 =9
See the pattern? On the 1000th power, the last digit is a 1. What's the remainder of XXX1 divided by 23 ? 8
VP
VP
avatar
Joined: 22 Nov 2007
Posts: 1102
Followers: 6

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

GMAT Tests User
Re: Remainder: quickest way...tough one [#permalink] New post 11 Jan 2008, 06:29
fresinha12 wrote:
what is the remainder of 49^1000 divided by 23?

1) 9
2) 8
3) 7
4) 6
5) 1


7^2000/3.....7^2000 terminates in 7 (7,9,3,1,7....), 3*2=6; 7-6=1 OA is 5
Manager
Manager
User avatar
Joined: 01 Jan 2008
Posts: 227
Schools: Booth, Stern, Haas
Followers: 1

Kudos [?]: 44 [0], given: 2

GMAT Tests User
Re: Remainder: quickest way...tough one [#permalink] New post 11 Jan 2008, 07:10
marcodonzelli wrote:
fresinha12 wrote:
what is the remainder of 49^1000 divided by 23?

1) 9
2) 8
3) 7
4) 6
5) 1


7^2000/3.....7^2000 terminates in 7 (7,9,3,1,7....), 3*2=6; 7-6=1 OA is 5


don't follow your steps, could you explain? moreover isn't OA is 8?
VP
VP
avatar
Joined: 22 Nov 2007
Posts: 1102
Followers: 6

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

GMAT Tests User
Re: Remainder: quickest way...tough one [#permalink] New post 11 Jan 2008, 07:59
kazakhb wrote:
marcodonzelli wrote:
fresinha12 wrote:
what is the remainder of 49^1000 divided by 23?

1) 9
2) 8
3) 7
4) 6
5) 1


7^2000/3.....7^2000 terminates in 7 (7,9,3,1,7....), 3*2=6; 7-6=1 OA is 5


don't follow your steps, could you explain? moreover isn't OA is 8?


I'm sorry, I didn't read 23....OA is 8:

49^1000 is a number terminating in 1. since the are no common factor b/w 49^1000 and 23, we have a number terminating in 1 divided by a prime number (23). thus, the remainder would be 8....
Director
Director
User avatar
Joined: 12 Jul 2007
Posts: 867
Followers: 12

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

GMAT Tests User
Re: Remainder: quickest way...tough one [#permalink] New post 11 Jan 2008, 08:16
Quote:
we have a number terminating in 1 divided by a prime number (23). thus, the remainder would be 8....



can someone explain this last step in more detail? Up to the part where we know 49^1000 ends in 1, but not how we know that 49^1000/23 has a remainder of 8.
VP
VP
avatar
Joined: 22 Nov 2007
Posts: 1102
Followers: 6

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

GMAT Tests User
Re: Remainder: quickest way...tough one [#permalink] New post 11 Jan 2008, 12:15
eschn3am wrote:
Quote:
we have a number terminating in 1 divided by a prime number (23). thus, the remainder would be 8....



can someone explain this last step in more detail? Up to the part where we know 49^1000 ends in 1, but not how we know that 49^1000/23 has a remainder of 8.


my reasoning is: since we have 1 as unit digit, the remainder must end in 8, which actually means 8 and 18, not 28 because 28>23. since we don't have 18 as answer choice, we can say only 8...what do you think about that?


anyway 23*104=2392
7^4=2401
remainder is 9..am i going crazy????
Director
Director
User avatar
Joined: 12 Jul 2007
Posts: 867
Followers: 12

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

GMAT Tests User
Re: Remainder: quickest way...tough one [#permalink] New post 11 Jan 2008, 14:29
Quote:
since we have 1 as unit digit, the remainder must end in 8,


what rule is this? I'm not following the logic here.
VP
VP
avatar
Joined: 22 Nov 2007
Posts: 1102
Followers: 6

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

GMAT Tests User
Re: Remainder: quickest way...tough one [#permalink] New post 11 Jan 2008, 23:22
eschn3am wrote:
Quote:
since we have 1 as unit digit, the remainder must end in 8,


there is no logic. I'm trying to find one without doing long calculus!
Intern
Intern
avatar
Joined: 10 Jan 2008
Posts: 39
Followers: 0

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

Re: Remainder: quickest way...tough one [#permalink] New post 29 Feb 2008, 08:57
49^1000 = 7^1000 * 7^1000
Using the 7,9,3,1 repeat rule, we have X1 * X1 = Y1

If Y = any digit besides 3 or 0, the remainder is larger than any of the answer choices. (lets say that Y results after doing long division by 23)
If Y = 3 the remainder is 8
If Y = 0 the remainder is 1
This could be a quick 50/50 guess, but I think the 0 possibility can be eliminated.
A quick check, some number divisible by 23 (such as 230), with a 01 added at the end....23001 (since this would give a remainder of 1)
Could such a number occur from multiplying 7*7*7 etc. I'm not sure, but this one isn't divisible by 7, so my guess was 8 as the remainder.
Re: Remainder: quickest way...tough one   [#permalink] 29 Feb 2008, 08:57
    Similar topics Author Replies Last post
Similar
Topics:
8 What is the remainder when (1!)!^3 + (2!)^3 + (3!)^3 + … + ( langtuprovn2007 2 23 Jun 2014, 15:44
Experts publish their posts in the topic 1/2 + [(2/3 * 3/8)/4] - 9/16 = Walkabout 2 07 Dec 2012, 05:03
14 Experts publish their posts in the topic What is the remainder when (1!)^3+ (2!)^3 + (3!)^3 +.....(11 virtualanimosity 10 04 Nov 2009, 00:07
What is the remainder when k^2 is divided by 8? 1). When k apollo168 8 17 Aug 2006, 07:20
What is the remainder when k^2 is divided by 8? 1). When k gmat_crack 4 26 May 2006, 23:24
Display posts from previous: Sort by

what is the remainder of 49^1000 divided by 23? 1) 9 2) 8 3)

  Question banks Downloads My Bookmarks Reviews Important topics  


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

Powered by phpBB © phpBB Group and phpBB SEO

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®.