What is the remainder when 7^44 is divided by 9?

Question

What is the remainder when  7^{44}  is divided by 9?

A. 1
B. 3
C. 4
D. 6
E. 9

IanStewart · Accepted Answer

7^3 = 343, which has (as we can see by summing its digits) a remainder of 1 when divided by 9. So (7^3)^14 = 7^42 also produces a remainder of 1 when divided by 9. Since 7^44 = (7^42)(7^2), the remainder we're asked for will just be 1 times the remainder when 7^2 = 49 is divided by 9, so will be 4.

I'm using principles from modular arithmetic here (without explaining them) that really aren't necessary on actual GMAT questions.

I'm using principles from modular arithmetic here (without explaining them) that really aren't necessary on actual GMAT questions.

yashikaaggarwal · Answer

Using Euler theorem,

When A^x is divided by N, where A and N are co prime.
Since N here has 3 as prime factor (p) 
Ø(n) = n(1-1/p)
Ø(9) = 9(1-1/3)
Ø(9) = 9*(2/3)
Ø(9) = 3*2
Ø(9) = 6

So A^Ø(n) mod n = 1 as remainder
7^6 mod 9 = 1
(7^6)7 mod 9 * 7^2 mod 9
1*4 mod 9
4 mod 9
4 as remainder

Answer is C

justbegan · Answer

i read all explanations but not convinced as 44 on dividing by 4 (the unit digits are repeated in the sequence of 4 for powers of 7. for example, 7^1=7, 7^2=49 (9), 7^3=343 (3), 7^4= 2401 (1)) Thus on dividing 44 by 4, remainder will be 0 and unit digit should be 1 which will be divided by 9 gives 1 as final remainder. can anyone clear my doubt?

CrackverbalGMAT · Answer

Hello justbegan. you are right about dividing the power by the cyclicity of 7 (which is 4) to give you a remainder of 0. The last digit of 7^44 is 1.

The question here though is not asking for the last digit. The last digit would have been 1, if the divisor was 10. Here the divisor is 9.

So here every 3 powers of 7 gives 343 and 343 divided by 9 gives a remainder of 1. So  R  = R  = 4

Hope this helps

Arun Kumar

IanStewart · Answer

It's true that the units digit of 7^44 will be 1. But when you know a number's units digit, that only tells you the remainder you will get when you divide that number by 2, 5, or 10. In this question, we're dividing by 9, and knowing the units digit alone doesn't actually tell us anything about what remainder we'll get when we divide by 9. If you think of several numbers with a units digit of 1, and divide them by 9, you'll see you get different remainders: when we divide by 9, 11 gives a remainder of 2, 21 gives a remainder of 3, 31 gives a remainder of 4, and so on. Numbers with a units digit of 1 can actually have any remainder at all (from 0 to 8 inclusive) when divided by 9.

The question in this thread isn't a realistic GMAT problem, incidentally, and on the real test, most questions that look similar to this one will actually be asking about remainders when dividing by 5 or by 10, in which case your method will work.

Abhishek009 · Answer

7^{3}=343

Now,  7^{44}=7^{14*3+2}

Since,  \frac{7^{3}}{9} = \frac{343}{9}  = Remainder 1

So,  \frac{7^2}{9}  = = Remainder 4

Thus, Answer must be (C) 4

magbot · Answer

7^44/ 9

Make the numerator close to 9

= (9 - 2)^{44} / 9  
 = 9^{44} + ........ + (-2)^{44} / 9   
 = (-2)^{44} / 9    
 = 2^{44} / 9

Make the numerator again close to 9 
 = 2^{42} * 4 / 9  
 = 8^{14} * 4 / 9  
 = (9 - 1)^{14} * 4 / 9   
 = (-1)^{14} * 4 / 9   
 =4/9   
Remainder is 4

Can someone verify this ?

Abhishek009 · Answer

Verified, this works as well !!!

IanStewart · Answer

The general idea here is correct, but the solution actually contains two mistakes, and the second fortunately reversed the first one, which is why you arrived at the right answer.

First, (9-2)^44 is not equal to 9^44 - 2^44 (just as (5-4)^2, which is 1, is not equal to 5^2 - 4^2, which is 9). If you want to expand (9-2)^44, you need to use the "binomial theorem", which isn't ever needed on the GMAT. But the binomial theorem tells us that

(9 - 2)^44 = 9^44 - (something)*9^43 + (something)*9^42 - .... - (something)*9 + (-2)^44

