What is the remainder when 8^643/132?

Question

A. 116
B. 117
C. 120
D. 109

8^643 = (2^3)^643=2^1929

2^x has a cyclicity of 3 , 1929 is divisible by 3..

how to proceed please help..

KarishmaB · Accepted Answer

Both 29 and 116 can be in the options because the answer is only 116. In fact, it is quite likely that both will be there since if there is a way to trip you, GMAT will not let it go. You can choose to cancel off terms in the numerator and denominator or you can choose to keep them as it is. In either case, answer will be 116.

\frac{8^{643}}{132} = \frac{8*8^{642}}{132}

We get  2*\frac{8^{642}}{33} = 2*\frac{2^{1926}}{33}

Now, notice that  2^5 = 32  is 1 less than 33 so we use it. 
1926 is 1 more than a multiple of 5 so we keep aside a 2.

2*2*\frac{2^{1925}}{33} = 4*\frac{32^{385}}{33}

We get  4*\frac{(33 - 1)^{385}}{33}

Using binomial theorem (discussed in the link given above), we see that the remainder is -4 i.e. 29.

Recall that we cancelled off 4 from the numerator in the beginning. We need to multiply it back so actual remainder is 29*4 = 116

EvaJager · Answer

8^{643}=(2^3)^{643}=2^{1929} 
 132=2^2\cdot{3}\cdot{11}

33=32+1=2^5+1

2^{1927}=(2^5)^{385}\cdot2^2=(33-1)^{385}\cdot{4}=(M33-1)\cdot{4}=M33-4=M33-33+29=M33+29 .
( M33  designates multiple of  33 .)

2^{1929}=2^{1927}\cdot2^2=(M33+29)\cdot{4}=M132+29\cdot{4}=M132+116 .
 M33+29  means  33n+29 , for some integer  n . Then  (M33+29)\cdot{4}=132n+29\cdot{4}=M132+116 .

Hence, the remainder is 116.

g3kr · Answer

What is wrong if i cancel out 2^2 in the numerator and divide by 33 . I still have to get the same reminder right?

Vips0000 · Answer

Hi g3kr,

Both of the last 2 solutions fetching 29 and 116 are correct processwise, but for a logical mistake in former.

Consider the case, 16/10 will have a remainder of 6, but its not same as 8/5 which has a remainder of 3 only.

The difference? notice that for any y/x remainder can not be greater than x, hence if you have factored out a number from numerator and denominator, you have reduced remainder by that times.
In our example of 16/10: if we make it 8/5 by dividing each term by 2 and get 3 as remainder. we should multiply result by 2 to get correct ans 6.

hence, once you arrived in first solution (M33+29)

you should remember to multiply it by 4, the one which was factored out earlier. Or better dont factor out and cancel a term in a remainder problem.

Hope it helps.

mindmind · Answer

What is wrong if i cancel out 2^2 in the numerator and divide by 33 . I still have to get the same reminder right?

Hi g3kr,

Both of the last 2 solutions fetching 29 and 116 are correct processwise, but for a logical mistake in former.

Consider the case, 16/10 will have a remainder of 6, but its not same as 8/5 which has a remainder of 3 only.

The difference? notice that for any y/x remainder can not be greater than x, hence if you have factored out a number from numerator and denominator, you have reduced remainder by that times.
In our example of 16/10: if we make it 8/5 by dividing each term by 2 and get 3 as remainder. we should multiply result by 2 to get correct ans 6.

hence, once you arrived in first solution (M33+29)

you should remember to multiply it by 4, the one which was factored out earlier. Or better dont factor out and cancel a term in a remainder problem.

Hope it helps.

Thanks,

Even I had the same ambiguity..
But just to be sure.. there wont be both options in the answer : 29 & 116 ?

Vips0000 · Answer

Hi mindmind (too many minds :D), Exactly what I explained with example of 16/10 and 8/5. if i ask you remainder of 16/10 and give u option of 6 and 3, will you be confused? I dont think so

If u factor out a number, the "fraction" remains same but "remainder" does not. please re-read the post. Also this is why it is important not to factor out in remainder problem. Also try to check one more way of understanding it: a remainder is shown as below: if n = qm +r then kn = kqm +kr where Kn is a multiple of n and km is multiple of m. But this changes remainder from r to kr. Hope it is clear..

KarishmaB · Answer

Responding to a pm:

What is the remainder when 12 is divided by 8? 
12/8 quotient 1 and remainder 4.

But when we divide both numerator and denominator by 4, we get 3/2. What is the remainder when 3 is divided by 2? It is 1. It is not the same as the remainder when 12 is divided by 8. 
To get the actual remainder, you need to multiply 1 by 4 back to get 4 as remainder.

vcmnamban · Answer

Hi, Correct me if I'm wrong.

Here, cyclicity of 8 is 4. 
643/4, gives 3 as reminder.
8^3 /132 = 512/132, leaves a reminder of 116.

Fish181 · Answer

Different way to solve: It worked somehow and it's easier than what's being said. Find the unit's digit pattern for 8. (I've noticed all numbers' units digit pattern repeats after 4 iterations).

8^1 =  8 
8^2 = 6 4 
8^3 = 51 2 
8^4 = 409 6

Find 643/4 = 160 r3. This means that the number will end in the iteration of 8^3 = 51 2 .

512/132 = 3  r 116

mumuxi · Answer

you will need Fermat's little theorem and then extend it to Euler totient theorem 
first general formula for modula
(a x b ) mod c = ((a mod c) x (b mod c)) mod c 
(a^b) mod c =. (a mod c )^b mod c

8^643 mod 132 = 4x (2^1927 mod 33)
so lets solve 2^1927 mod 33 first 
f(33) = f(3) * f(11) = (3-1)x(11-1) = 20
2^20 =1 mod 33 by Euler's theorem
1927 = 20*96+7
2^1927 mod 33 = 2^7 mod 33 = 128 mod 33 = 29
29 x 4 = 116

What is the remainder when 8^643/132?

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 8^643/132?

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