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.
|
|
|
