What is the remainder when 47^203 is divided by 7?

Cyclicity of \(7 (47) \ is \ 4, so \ \frac{203}{4} = remainder \ 3\)

\(47^3 = 7*7*7 = 49*7 = ...3\)

\(= \frac{3}{7}=3 \ is \ the \ remainder\)

The answer is \(C\)

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.

CONCEPT: Remainders.

-Try to reach a 1 or a –1 by grouping the individual remainders.

SOLUTION: Every 47 on dividing by 7 leaves a remainder of (-2).

Thus,203 47’s will leave 203 (-2)s as remainders.

So, 47^203 / 7 -> (-2)^203 / 7

Group three 2s to obtain a 8. On dividing this by 7 you have a 1 as remainder. (-1) shall be multiplied
at the end as you are grouping (-2) s.
67 such groups would be created.
Thus (-2)^203/7--> (-1) x (8^67 ) x (-2) x (-2)
-->(-4)/7 = +3 as remainder.

Hope this helps. Keep studying and growing.

All the Best!

Devmitra Sen

Solution:

Notice that if it’s 49^203, the remainder is 0 since 49 is a multiple of 7. Since the base is actually 47 and 47 - 49 = -2, we can think of this as (-2)^203 or -(2^203). Now, 2^203 = (2^3)^67 x 2^2 and 2^3 = 8, which has a remainder of 1 when divided by 7. Therefore, we can consider 2^203 as 1^67 x 2^2 = 4. Of course, we have mentioned it’s actually -(2^203), so it should be -4 and the remainder should be -4 + 7 = 3.

(Note: Recall that whenever the “remainder” is negative (and its absolute value is less than the divisor), add the divisor to make it positive and that will be the actual remainder.)

Alternate Solution:

The remainder when 47 is divided by 7 is 5, so we can determine the remainder when 5^203 is divided by 7.

Let’s calculate the remainders obtained by dividing the first few powers of 5 by 7:

5^1 = 5
5^2 = 4 (because 25/7 = 3R4)
5^3 = 5^2 * 5^1 = 4 * 5 = 20 = 6 (because 20/7 = 2R6)
5^4 = 5^3 * 5^1 = 6 * 5 = 30 = 2 (because 30/7 = 4R2)
5^5 = 5^4 * 5^1 = 2 * 5 = 10 = 3 (because 10/7 = 1R3)
5^6 = 5^5 * 5^1 = 3 * 5 = 15 = 1 (because 15/7 = 2R1)

Notice that 5^203 can be rewritten as (5^198)*(5^5) = (5^6)^33 * (5^5). Since 5^6 = 1 and 5^5 = 3, the remainder when 5^203 is divided by 7 is 1^33 * 3 = 3.

Answer: 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.
Took me at least 4-5 minutes with this method

Cycle:

47/7 R:5

... 5*5 / 7 R:1

5*5*5 / 7 R:6

till the cycle repeat's itself. That's how I would have done that.

Asked: What is the remainder when 47^203 is divided by 7?

47 = 49-2
Remainder when 47^203 = (49-2)^203 is divided by 7 = (-2)^203 = 8^67*(-1)^67 (-2)^2 = -(7+1)^67* 4 = -4 = 7 -4 = 3

IMO C

Hello, Can you help me out with this approach. I have a few questions -
1. Will this not work if I start by saying Every 47 will leave a remainder of 5 as opposed to (-2)?
2. I understand the part up to the grouping of 2s and that we have 67 such groups. But why are we ignoring that part and only considering the portion that we could not group?

Thanks in advance for your help!

Chetan, can you explain why you broke down things the way you did after 2^202? I don't follow that. What's a general methodology here?

For problems like this, can't we just find the unit digit of the last number in the integer? 7 in this case?

Most numbers are beautiful for the patterns they make. Although this method IS shown, I am not sure it is clear, so I would like to add a visual.
To be clear, we are using the exponents of 7^x b/c that is what will tell us our final digit.
As with many numbers, 7^exp makes a cycle that can be used to answer questions just like this.
The 4th number in the pattern is generally the one with a remainder of zero.
7 has 4 ending digits in the cycle. For this reason, we will divide the exponent we are given (203) by 4. This will tell us how many times we needed to go around the cycle. Frankly, we don't care about that. Next, the remainder will show how many places we went past the end of the cycle. That will be the last digit of the number in question. It also shows the remainder--how many items of the cycle you "pass" before landing on the remainder.

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.