document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1205778>Question 1205778</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Hi, I have shown my working for the question below, am I on the right track?\r<BR>\n" );
document.write( "\n" );
document.write( "〖Simplify 10〗^241  mod(13) \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Fermat’s Little Theorem states:<BR>\n" );
document.write( "a^(p-1)≡1mod(p)\r<BR>\n" );
document.write( "\n" );
document.write( "Substitute:<BR>\n" );
document.write( "10^12≡1mod(13) \r<BR>\n" );
document.write( "\n" );
document.write( "By our multiplication theorem we know that if<BR>\n" );
document.write( "10^12≡1mod(13) <BR>\n" );
document.write( "Then<BR>\n" );
document.write( "10^((12)A)≡(1)^A mod (13) \r<BR>\n" );
document.write( "\n" );
document.write( "We want to get from a power of 12 up to around 241, and 12 x 20 = 240<BR>\n" );
document.write( "         10^(12)(20) ≡1^20 mod(13) <BR>\n" );
document.write( "  ≡1mod(13)\r<BR>\n" );
document.write( "\n" );
document.write( "So what we have so far is<BR>\n" );
document.write( "10^241 mod(13)≡10^240×10^1 mod(13) <BR>\n" );
document.write( "                          ≡1×10mod(13) <BR>\n" );
document.write( "                          ≡10mod(13)\r<BR>\n" );
document.write( "\n" );
document.write( "When 10^241is divided by 13, the remainder is 10 \r<BR>\n" );
document.write( "\n" );
document.write( "Thank you </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #842810 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=842810\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <font color=black size=3><BR>\n" );
document.write( "You have the correct line of thinking and correct answer. Nice work.<BR>\n" );
document.write( "This first section basically restates what you mentioned. <BR>\n" );
document.write( "The next two sections will go over other approaches.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Fermat's Little Theorem (FLT)<BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large a^{p} \equiv a (\text{mod } p)\"> <BR>\n" );
document.write( "'a' is an integer<BR>\n" );
document.write( "p is prime\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Special case of FLT<BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large a^{p-1} \equiv 1 (\text{mod } p)\"><BR>\n" );
document.write( "where p is <u>not</u> a factor of 'a' \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{12} \equiv 1 (\text{mod } 13)\"> Due to the special case of FLT\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large \left(10^{12}\right)^{20} \equiv 1^{20} (\text{mod } 13)\"> Raise both sides to the 20th power\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{12*20} \equiv 1 (\text{mod } 13)\"> Use the rule that (a^b)^c = a^(b*c)\r<BR>\n" );
document.write( "\n" );
document.write( " <BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{240} \equiv 1 (\text{mod } 13)\"> \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10*10^{240} \equiv 10*1 (\text{mod } 13)\"> Multiply both sides by 10\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^1*10^{240} \equiv 10 (\text{mod } 13)\"> \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{1+240} \equiv 10 (\text{mod } 13)\"> Use the rule that a^b*a^c = a^(b+c)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{241} \equiv 10 (\text{mod } 13)\"> \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "--------------------------------------------------------------------------\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "A 2nd approach:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Let's look at powers of 10^n (mod 13) to see if we can spot any patterns. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{1} \equiv 10 (\text{mod } 13)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{2} \equiv 100 \equiv 9  (\text{mod } 13)\"> because 100/13 = 7 remainder 9. We only care about the remainder.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{3} \equiv 10*10^2 \equiv 10*9 \equiv 90 \equiv 12  (\text{mod } 13)\"> because 90/13 = 6 remainder 12. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{4} \equiv 10*10^3 \equiv 10*12 \equiv 120 \equiv 3  (\text{mod } 13)\"> because 120/13 = 9 remainder 3\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "You can keep this process going. <BR>\n" );
document.write( "I'll use a spreadsheet to extend this list. I'm using a command called <font color=red>Mod</font><BR>\n" );
document.write( "Example: Type in <font color=red>=Mod(100,13)</font> to get 9<BR>\n" );
document.write( "<TABLE  border = \"1\" cellpadding = \"5\">\n" );
document.write( "<tr><TD >n</TD><TD >10^n mod 13</TD></tr><tr><TD >1</TD><TD >10</TD></tr><tr><TD >2</TD><TD >9</TD></tr><tr><TD >3</TD><TD >12</TD></tr><tr><TD >4</TD><TD >3</TD></tr><tr><TD >5</TD><TD >4</TD></tr><tr><TD >6</TD><TD >1</TD></tr><tr><TD >7</TD><TD >10</TD></tr><tr><TD >8</TD><TD >9</TD></tr><tr><TD >9</TD><TD >12</TD></tr><tr><TD >10</TD><TD >3</TD></tr>\n" );
document.write( "</TABLE><BR>\n" );
document.write( "I'll leave the scratch work for the student to do.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The pattern is 10, 9, 12, 3, 4, 1, 10, 9...<BR>\n" );
document.write( "Once reaching remainder 1, the pattern repeats over again. <BR>\n" );
document.write( "This is simply because 1 times any number is that number. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "There are 6 items in the set {10, 9, 12, 3, 4, 1}<BR>\n" );
document.write( "So this means we'll divide 241 over 6 to look at the remainder (yes it seems a bit strange to change the modulus all of a sudden)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "241/6 = 40 remainder 1<BR>\n" );
document.write( "The remainder 1 means we'll look at the 1st slot of that 6 number repeating pattern. That 1st slot is 10.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Therefore we found another way to determine that <BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{241} \equiv 10  (\text{mod } 13)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "--------------------------------------------------------------------------------------------------------------------\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "A 3rd approach:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Let's look at terms of the form 10^(2^n) where n is a positive integer <BR>\n" );
document.write( "Effectively we're repeatedly squaring powers of 10, since something like 10^4 is the squaring of 10^2; or 10^8 is the squaring of 10^4, etc\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{2} \equiv 9 (\text{mod } 13)\"> mentioned in the previous section\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large  10^{4} \equiv \left(10^{2}\right)^2 \equiv 3 (\text{mod } 13)\"> mentioned in the previous section\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large  10^{8} \equiv \left(10^{4}\right)^2 \equiv \left(3\right)^2   \equiv 9 (\text{mod } 13)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large  10^{16} \equiv \left(10^{8}\right)^2 \equiv \left(9\right)^2   \equiv 81  \equiv 3 (\text{mod } 13)\"> because 81/13 = 6 remainder 3.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Keep this process going to generate this table<BR>\n" );
document.write( "<TABLE  border = \"1\" cellpadding = \"5\">\n" );
document.write( "<tr><TD >n</TD><TD >2^n</TD><TD >10^(2^n) mod 13</TD></tr><tr><TD >1</TD><TD >2</TD><TD >9</TD></tr><tr><TD >2</TD><TD >4</TD><TD >3</TD></tr><tr><TD >3</TD><TD >8</TD><TD >9</TD></tr><tr><TD >4</TD><TD >16</TD><TD >3</TD></tr><tr><TD >5</TD><TD >32</TD><TD >9</TD></tr><tr><TD >6</TD><TD >64</TD><TD >3</TD></tr><tr><TD >7</TD><TD >128</TD><TD >9</TD></tr><tr><TD >8</TD>\r\n" );
document.write( "<TD >256</TD><TD >3</TD></tr>\n" );
document.write( "</TABLE><BR>\n" );
document.write( "We have a much nicer pattern going on here.<BR>\n" );
document.write( "The remainder is either 9 or 3 depending if n is odd or even in that order.<BR>\n" );
document.write( "Technically a table isn't needed, but it could be nice to have.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This is so we can break 241 into its binary components so to speak.<BR>\n" );
document.write( "Refer to tutorials on how to convert from base 10 to base 2.<BR>\n" );
document.write( "241 base 10 = 11110001 base 2<BR>\n" );
document.write( "241 base 10 = 1*2^7 + 1*2^6 + 1*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 1*2^0<BR>\n" );
document.write( "241 base 10 = 1*128 + 1*64 + 1*32 + 1*16 + 0*8 + 0*4 + 0*2 + 1*1<BR>\n" );
document.write( "241 base 10 = 128 + 64 + 32 + 16 + 1<BR>\n" );
document.write( "241 = 128 + 64 + 32 + 16 + 1\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Then notice the following computation<BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{241} \equiv 10^{128+64+32+16+1} (\text{mod } 13)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{241} \equiv 10^{128}*10^{64}*10^{32}*10^{16}*10^{1} (\text{mod } 13)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{241} \equiv 9*3*9*3*10 (\text{mod } 13)\"> Use the table shown above. For example, 10^128 = 9 (mod 13)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{241} \equiv (9*3)*(9*3)*10 (\text{mod } 13)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{241} \equiv (27)*(27)*10 (\text{mod } 13)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{241} \equiv (1)*(1)*10 (\text{mod } 13)\"> because 27/13 = 2 remainder 1\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 10^{241} \equiv 10 (\text{mod } 13)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "--------------------------------------------------------------------------------------------------------------------\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "FLT is perhaps the best choice since it appears your professor has introduced it and is likely expecting you to use it; however, it's still good practice to be able to tackle problems in various ways.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "For more practice, check out this similar question<BR>\n" );
document.write( "https://www.algebra.com/algebra/homework/complex/Complex_Numbers.faq.question.1205936.html<BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );