A Tricky Question on Negative Remainders

Question

https://d3scmz9sa6n2x2.cloudfront.net/blog/wp-content/uploads/2010/11/quarter-wit-150x150.jpg 
Today, we will discuss the question we left you with  last week . It involves a lot of different concepts – remainder on division by 5, cyclicity and negative remainders. Since we did not get any replies with the solution, we are assuming that it turned out to be a little hard.

It actually is a little harder than your standard GMAT questions but the point is that it can be easily solved using all concepts relevant to GMAT. Hence it certainly makes sense to understand how to solve it.

Question: What is the remainder when 3^(7^11) is divided by 5? (here, 3 is raised to the power (7^11))

(A) 0

(B) 1

(C) 2

(D) 3

(E) 4

Solution: As we said last week, this question can easily be solved using cyclicity and negative remainders. What is the remainder when a number is divided by 5? Say, what is the remainder when 2387646 is divided by 5? Are you going to do this division to find the remainder? No! Note that every number ending in 5 or 0 is divisible by 5.

2387646 = 2387645 + 1

i.e. the given number is 1 more than a multiple of 5. Obviously then, when the number is divided by 5, the remainder will be 1. Hence the last digit of a number decides what the remainder is when the number is divided by 5.

On the same lines,

What is the remainder when 36793 is divided by 5? It is 3 (since it is 3 more than 36790 – a multiple of 5).

What is the remainder when 46^8 is divided by 5? It is 1. Why? Because 46 to any power will always end with 6 so it will always be 1 more than a multiple of 5.

On the same lines, if we can find the last digit of 3^(7^11), we will be able to find the remainder when it is divided by 5.

Recall from the discussion in your books, 3 has a cyclicity of 4 i.e. the last digit of 3 to any power takes one of 4 values in succession.

3^1 = 3

3^2 = 9

3^3 = 27

3^4 = 81

3^5 = 243

3^6 = 729

and so on… The last digits of powers of 3 are 3, 9, 7, 1, 3, 9, 7, 1 … Every time the power is a multiple of 4, the last digit is 1. If it is 1 more than a multiple of 4, the last digit is 3. If it is 2 more than a multiple of 4, the last digit is 9 and if it 3 more than a multiple of 4, the last digit is 7.

What about the power here 7^(11)? Is it a multiple of 4, 1 more than a multiple of 4, 2 more than a multiple of 4 or 3 more than a multiple of 4? We need to find the remainder when 7^(11) is divided by 4 to know that.

Do you remember the binomial theorem concept we discussed many weeks back? If no,  check it out here .

7^(11) = (8 – 1)^(11)

When this is divided by 4, the remainder will be the last term of this expansion which will be (-1)^11. A remainder of -1 means a positive remainder of 3 (if you are not sure why this is so, check  last week’s post here ). Mind you, you are not to mark the answer as (D) here and move on! The solution is not complete yet. 3 is just the remainder when 7^(11) is divided by 4.

So 7^(11) is 3 more than a multiple of 4.

Review what we just discussed above: If the power of 3 is 3 more than a multiple of 4, the last digit of 3^(power) will be 7.

So the last digit of 3^(7^11) is 7.

If the last digit of a number is 7, when it is divided by 5, the remainder will be 2. Now we got the answer!

Answer (C)

Interesting question, isn’t it?

Karishma , a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the  GMAT  for Veritas Prep and regularly participates in content development projects such as this blog!

Bunuel · Answer

Also check  All About Negative Remainders on the GMAT

chetan2u · Answer

hi ...
 another fast way to such Q is through remainder theorem(?)..
 we find modulus and here it is 5*(1-1/5)=4..
this means the remainder asked will be same as remainder of 3^(remainder of 7^11 when divided by 4) divided by 5..
7^11 when divided by 4 will give remainder of (-1)^11=-1 or 3...
so 3^3 divided will give 27/5 or 2 is the remainder...

padener · Answer

Hi everyone,

I am new and I was just reading the post but I was somehow lost when following the solution...so I tried to solve myself and I did in this way:

I wrote down the following in order to find a possible pattern (R=remainder):

k | 3^k | R when divided by 5 |
0 | 1___|_______1________|
1 | 3___|_______3________|
2 | 9___|_______4________|
3 | 27__|_______2________|
4 | 81__|_______1________|
5 | 243_|_______3________|

Stop! OK I found a general pattern for the remainder cyclical (1,3,4,2)...then since 3^(7^11) is equal to 3^77 then is sufficient to look at the line where k is 7 (because 77 is eleven times 7)...that is the same as the line with k=3 so R=2! Indeed...

6 | not needed |_______4________|
7 | not needed |_______2________|
 
So the answer is 2 that is (C).

Am I wrong? It was quite fast in this way...

Thanks to everybody!

Padener

P.s.
Sorry for the _____ but I did not know how to format properly the table....

Bunuel · Answer

When getting the pattern of the units digit of x^k you should always start with k=1, not k=0.

padener · Answer

Yes you are right because k=0 will always give 1 as results...so no meaning.

But apart from that is right the approach?

Thanks for the answer.

Padener

Bunuel · Answer

The red part is not correct: 3^7^11 = 3^77 but 3^(7^11) = 3 to the power of (7^11). Theory on Exponents: math-number-theory-88376.html Tips on Exponents: exponents-and-roots-on-the-gmat-tips-and-hints-174993.html Check Units digits, exponents, remainders problems directory in our Special Questions Directory .

JesusWalks · Answer

Is there something wrong in my methodology?

7^11 .. 7 has cycle of 7, 9, 3, 1.. so the remainder is 3. 
3^3 = 27
27 / 5 = remainder of 2

IanStewart · Answer

When you divide 3^k by 5 or 10, and want to know the remainder, then you want to know where you'll be in the units digit pattern of 3^k. Because the units digit pattern of 3^k repeats in 'blocks' (cycles) of 4 terms, you need to know the remainder when you divide k by 4 in order to know where you'll be in that pattern. In this question, k = 7^11, so you'd need to find the remainder when you divide 7^11 by 4. What you found above is the remainder when you divide 7^11 by 10. So you correctly determined that 7^11 has a units digit of 3, but that alone doesn't tell you the remainder when you divide 7^11 by 4 (since some numbers that end in 3 will give a remainder of 1 when you divide by 4, and some will give a remainder of 3 when you divide by 4). It's because it's not straightforward to find the remainder when you divide 7^11 by 4 that the posters above needed some lengthier solutions.

Kritisood · Answer

Hi 
"7^11 .. 7 has cycle of 7, 9, 3, 1.. so the  remainde r is 3". Here the units digit would be 3 and not the remainder. Am I correct? 
how to solve ahead if we know 3^m3/5? could someone help pls.

bumpbot · Answer

Automated notice from GMAT Club BumpBot: 

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

 This post was generated automatically.

A Tricky Question on Negative Remainders

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

A Tricky Question on Negative Remainders

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