Bunuel wrote:
What is the remainder when 47^203 is divided by 7?
A. 1
B. 2
C. 3
D. 4
E. 5
This is an interesting problem. Here's my initial thinking:
- 47^203 is going to be a HUGE number. So, I can't do the calculation. On the GMAT, that means there must be a pattern.
- It says "divided by 7", which reminds me of the language that's usually used in units digits problems. However, to find the units digit of a number, you need the remainder when the number is divided by
10, not by 7. So, I'm thinking I shouldn't look at units digits here.
- Finally, 47 is a prime number. So, no matter what power I raise it to, it's not going to be divisible by anything except for 1, 47, and powers of 47. It's not going to be divisible by 7! The remainder definitely won't be 0...
---
I'm thinking I'll try to start by finding a multiple of 7 that's close to 47. 42 is 7*6, so that should work. Let's rewrite 47 as "7*6 + 5."
What is the remainder when (7*6 + 5)^203 is divided by 7?
That's still way too hard. Let's start with a simpler question and look for a pattern:
What is the remainder when (7*6 + 5)^2 is divided by 7?
Well, (7*6 + 5)^2 = (7*6)^2 + 2*(7*6)*(5) + (5)^2.
Since we're looking for the remainder when we divide by 7, we can ignore any multiples of 7, because they'll contribute 0 to the remainder. So, the question is really "What is the remainder when 5^2 is divided by 7?"
What is the remainder when 25 is divided by 7?
The answer would be 25 - 21 = 4. In other words, 47^2 = 7*something + 4.
Let's go from there, to 47^3. To do that, we take the result we got for 47^2, and multiply by 47.
47^3 = (7*something + 4)*47 = 7*something*47 + 4*47
The first part is a multiple of 7, so it contributes nothing to the remainder. Therefore, we only need to look at 4*47. To make it even simpler, we can remove some multiples of 7, since again, they'll contribute 0 to the remainder:
4*47 = 4*(42 + 5) = 4*42 + 4*5 = a multiple of 7 + 4*5 = a multiple of 7 + 20
To find the remainder, just find the remainder for 20, which is 20 - 14 = 6.
Here's the pattern so far:
47^1: remainder of 5
47^2: remainder of 4
47^3: remainder of 6.
Let's do the same thing to go from 47^3 to 47^4. However, I'm not going to multiply by 47 this time. I'm just going to multiply by 5, since as we saw above, if you write 47 as 42+5, you can totally ignore the 42 part when you calculate the remainder.
So, now I'm going to do 47^4 remainder = (7*something + 6)*(5) = 7*something*5 + 6*5. Calculate the remainder for 30, which is 30-28 = 2.
47^4: remainder of 2
Continuing this process, here's what we get:
47^5: remainder of 3
47^6: remainder of 1
47^7: remainder of 5
There's the pattern! 47^1 and 47^7 have the same remainder.47^8: remainder of 4
47^9: remainder of 6... etc. It should just keep repeating.
So, it repeats every 6 numbers. 47^1 will have the same remainder as 47^(1+6), and the same remainder as 47^(1+6+6), etc.
We just need to figure out where in this pattern the number 203 is.
203 is 5 greater than 198, which is a multiple of 6. Multiples of 6 will have a remainder of 1 in this pattern. A number that's 1 greater than a multiple of 6 will have a remainder of 5. A number that's 2 greater will have a remainder of 4, and so on. Continuing in the pattern, 47^203 should give a remainder of 3, and the answer should be
C.
To calculate this at home may work but I don't think this is applicable in a test situation and approximately 2 mins of time.
... 5*5 / 7 R:1
till the cycle repeat's itself. That's how I would have done that.