SOLUTION: What is the remainder when 2 ^ 2006 is divided by 17 ?

Question 249147: What is the remainder when 2 ^ 2006 is divided by 17 ?
Answer by Theo(13342) (Show Source): You can put this solution on YOUR website!
Apparently there is no easy way to do this.

I found the answer here.

the answer was not complete but it started me on my way to finding out how it was done.

here's what I found.

you need to find a pattern.

if you follow the directions you will see that the pattern is every 8 exponents.

2^0 = 1 / 17 = remainder of 1
2^8 = 256 / 17 = remainder of 1
2^16 = 65536 / 17 = remainder of 1

the first 8 numbers in the sequence are:

2^0 = 1 / 17 = 0 with a remainder of 1
2^1 = 2 / 17 = 0 with a remainder of 2
2^2 = 4 / 17 = 0 with a remainder of 4
2^3 = 8 / 17 = 0 with a remainder of 8
2^4 = 16 / 17 = 0 with a remainder of 16
2^5 = 32 / 17 = 1 with a remainder of 15
2^6 = 64 / 17 = 3 with a remainder of 13
2^7 = 128 / 17 = 7 with a remainder of 9
2^8 = 256 / 17 = 15 with a remainder of 1 and the pattern starts all over again.

what happens if you are given 2^9 / 17 and are asked to find the remainder.

you can actually solve this, and your answer will be 2 because the pattern repeated all over again.

2^9 = 512 / 17 = 30 with a remainder of 2.

if the number was very large, like 2^2006, you can't do this.

If you know the repeating pattern, however, you can figure it out.

since the pattern repeats every 8 exponents, just divide 9 by 8 to get 1.something.

take the integer part and multiply it by 8 to get 8.

subtract 8 from 9 to get 1.

your 2^9 remainder is equivalent to the remainder of 2^1.

That remainder equals 2.

try it again with a larger number.

suppose your number is 2^20 / 17 and they want to know what the remainder is.

take the exponent of 20 and divide it by 8 to get 2.5

take the integer part of the answer and multiply it by 8 to get 2 * 8 = 16

subtract 16 from 20 to get 4.

your remainder will be equivalent to the remainder of 2^4 which would equal 16

again, this is small enough that we can prove it, so:

2^20 = 1048576 / 17 = 61680.94118 and the remainder is .9411765 * 17 = 16

there will be some rounding errors, but 16 is the remainder and the equivalent of 2^4 remainder is also 16 so we're good.

applied to your problem, you would do the following:

2^2006 / 17 = remainder of ?????

take 2006 and divide it by 8 to get 250.75

multiply 8 by 250 to get 2000.

subtract 2000 from 2006 to get 6

your remainder will be equivalent to the remainder of 2^6.

that would equal 13

I calculated up to 2^23 just to ensure myself that the pattern repeated every 8 exponents.

It does, but you have to start from 2^0 in order to see that for the first 8 exponents.

2^7 - 2^0 = 8
2^7 equals a remainder of 9
2^(7+8) = 2^15 equals a remainder of 9
2^(15+8) = 2^23 equals a remainder of 9

Once the number of exponents in the repeating pattern was derived, the rest was how to apply that number to the exponents which is the procedure I just gave you.

RELATED QUESTIONS
what will be the remainder when 16^2+17^2+18^2+19^2 is divided by... (answered by fractalier)

What is that number , when that number is divided by 9 the remainder is 8 , when that... (answered by AnlytcPhil)

1) What is the remainder when 2^31 is divided by 10? 2) What is the remainder when 2^69... (answered by Boreal)

What is the remainder when (2^2015+2015^2) when divided by... (answered by ikleyn)

1) What is the remainder when 231 is divided by 10? 2) What is the remainder when 269 is (answered by Boreal)

when N is divided by 5, the remainder is 3. what is the remainder when 7N is divided by... (answered by richwmiller)

when N is divided by 5, the remainder is 3. what is the remainder when 7N is divided by... (answered by richwmiller,jim_thompson5910)

When Z is divided by 8, the remainder is 5. What is the remainder when 4Z is divided by... (answered by ankor@dixie-net.com)

When x is divided by 7, the remainder is 5. What is the remainder when 5x is divided by... (answered by ikleyn)