This is a lot easier if you know some advanced math. I can't see any way a GMAT test-taker could be expected to answer this question.Carlo75 wrote:what is the remainder of 49^1000 divided by 23?
1) 9
2) 8
3) 7
4) 6
5) 1
please explanations ...
In any case, the answer is 8, but that's only something I can find by knowing a few things you won't need on the test- modular arithmetic and group theory. First, 3 is "congruent to" 49 when you're talking about division by 23 because 3 is 46 = 2*23 away from 49. This means that, when dealing with multiplication, addition or subtraction, 3 is effectively the same as 49 if you're only concerned about finding remainders. This means we only need to worry about 3^1000 here, and not 49^1000; we'll get the same answer either way. I'll use this 'congruence' property throughout the following.
In addition, and here's where we get very, very far from GMAT-required knowledge, if you have an integer x, and a prime p, the remainder will always be 1 when you divide x^(p-1) by p, as long as x is not divisible by p.
[actually, this can be kind of interesting. Try it with p=5; if you divide 2^4 = 16, 3^4 = 81 or 4^4 = 256 (or any other integer which is not a multiple of 5, raised to the power 4) by 5, you'll see the remainder is 1 in each case. If you want to try some others, try dividing 2^6 or 3^6 by 7, and you'll again find the remainder is 1. This is true in general, as long as you're dividing by a prime.]
So:
3^1000 = 3^10 * (3^22)^45
Now (3^22)^45 will give a remainder of 1 when divided by 23; we only need to look at 3^10. 3^10 = (27^3) * 3, which is congruent to 3*(4^3), which is congruent to 3*18 = 2*23 + 8; that is, the remainder will be 8 when you divide 49^1000 by 23.
Trust me, you do not need to know this for the GMAT!
