document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1197923>Question 1197923</A>: <I><SPAN STYLE=\"word-break: break-all;\"> What remainder is left when the number <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=%28567288133%29%5E6 ALIGN=MIDDLE  ALT=\"%28567288133%29%5E6\"   DISABLED_style= \"max-width:90%; height:auto;\" > is divided by 8? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #831392 by </B><A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><B>math_tutor2020(3817)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><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/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=831392\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <font color=black size=3><BR>\n" );
document.write( "Recall the divisibility by 8 rule says that we only need to look at the last 3 digits of the number to see if the number is a multiple of 8 or not.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This means numbers like <BR>\n" );
document.write( "800<BR>\n" );
document.write( "1800<BR>\n" );
document.write( "11800<BR>\n" );
document.write( "111800<BR>\n" );
document.write( "are all multiples of 8 since 800, in the last three digits, is a multiple of 8.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Then note how 8*16 = 128<BR>\n" );
document.write( "So numbers like <BR>\n" );
document.write( "128<BR>\n" );
document.write( "4128<BR>\n" );
document.write( "54128<BR>\n" );
document.write( "754128<BR>\n" );
document.write( "are all multiples of 8 because 128 is a multiple of 8.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Furthermore, adding 5 more to each number causes us to get a remainder of 5 when dividing by 8.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "128+5 = 133<BR>\n" );
document.write( "133/8 = something remainder 5\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "4128+5 = 4133<BR>\n" );
document.write( "4133/8 = something remainder 5\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "54128+5 = 54133<BR>\n" );
document.write( "54133/8 = something remainder 5\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "and so on. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "In short, the last three digits of 133 indicate we'll get a remainder of 5 when dividing it over 8.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "So even if the number 567288133 is really massive, we only need to care about the 133 at the end.<BR>\n" );
document.write( "133/8 = something remainder 5<BR>\n" );
document.write( "567288133/8 = something remainder 5<BR>\n" );
document.write( "We don't need to worry about the quotient, so I just labeled it as \"something\".\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This leads 567288133^6 to reduce to 5^6 mod 8.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Let's look at powers of 5 mod 8.<BR>\n" );
document.write( "Meaning that I'll divide numbers of the form 5^k over 8 to determine the remainder<BR>\n" );
document.write( "5^1 = 5 (mod 8)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "5^2 = 5*5 (mod 8)<BR>\n" );
document.write( "5^2 = 25 (mod 8)<BR>\n" );
document.write( "5^2 = 1 (mod 8) since 25 is 1 more than 24 = 3*8\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "5^3 = 5*5^2 (mod 8)<BR>\n" );
document.write( "5^3 = 5*25 (mod 8)<BR>\n" );
document.write( "5^3 = 5*1 (mod 8) .... replace 25 with 1 mod 8<BR>\n" );
document.write( "5^3 = 5 (mod 8)<BR>\n" );
document.write( "This tells us that dividing 5^3 over 8 gets us a remainder of 5.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "5^4 = 5*5^3 (mod 8)<BR>\n" );
document.write( "5^4 = 5*5 (mod 8) .... replace 5^3 with 5 mod 8<BR>\n" );
document.write( "5^4 = 25 (mod 8)<BR>\n" );
document.write( "5^4 = 1 (mod 8)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "As you can see, we get this pattern of remainders: 5, 1, 5, 1, ...<BR>\n" );
document.write( "It cycles forever like this.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "If the exponent k is odd, then 5^k = 5 (mod 8)<BR>\n" );
document.write( "If the exponent k is even, then 5^k = 1 (mod 8)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Therefore, 5^6 = 1 (mod 8)  because of the even number exponent<BR>\n" );
document.write( "i.e. (5^6)/8 = something remainder 1\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Check:<BR>\n" );
document.write( "5^6 = 15625<BR>\n" );
document.write( "15625/8 = 1953.125 = 1953 remainder 1\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Answer:  <font color=red>1</font><BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );