document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1116320>Question 1116320</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Calculate<BR>\n" );
document.write( " <BR>\n" );
document.write( "9^563 mod907<BR>\n" );
document.write( " <BR>\n" );
document.write( "Identify which one of the following options gives the correct solution for the above expression ?<BR>\n" );
document.write( " \r<BR>\n" );
document.write( "\n" );
document.write( "	<BR>\n" );
document.write( " 310<BR>\n" );
document.write( "	<BR>\n" );
document.write( " 520<BR>\n" );
document.write( "	<BR>\n" );
document.write( "630<BR>\n" );
document.write( "	<BR>\n" );
document.write( "493\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "My working:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "9^563 mod 907\r<BR>\n" );
document.write( "\n" );
document.write( "First I identified the exponents.\r<BR>\n" );
document.write( "\n" );
document.write( "9^1 mod 907<BR>\n" );
document.write( "9^2 mod 907<BR>\n" );
document.write( "9^16 mod 907 <BR>\n" );
document.write( "9^32 mod 907 <BR>\n" );
document.write( "9^512 mod 907\r<BR>\n" );
document.write( "\n" );
document.write( "(512+32+16+2+1=563)\r<BR>\n" );
document.write( "\n" );
document.write( "9^1 mod 907=9<BR>\n" );
document.write( "9^2 mod 907=81<BR>\n" );
document.write( "9^16 mod 907 =669<BR>\n" );
document.write( "9^32 mod 907 =410<BR>\n" );
document.write( "9^512 mod 907=862\r<BR>\n" );
document.write( "\n" );
document.write( "To show my working between 9^32 mod 907 and 9^512 mod 907\r<BR>\n" );
document.write( "\n" );
document.write( "9^64 mod 907= 410^2 mod 907 =305<BR>\n" );
document.write( "9^128 mod 907=305^2 mod 907=511<BR>\n" );
document.write( "9^256 mod 907 =511^2 mod 907 = 812<BR>\n" );
document.write( "9^512 mod 907= 812^2 mod 907=862\r<BR>\n" );
document.write( "\n" );
document.write( "But I am not sure what is the final step....<BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #844300 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=844300\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <font color=black size=3><BR>\n" );
document.write( "Answer: <font color=red size=4>520</font>\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Work Shown\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Let's list out the powers of 2.<BR>\n" );
document.write( "2^0 = 1<BR>\n" );
document.write( "2^1 = 2<BR>\n" );
document.write( "2^2 = 4<BR>\n" );
document.write( "2^3 = 8<BR>\n" );
document.write( "2^4 = 16<BR>\n" );
document.write( "2^5 = 32<BR>\n" );
document.write( "2^6 = 64<BR>\n" );
document.write( "2^7 = 128<BR>\n" );
document.write( "2^8 = 256<BR>\n" );
document.write( "2^9 = 512<BR>\n" );
document.write( "2^10 = 1024<BR>\n" );
document.write( "etc...<BR>\n" );
document.write( "We stop here since we won't go larger than 563.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Subtract off the largest power of 2 that is smaller than 563 or equal to it.<BR>\n" );
document.write( "We'll have:<BR>\n" );
document.write( "563-512 = 51<BR>\n" );
document.write( "Off to the side somewhere write 512 since we'll be using it later.<BR>\n" );
document.write( "Then subtract off the largest power of 2 that is smaller than 51 or equal to it.<BR>\n" );
document.write( "So,<BR>\n" );
document.write( "51 - 32 = 19<BR>\n" );
document.write( "Write 32 off to the side to join with 512.<BR>\n" );
document.write( "We keep this process going until we arrive at 0.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Here's what the scratch work looks like.<BR>\n" );
document.write( "563 - 512 = 51<BR>\n" );
document.write( "51 - 32 = 19<BR>\n" );
document.write( "19 - 16 = 3<BR>\n" );
document.write( "3 - 2 = 1<BR>\n" );
document.write( "1 - 1 = 0<BR>\n" );
document.write( "Those second values on the left hand side can then be reconstructed like this<BR>\n" );
document.write( "1+2+16+32+512 = 563<BR>\n" );
document.write( "This is useful for any time we need to convert from base 10 to binary.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "It appears that you already know of this trick, but I wrote it out just in case another student is curious. The same applies for the scratch work shown in the next section.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "--------------------------------------------------------------------------\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Now we'll look at terms of the form 9^(2^n)<BR>\n" );
document.write( "In other words we'll look at terms of the form 9^m where m is a power of 2.<BR>\n" );
document.write( "Specifically we're interested in the modulus when dividing by 907.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "9^1 = 9 (mod 907)<BR>\n" );
document.write( "9^2 = 81 (mod 907)<BR>\n" );
document.write( "are fairly straight forward.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Square both sides of the second equation to get:<BR>\n" );
document.write( "9^4 = (9^2)^2 = (81)^2 = 6561 = 212 (mod 907)<BR>\n" );
document.write( "Note that 6561/907 = 7 remainder 212. We ignore the quotient. The modulus only cares about the remainder.<BR>\n" );
document.write( "This idea is applied many times in the scratch work shown below.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "We'll repeatedly square each simplified result to generate the next term we need.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "9^1 = 9 (mod 907)<BR>\n" );
document.write( "9^2 = 81 (mod 907)<BR>\n" );
document.write( "9^4 = (9^2)^2 = (81)^2 = 6561 = 212 (mod 907)<BR>\n" );
document.write( "9^8 = (9^4)^2 = (212)^2 = 44944 = 501 (mod 907)<BR>\n" );
document.write( "9^16 = (9^8)^2 = (501)^2 = 251001 = 669 (mod 907)<BR>\n" );
document.write( "9^32 = (9^16)^2 = (669)^2 = 447561 = 410 (mod 907)<BR>\n" );
document.write( "9^64 = (9^32)^2 = (410)^2 = 168100 = 305 (mod 907)<BR>\n" );
document.write( "9^128 = (9^64)^2 = (305)^2 = 93025 = 511 (mod 907)<BR>\n" );
document.write( "9^256 = (9^128)^2 = (511)^2 = 261121 = 812 (mod 907)<BR>\n" );
document.write( "9^512 = (9^256)^2 = (812)^2 = 659344 = 862 (mod 907)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "In short,<BR>\n" );
document.write( "9^1 = 9 (mod 907)<BR>\n" );
document.write( "9^2 = 81 (mod 907)<BR>\n" );
document.write( "9^4 = 212 (mod 907)<BR>\n" );
document.write( "9^8 = 501 (mod 907)<BR>\n" );
document.write( "9^16 = 669 (mod 907)<BR>\n" );
document.write( "9^32 = 410 (mod 907)<BR>\n" );
document.write( "9^64 = 305 (mod 907)<BR>\n" );
document.write( "9^128 = 511 (mod 907)<BR>\n" );
document.write( "9^256 = 812 (mod 907)<BR>\n" );
document.write( "9^512 = 862 (mod 907)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Let's toss out the rows we don't need.<BR>\n" );
document.write( "We'll end up with this:<BR>\n" );
document.write( "9^1 = 9 (mod 907)<BR>\n" );
document.write( "9^2 = 81 (mod 907)<BR>\n" );
document.write( "9^16 = 669 (mod 907)<BR>\n" );
document.write( "9^32 = 410 (mod 907)<BR>\n" );
document.write( "9^512 = 862 (mod 907)<BR>\n" );
document.write( "Nice work on getting the correct values so far.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Then,<BR>\n" );
document.write( "9^563 = 9^(1+2+16+32+512)<BR>\n" );
document.write( "9^563 = (9^1)*(9^2)*(9^16)*(9^32)*(9^512)<BR>\n" );
document.write( "9^563 = (9)*(81)*(669)*(410)*(862)<BR>\n" );
document.write( "9^563 = (9*81)*(669*410)*(862)<BR>\n" );
document.write( "9^563 = (729)*(274290)*(862)<BR>\n" );
document.write( "9^563 = (729)*(376)*(862) (mod 907)<BR>\n" );
document.write( "9^563 = (729*376)*(862) (mod 907)<BR>\n" );
document.write( "9^563 = 274104*862 (mod 907)<BR>\n" );
document.write( "9^563 = 190*862 (mod 907)<BR>\n" );
document.write( "9^563 = 163780 (mod 907)<BR>\n" );
document.write( "9^563 = <font color=red>520</font> (mod 907)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "You can use a tool like <a  rel=nofollow HREF= \"https://www.wolframalpha.com/input?i=9%5E563+%3D+520+%28mod+907%29\">WolframAlpha</a> to confirm the answer.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "More practice is found <a  rel=nofollow HREF= \"https://www.algebra.com/algebra/homework/divisibility/lessons/successive-squaring.lesson\">here</a><BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );