remainder

[demoskopico]

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

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

at a glance I say 8 because 49^1000 is a number terminating in 1 ... but simply multiplying I say 9 because:

23*104=2392
49*49=2401

2401-2392=9

moreover:

31-23=remainder 8
41-23=remainder 18
51-23 gives us a remainder of 5
61-23 gives us a remainder of 15
71-23 gives us a remainder of 2
81-23 gives us a remainder of 12
91, a remainder of 22
101 a remainder of 9

so possible OA are 8 and 9. more specifically it is 9 when the multiple of 23 terminates in 3 and 8 when it terminates in 1...anyway...the answer I have had from whom posted this question is 8 and I believe is 9...

any help???? any quick method...help!!!

[JohnB]

Hi Demoskopico,

This problem is rather challenging. Unfortunately, we can't work just with the ones digit, or even the ones and tens digits, to predict the remainder. (To see this, notice that the remainder for 131 divided by 23 is 16, while the remainder for 231 divided by 23 is 1.)

We need some more general way to characterize the remainder of 49^1000 divided by 23. The key fact that can help us here comes from what's called modular arithmetic, or the arithmetic of remainders. The result of dividing the product of two numbers obeys the following rule, where s mod t is the remainder when s is divided by t:

a*b mod c = [(a mod c) * (b mod c)] mod c. In other words, when we multiply the remainders of the two individual numbers and then find the remainder when that product is divided by c, it's the same as the remainder when the original product is divided by c.

EX. 12*12 mod 5 = [(12 mod 5) * (12 mod 5)] mod 5 = 4 mod 5 = 4.

(Or, the remainder when 144 is divided by 5 is 4. This is also the remainder when 2 (the remainder when 12 is divided by 5) times 2 (same) is divided by 5.)

If you didn't know this rule (& now you do!), you might think about it this way:

Consider the example 12*12/5 again. We could rewrite this as [(10 + 2)*12]/5, and then distribute: (10*12 + 2*12)/5 = (10*12)/5 + (2*12)/5. The first part of this final expression is divisible by 5, so it won't contribute to the remainder; only the second part will. Now we can use similar reasoning to separate the second 12 into 10 and 2. In the end, the remainder will be determined only by a fraction that looks like: (2 * 2) /5 = 4/5, so the remainder is 4.

This post is already quite long. I'm going to start a new post showing how to apply this to the problem.

[JohnB]

We're trying to find the remainder when 49^1000 is divided by 23. From the ideas in the previous post, we know that this will be the same as the remainder when (the remainder of 49 divided by 23)^1000 is divided by 23. The remainder of 49 divided by 23 is 3. So we want the remainder of 3^1000 divided by 23.

That may not seem like much of an improvement. But we can rewrite 3^1000 as 81^250 (since 81 = 3^4). Now let's use the same logic as before--since the remainder when 81 is divided by 23 is 12, we are looking for the remainder when 12^250 is divided by 23.

We'll repeat these steps until we get down to manageable numbers:
12^250 = 144^125
The remainder when 144 is divided by 23 is 6.
6^125 = 7776^25 (since 7776 = 6^5).
The remainder when 7776 is divided by 23 is 2.
2^25 = 32^5
The remainder when 32 is divided by 23 is 9.
9^5 = 59,049.

The remainder when 59,049 is divided by 23 is 8. So the answer is 8.

[demoskopico]

I see it works ....is there a much faster metthod???I think I won't have the necessary time in te gmat...

moreover:

EX. 12*12 mod 5 = [(12 mod 5) * (12 mod 5)] mod 5 = 4 mod 5 = 4.

I have a question: this equation is: 2*2 mod 5...and this is ok

anyway why 4 mod 5 = 4?

4/5= 0,8

please help me! moreover, do you happen to have exercises like that with which I can exercise?

[kevin]

I see it works ....is there a much faster metthod???I think I won't have the necessary time in te gmat...

moreover:

EX. 12*12 mod 5 = [(12 mod 5) * (12 mod 5)] mod 5 = 4 mod 5 = 4.

I have a question: this equation is: 2*2 mod 5...and this is ok

anyway why 4 mod 5 = 4?

4/5= 0,8

please help me! moreover, do you happen to have exercises like that with which I can exercise?

Remember that when 76 is divided by 7, the quotient is 10 and the reaminder is 6 (76-7(10))

When 4 is divided by 5, the quotient is 0 and the remainder is 4.

In general , when positive integer m is divided by positive integer k and k > m, the quotient is 0 and the remainder is m. i.e. k mod m = k

[demoskopico]

Remember that when 76 is divided by 7, the quotient is 10 and the reaminder is 6 (76-7(10))

When 4 is divided by 5, the quotient is 0 and the remainder is 4.

In general , when positive integer m is divided by positive integer k and k > m, the quotient is 0 and the remainder is m. i.e. k mod m = k


could you solve me the problem 49^1000 / 23 with modular arithmetic? i think that,altough it is a good method, it is hard to apply in this case...maybe the distribution method is better...