Question 249147
Apparently there is no easy way to do this.


I found the answer <a href = "http://mathcentral.uregina.ca/QQ/database/QQ.09.08/h/sophia1.html" target = "_blank">here.</a>


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.