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

Question

A. 1
B. 2
C. 3
D. 4
E. 5

chetan2u · Accepted Answer

uchihaitachi , It will not be correct to check on units digit when finding remainder on division by 7. Units digit will help while finding remainders on division by 5 and 10..

Here  47^{203}=(49-2)^{203} , All terms on expansion except  (-2)^{203}  will be divisible by 7....
 (-2)^{203}  = (-2)^{202}*(-2)=(2)^{202}*(-2)=(2^3)^{\frac{201}{3}}*2*(-2)=(8)^{67}*2*(-2)=(7+1)^{67}*2*(-2)=1^{67}*(-4)=-4  
 Remainders cannot be negative, so remainder  =7-4=3

You can also find pattern by finding remainders when successive powers are divided..  
47^1 leaves 5, 47^2 leaves 4 and so on.. pattern is 5,4,6,2,3,1,5,4,...Thus, the pattern repeats after every 6th number..
So convert 203 in 6k form.. 203=6k+5..
So remainder will be 5th in the pattern 5, 4, 6, 2, 3, 1, hence 3

C

Kinshook · Answer

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

ccooley · Answer

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 .

chrtpmdr · Answer

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.

MHIKER · Answer

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

CrackverbalGMAT · Answer

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

All the Best! Devmitra Sen

MBAB123 · Answer

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!

ScottTargetTestPrep · Answer

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

CEdward · Answer

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?

Sushen · Answer

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.

BrushMyQuant · Answer

We need to find the remainder when  47^{203}  is divided by 7? 
 
 We solve these problems by using Binomial Theorem, where we split the number into two parts, one part is a multiple of the divisor(7) and a big number, other part is a small number.

=>  47^{203}  =  (49-2)^{203}

Watch this video to  MASTER BINOMIAL Theorem

Now, if we use Binomial Theorem to expand this then all the terms except the last term will be a multiple of 7
=> All terms except the last term will give remainder of 0 when divided by 7 
=> Problem is reduced to what is the remainder when the last term (i.e. 203C203 * 49^0 * (-2)^203) is divided by 7
=> Remainder of 2^68 is divided by 7

To solve this problem we need to find the cycle of remainder of power of 2 when divided by 7

Remainder of  2^1  (=2) by 7 = 2
Remainder of  2^2  (=4) by 7 = 4 
Remainder of  2^3  (=8) by 7 = 1
Remainder of  2^4  (=16) by 7 =   2   
Remainder of  2^5  (=32) by 7 =   4  
Remainder of  2^6  (=64) by 7 =   1

=> Cycle is 3

Remainder of 203 by 3 = 2
=> Remainder of  2^{203}  by 7 = Remainder of  2^{2}  by 7 = 4
  => Remainder of - 2^{203}  by 7 = -4
=> Remainder = -4 + 7 = 3

So,  Answer will be C 
Hope it Helps!

Watch following video to MASTER Remainders by 2, 3, 5, 9, 10 and Binomial Theorem

https://www.youtube.com/watch?v=h1HTEhmUb1w

eega · Answer

47^203 can be written as (49-2)^203
Expanding using binomial expansion we'll get (-2)^203 as reminder
taking (-2)^2 outside we get 4*(-2)^201 which will give (-8)^67 => (-1)^67 
which when multiplied with 4 gives -4 
7-4 = 3 is the reminder (Option C)

luisdicampo · Answer

Concept: Modular Arithmetic & Cyclicity  
We need to find the remainder of  \frac{47^{203}}{7} .

Step 1: Simplify the Base  
First, find the remainder of the base 47 when divided by 7.
 47 = 7 	imes 6 + 5 .
The remainder is 5.
So, the problem simplifies to finding the remainder of  5^{203}  divided by 7.

Step 2: Find the Pattern (Cyclicity)  
To avoid calculating huge numbers, we multiply the  previous remainder  by 5 to get the next remainder:

1.  5^1 ightarrow 5  (Rem:  5 )
2.  5^2 ightarrow 25 \div 7  (Rem:  4 )
3.  5^3 ightarrow  take prev rem  4 	imes 5 = 20 .  20 \div 7  (Rem:  6 )
4.  5^4 ightarrow  take prev rem  6 	imes 5 = 30 .  30 \div 7  (Rem:  2 )
5.  5^5 ightarrow  take prev rem  2 	imes 5 = 10 .  10 \div 7  (Rem:  3 )
6.  5^6 ightarrow  take prev rem  3 	imes 5 = 15 .  15 \div 7  (Rem:  1 )

Since we hit remainder 1, the cycle repeats every  6  powers.
Cycle:  5, 4, 6, 2, 3, 1 .

Step 3: Reduce the Exponent  
Divide the exponent (203) by the cycle length (6):
 203 = 6 	imes 33 + 5 .
The remainder is 5.
This means  5^{203}  corresponds to the 5th term in our cycle.

Step 4: Match to Pattern  
The 5th remainder in our sequence is  3 .

Answer:  C

Jodedol · Answer

Now we need to find the unit digit of 7^3 which is 3 as 7^3 = 343. The remainder becomes 3.

How'd you go from 7^3=343 to the conclusion that the remainder is 3

Bunuel · Answer

That solution was not precise, so I removed it. Please refer to the other solutions in the thread.

Adit_ · Answer

47^6 mod 7 = 1
47^204 mod 7 = 1.
Therefore some value when multipled by 47 gives a remainder of 1.
47 mod 7 = 5
Hence 5*x mod 7 = 1.
From option 3 fits perfectly.

Answer:  Option C

egmat · Answer

Hi Jodedol,

Great question — your confusion is totally justified because that step is actually  NOT  valid in general.

Finding the unit digit of a number does  NOT  tell you the remainder when dividing by  7 . Those are two completely different things.

For example, the number  43  has a unit digit of  3 , but  43  divided by  7  gives a remainder of  1 , not  3 . So  unit digit ≠ remainder when dividing by 7 .

In this problem, the fact that the unit digit of  47 ^ 203  is  3  AND the remainder when dividing by  7  is also  3  is just a  coincidence .

Here's the correct approach:

Step 1:   47  divided by  7  gives remainder  5 . So  47 ^ 203  mod  7  =  5 ^ 203  mod  7 .

Step 2:  Find the  cycle of remainders  when powers of  5  are divided by  7 :
-  5 ^ 1  =  5  → remainder  5 
-  5 ^ 2  =  25  → remainder  4 
-  5 ^ 3  =  125  → remainder  6 
-  5 ^ 4  → remainder  2 
-  5 ^ 5  → remainder  3 
-  5 ^ 6  → remainder  1  (cycle restarts!)

The cycle length is  6 .

Step 3:   203  =  6  ×  33  +  5 , so  5 ^ 203  has the same remainder as  5 ^ 5 , which is  3 .

Answer: C (3)

Key principle:  Unit digit tricks only work for divisibility by  10  (or  2 , or  5 ). For dividing by  7 , you must track the actual  remainder cycle .

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

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

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

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards