Find the remainder when 17^17 is divided by 64:

Question

A 0
B 1
C 17
D 34
E 64

cric_fan · Accepted Answer

An easier way here would be using the options.

Given an even number is dividing an odd number the remainder has to be odd

That leaves us with only 2 options - 1 and 17

Let’s consider 17 first:

If 17 is the remainder, (17^17-17)/64 must leave a remainder of 0

= 17(17^16-1)/64

Now, 17^16 - 1 can be broken down as (17^8 -1)(17^8+1) = (17^4-1)(17^4+1)(17^8+1) and so on. Hence it is divisible by 17-1 = 16 and every other factor of it will be divisible by 2.

Hence, 17^17-17 must be divisible by 64

Posted from my mobile device

gmatophobia · Answer

Remainder( \frac{17^{17}}{64} ) =  \frac{17^{16}*17}{64}

= Remainder( \frac{17^{16}}{64} ) * Remainder( \frac{17}{64} )

= Remainder( \frac{((16+1)^{2})^8}{64} ) * Remainder( \frac{17}{64} )

= Remainder( \frac{(256 + 1 + 32)^8}{64} ) * Remainder( \frac{17}{64} )

⇒  Remainder( \frac{(256 + 1 + 32)}{64} ) = 33

A remainder of 33, can be represented as 64 - 31, hence the remainder of 33 can be expressed as -31.

Remainder( \frac{(-31)^8}{64} ) * Remainder( \frac{17}{64} )

= Remainder( \frac{((-31)^2)^4}{64} ) * Remainder( \frac{17}{64} )

⇒  Remainder( \frac{(-31)^2)}{64} )

⇒  Remainder( \frac{961}{64} ) = 1

= Remainder( \frac{(1)^4}{64} ) * Remainder( \frac{17}{64} )

1 * 17 = 17

Option C

Another method to solve this question is using theorems. However, such concepts are not required to solve any questions in GMAT.

playthegame · Answer

Great thanks. So re: your comment about theorems which ones are you suggesting? Binomial theorem? Would you be able to describe the theorem you think is applicable in this case?

I think Fermat's little theorem and the remainder theorem I was not able to really apply.

I ended up taking 17 square out as 289 then that gave me a remainder of 33 when divided by 64 (289-256) and I ended up reducing from there.

Thanks!

stne · Answer

Is this a typo or am I lacking some concept?

How  17 = 16-1

Thank you.

gmatophobia · Answer

Corrected typo.

Hope it helped.

sachi-in · Answer

This is a problem of Binomial expansion

17 ^ 17  divided by 64  ( we should note 64 can be written as 16 * 4 )

hence we can write 17 ^ 17 as  ( 16 + 1 ) ^ 17

(x + y) ^ 17 Binomial expansion is :

C0 * x^17 * y^0 + C1 * x^16 * y^1 + ..... + C16 * x^1 * y^16 + C17 * x^0 * y^17

C0 * 16^17 * 1^0 + C1 * 17^16 * 1^1 + ..... +   C16 * 16^1 * 1^16 + C17 * 16^0 * 1^17

The portion marked in green is the only portion not divisible by 64 rest all terms have atleast 16^2 as power hence divisible by 64

C16 * 16^1 * 1^16 + C17 * 16^0 * 1^17  =  17 * 16 * 1 + 1   =   16(16 + 1) + 1

Again 16*16 is divisible by 64 ..  remiander is 16*1 + 1 = 17

Oppenheimer1945 · Answer

(16+1)^17=17C1 (16)^17+17C1 (16)^17+… 17C1(16)+17C0
=16^2 z+ 17x16+1=16^2a+16+1=16^2b+17

Remainder is 17

Posted from my mobile device

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.

Find the remainder when 17^17 is divided by 64:

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

­Find the remainder when 17^17 is divided by 64:

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

Find the remainder when 17^17 is divided by 64: