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.

Thank you for using the timer!
We noticed you are actually not timing your practice. Click the START button first next time you use the timer.
There are many benefits to timing your practice, including:

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!

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!

Re: Remainder: quickest way...tough one [#permalink]
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

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!

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.

Re: Remainder: quickest way...tough one [#permalink]
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....

Re: Remainder: quickest way...tough one [#permalink]
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.

Re: Remainder: quickest way...tough one [#permalink]
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????

Re: Remainder: quickest way...tough one [#permalink]
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.

gmatclubot

Re: Remainder: quickest way...tough one
[#permalink]
29 Feb 2008, 08:57