document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=249147>Question 249147</A>: <I><SPAN STYLE=\"word-break: break-all;\"> What is the remainder when 2 ^ 2006 is divided by 17 ? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #181514 by </B><A HREF=/tutors/aboutme.mpl?userid=Theo><B>Theo(13342)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=Theo><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=Theo><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=181514\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> Apparently there is no easy way to do this.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "I found the answer <a  rel=nofollow HREF= \"http://mathcentral.uregina.ca/QQ/database/QQ.09.08/h/sophia1.html\" target = \"_blank\">here.</a>\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "the answer was not complete but it started me on my way to finding out how it was done.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "here's what I found.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "you need to find a pattern.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "if you follow the directions you will see that the pattern is every 8 exponents.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "2^0 = 1 / 17 = remainder of 1<BR>\n" );
document.write( "2^8 = 256 / 17 = remainder of 1<BR>\n" );
document.write( "2^16 = 65536 / 17 = remainder of 1\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "the first 8 numbers in the sequence are:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "2^0 = 1 / 17 = 0 with a remainder of 1<BR>\n" );
document.write( "2^1 = 2 / 17 = 0 with a remainder of 2<BR>\n" );
document.write( "2^2 = 4 / 17 = 0 with a remainder of 4<BR>\n" );
document.write( "2^3 = 8 / 17 = 0 with a remainder of 8<BR>\n" );
document.write( "2^4 = 16 / 17 = 0 with a remainder of 16<BR>\n" );
document.write( "2^5 = 32 / 17 = 1 with a remainder of 15<BR>\n" );
document.write( "2^6 = 64 / 17 = 3 with a remainder of 13<BR>\n" );
document.write( "2^7 = 128 / 17 = 7 with a remainder of 9<BR>\n" );
document.write( "2^8 = 256 / 17 = 15 with a remainder of 1 and the pattern starts all over again.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "what happens if you are given 2^9 / 17 and are asked to find the remainder.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "you can actually solve this, and your answer will be 2 because the pattern repeated all over again.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "2^9 = 512 / 17 = 30 with a remainder of 2.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "if the number was very large, like 2^2006, you can't do this.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "If you know the repeating pattern, however, you can figure it out.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "since the pattern repeats every 8 exponents, just divide 9 by 8 to get 1.something.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "take the integer part and multiply it by 8 to get 8.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "subtract 8 from 9 to get 1.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "your 2^9 remainder is equivalent to the remainder of 2^1.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "That remainder equals 2.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "try it again with a larger number.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "suppose your number is 2^20 / 17 and they want to know what the remainder is.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "take the exponent of 20 and divide it by 8 to get 2.5\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "take the integer part of the answer and multiply it by 8 to get 2 * 8 = 16\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "subtract 16 from 20 to get 4.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "your remainder will be equivalent to the remainder of 2^4 which would equal 16\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "again, this is small enough that we can prove it, so:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "2^20 = 1048576 / 17 = 61680.94118 and the remainder is .9411765 * 17 = 16\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "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.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "applied to your problem, you would do the following:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "2^2006 / 17 = remainder of ?????\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "take 2006 and divide it by 8 to get 250.75\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "multiply 8 by 250 to get 2000.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "subtract 2000 from 2006 to get 6\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "your remainder will be equivalent to the remainder of 2^6.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "that would equal 13\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "I calculated up to 2^23 just to ensure myself that the pattern repeated every 8 exponents.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "It does, but you have to start from 2^0 in order to see that for the first 8 exponents.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "2^7 - 2^0 = 8\r<BR>\n" );
document.write( "\n" );
document.write( "2^7 equals a remainder of 9<BR>\n" );
document.write( "2^(7+8) = 2^15 equals a remainder of 9<BR>\n" );
document.write( "2^(15+8) = 2^23 equals a remainder of 9\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "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.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );