what is the remainder of 49^1000 divided by 23? 1) 9 2) 8 3) : Quant Question Archive [LOCKED]
Check GMAT Club Decision Tracker for the Latest School Decision Releases http://gmatclub.com/AppTrack

 It is currently 17 Jan 2017, 12:45

### 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

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

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

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

Author Message
Current Student
Joined: 28 Dec 2004
Posts: 3384
Location: New York City
Schools: Wharton'11 HBS'12
Followers: 15

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

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

### Show Tags

22 Aug 2007, 12:25
This topic is locked. If you want to discuss this question please re-post it in the respective forum.

what is the remainder of 49^1000 divided by 23?

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

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

### Show Tags

22 Aug 2007, 12:47
ok i calculated the answer as 8 but its too complex to be termed as "fastest" way
Manager
Joined: 15 Aug 2007
Posts: 70
Followers: 2

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

### Show Tags

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:

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
Joined: 13 May 2007
Posts: 250
Followers: 2

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

### Show Tags

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
Joined: 10 Jun 2007
Posts: 1459
Followers: 7

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Joined: 28 Dec 2004
Posts: 3384
Location: New York City
Schools: Wharton'11 HBS'12
Followers: 15

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

### Show Tags

22 Aug 2007, 16:33
OA is 8
CEO
Joined: 21 Jan 2007
Posts: 2756
Location: New York City
Followers: 11

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

### Show Tags

26 Dec 2007, 12:26
this question is insane. i would just take 20 seconds and reasonably guess
Director
Joined: 08 Jun 2007
Posts: 583
Followers: 2

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

### Show Tags

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:

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....
just kidding...
but yeah this is a lengthy approach...best would be make an educated guess.
Manager
Joined: 11 Nov 2007
Posts: 60
Followers: 1

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Joined: 22 Nov 2007
Posts: 1092
Followers: 8

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Joined: 01 Jan 2008
Posts: 227
Schools: Booth, Stern, Haas
Followers: 1

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Joined: 22 Nov 2007
Posts: 1092
Followers: 8

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Joined: 12 Jul 2007
Posts: 862
Followers: 15

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Joined: 22 Nov 2007
Posts: 1092
Followers: 8

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Joined: 12 Jul 2007
Posts: 862
Followers: 15

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Joined: 22 Nov 2007
Posts: 1092
Followers: 8

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Joined: 10 Jan 2008
Posts: 39
Followers: 0

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

Re: Remainder: quickest way...tough one [#permalink]

### Show Tags

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
Display posts from previous: Sort by