and the binomial theorem also tells us what those "something" numbers are all equal to, but they don't matter here. The important point is that every number in that sum above is a multiple of 9 besides the last one, (-2)^44. Since we're dividing by 9 here, and we only care about our remainder, none of the multiples of 9 in the sum above will affect our answer (we'd only care about them if we cared about what quotient we get when we divide by 9). So we can ignore every term above besides the last one, (-2)^44.

Now, in your solution, you instead had -2^44, which you replaced with (-2)^44, and those aren't equal (since -2^44 is negative, but (-2)^44 is positive), but that's how you ended up 'fixing' your solution. Once we know we want to find the remainder when we divide (-2)^44 = 2^44 by 9, we can do something similar to what you did: 2^44 = (2^3)^14 * 2^2 = 8^14 * 4 which is just like (-1)^14 * 4 if we're finding a remainder by 9, so is just like 4.

magbot · Answer

IanStewart , You are right. Thanks.

I knew that the reduction came from binomial theorem but the example I looked previously had positive term and this one had a negative term. I knew something was off.. I will add more details in the above explanation.

If the power is odd and the last term will stay negative and remainder would be 9 -4 =5 for example right ?

IanStewart · Answer

Yes, it is true that the last term will stay negative when the power is odd. And it looks like you have the right idea about how to adjust a negative answer in a question like this: if you use a method like yours, and arrive at an answer like -4, you would need to add 9 (or whatever we're dividing by in the question) to get a valid remainder between 0 and 8 inclusive, so the answer would be 5.

But in this specific question, you'll never get 5 as the final answer (or "-4"), even if you change the exponent. Assuming our letters are non-negative integers, when you divide 7^x by 9, the only remainders you can ever get are 1, 4 or 7. That's because the remainder when you divide 7^3 by 9 is 1. So when we divide

7^(3k) = (7^3)^k by 9, the remainder is 1
7^(3k + 1) by 9, the remainder is 7
7^(3k + 2) by 9, the remainder is 4

and those are the only possible cases. Again, I'm using modular arithmetic principles here that aren't required on any real GMAT problems (but are helpful on a lot of prep company questions).

mcrea · Answer

I do not understand the following phrasing:
"So (7^3)^14 = 7^42 also produces a remainder of 1 when divided by 9."

why?

How can you know that by simply looking at 7^3?
For example:
- we cannot say that since 7^4 = 2401, which has a remainder of 7 when divided by 9, also (7^4)^11 = 7^44 has a remainder of 7.
- we can simply say that since 7^2 = 49, which has a remainder of 4 when divided by 9, also (7^2)^22 = 7^44 has a remainder of 4.

mcrea · Answer

simply notice that when:

7^1 is divided by 9 the remainder is 7
7^2 is divided by 9 the remainder is 4
7^3 is divided by 9 the remainder is 1
7^4 is divided by 9 the remainder is 7
so the remainders pattern repeats every 3 powers of 7. (7, 4, 1, 7, 4, 1, 7....)

Now, the closest multiple of 3 to 44 is 42, thus 7^42 has a remainder of 1 when devided by 9. 7^43 will have 7 and then finally 7^44 will have 4 as remainder when divided by 9.

Or, the closest multiple of 3 to 44 is 45, thus 7^45 has a remainder of 1 when divided by 9. Then, 7^44 will have 4 as remainder when divided by 9.

IanStewart · Answer

As I said in my post, I was using some modular arithmetic principles without explaining them fully (and I wasn't explaining them since they aren't tested on the GMAT, but they're essentially required for questions like this one). I'll explain the principle I was using with division by 9 for illustration, but this would work regardless of what you are dividing by:

If you want to know the remainder you will get when you divide k^x by 9, you can just find the remainder when you divide r^x by 9, where r is the remainder when k is divided by 9.

In other words, if we have a large base and an exponent in a remainders question, we can just replace that base with its remainder in questions like this. So, since when we divide 7^3 by 9, the remainder is 1, when we divide (7^3)^14 by 9, we can just replace the base 7^3 with 1, and we'll get the correct remainder if we just divide 1^14 by 9, i.e. if we divide 1 by 9, so the remainder is 1.

Applying this to your examples:

• since 7^4 gives a remainder of 7 when divided by 9, then (7^4)^11 will have the same remainder as 7^11 will have when divided by 9 (we'd still have some work to do then to get a practical calculation)

• since 7^2 gives a remainder of 4 when divided by 9, then (7^2)^22 will have the same remainder as 4^22 will have when divided by 9 (and again, we'd still have some work to do to make 4^22 manageably small)

To use this principle to solve these kinds of problems, you're really looking to find a remainder of 1 (or -1, if you know how to work with negative remainders), because then the remainder calculation becomes very easy, which is why I worked specifically with 7^3.

Your method is also perfect -- it is true (just as with units digits) that if you find the remainders dividing 7^1, 7^2, 7^3 and so on by 9, you'll eventually get a looping pattern, and this always happens no matter what number you're dividing by, so you can then use that pattern to predict the remainder you'll have for large exponents. You are, however, using somewhat advanced modular arithmetic principles, just as I did, to conclude that this pattern will in fact predictably repeat. The only potential problem with that method is the looping pattern can take a long time to emerge. If, say, you try to use this method to find the remainder when 2^120 is divided by 13, you'll see you have to list twelve different values before the pattern begins to repeat (for 2^1, 2^2, all the way up to 2^12, you get different remainders).

BrushMyQuant · Answer

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

=>  7^{44}  =  (9-2)^{44}

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 9
=> All terms except the last term will give remainder of 0 when divided by 9
=> Problem is reduced to what is the remainder when the last term (i.e. 44C44 * 9^0 * (-2)^44) is divided by 9
=> Remainder of 2^44 is divided by 9

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

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

=> Cycle is 6

=> We need to find Remainder of 44 by 6 = 2
=> Remainder of  2^{44}  is divided by 9 = Remainder of 2^2 by 9 = 4

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

Rohan271 · Answer

Can you explain the logic behind taking 7^3 (remainder=1) and not 2401? Also, is it wrong to make pattern for remainders (such as 7/9 -R=7, 49/9 R=4..etc)? Should I always look for which power the remainder is 1?

What is the remainder when 7^44 is divided by 9?

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 7^44 is divided by 9?

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