What is the remainder when 11^704 is divided by 17 ?

Question

What is the remainder when  11^{704}  is divided by 17 ?

A. 1
B. 5
C. 6
D. 11
E. 13

This is a  PS Butler Question

Check the links to other Butler Projects: 
 
   Data Sufficiency Butler 
   Critical Reasoning Butler  
   Sentence Correction Butler  
   Reading Comprehension Butler  
   Integrated Reasoning Butler

gmatophobia · Answer

Remainder ( \frac{11^{704} }{ 17} )

Remainder ( \frac{(-6)^{704} }{ 17} )

Remainder ( \frac{(36)^{352} }{ 17} )

Remainder ( \frac{(2)^{352} }{ 17} )

Remainder ( \frac{(2)^{4*88} }{ 17} )

Remainder ( \frac{16^{88} }{ 17} )

Remainder ( \frac{(-1)^{88} }{ 17} )

= 1

Option A

szcz · Answer

This sum can be done in a couple of ways. There is actually a formula as well but that is out of the purview of GMAT.
We use the remainder of 11/17 to find the remainder for 11^2/17, then we use the remainder of 11^2/17 to find the remainder for 11^3/17, and so on. Until we get a remainder of 1/-1.

Remainder (11/17)=11, 
Remainder (11^2/17)=2
.
.
.
Remainder (11^8)/17=-1
704= 8 * 88
Therefore, 11^704=88 (11^8)
Hence the remainder = -1 * -1 * -1... 88 times.
This will give us the remainder = 1
Option A

$!vakumar.m · Answer

11^704 divided by 17
11^2 = 121 which when divided by 17 gives 2 as remainder
2^(704/2) = 2^352. Now 2^4 = 16 and 16/17 = -1
so we can write as 
(-1)^(352/4) = (-1)^88 = 1
Therefore, the remainder is 1
Answer A

suddu · Answer

Could you please explain the last part where 16/17=-1 ???

$!vakumar.m · Answer

Hi suddu this is negative remainder. In the ibid case, 16/17 gives 16 as remainder or it can be seen as -1 (-1 + 17 = 16) as well. For details please refer this link from Bunuel https://gmatclub.com/forum/all-about-ne ... l#p1472077 Best Wishes Siva kumar

capnmoron · Answer

There is a theorem I read on this platform somewhere: Fermat's little theorem, which states that any number when raised to the power of (p-1), where p is a prime number, will leave remainder of 1 when divided by p.

Here, observe that 17 is a prime number, hence 11^(17-1) will leave a remainder of 1 when divided by 17.
Therefore, 11^16 can be written as 17x+1

Now, 11^704 = 11^(16*44) = (17x+1)^44

Expanding by binomial theorem,
(17x+1)^44 = 44C0* *  + 44C1* *  +........+ 44C43* *  + 44C44* *

Now, the final term of the expansion is the only term which does not have 17 as a factor, hence, the remainder is the remainder of final term when it is divided by 17, and since the final term is 1, the answer is 1.

What is the remainder when 11^704 is divided by 17 ?

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 11^704 is divided by 17 ?

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