document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1205936>Question 1205936</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Hi can you help me with this question:<BR>\n" );
document.write( "What is the remainder when 11^128 is divided by 43? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #843038 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=843038\">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>35</font>\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Explanation\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "I'll use Fermat's Little Theorem which is not to be confused with Fermat's Last Theorem.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Fermat's Little Theorem is<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( "where 'a' is an integer and p is prime\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "If p is <u>not</u> a factor of 'a', then an extension of Fermat's Little Theorem states that<BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large a^{p-1} \equiv 1 (\text{mod } p)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This is very useful due to the 1 on the right hand side.<BR>\n" );
document.write( "If a = 11 and p = 43, then,<BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large a^{p-1} \equiv 1 (\text{mod } p)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^{43-1} \equiv 1 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^{42} \equiv 1 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "How can we get the exponent 42 to turn into 128?<BR>\n" );
document.write( "Well let's divide the values to get 128/42 = 3.0476 approximately.<BR>\n" );
document.write( "So we need to triple 42 to get close to 128.<BR>\n" );
document.write( "Let's cube both sides of the last congruence equation shown above.<BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^{42} \equiv 1 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large (11^{42})^3 \equiv 1^3 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^{42*3} \equiv 1 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^{126} \equiv 1 (\text{mod } 43)\"><BR>\n" );
document.write( "I'm using the exponent rule that (a^b)^c = a^(b*c).<BR>\n" );
document.write( "Notice that cubing 1 results in 1. This is why the \"1\" is so useful.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "We have the exponent at 126 but we need it at 128 instead. <BR>\n" );
document.write( "So we need to add on 2. To do this, we multiply both sides by 11^2 as indicated in the scratch work below.<BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^{126} \equiv 1 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^2*11^{126} \equiv 11^2*1 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^{2+126} \equiv 121 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^{128} \equiv 35 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Notice that 121/43 = 2 remainder 35<BR>\n" );
document.write( "The remainder is all we care about when concerning modular arithmetic. <BR>\n" );
document.write( "This is why <IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 121 \equiv 35 (\text{mod } 43)\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Since <IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\Large 11^{128} \equiv 35 (\text{mod } 43)\"> we conclude that <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=%2811%5E128%29%2F43 ALIGN=MIDDLE  ALT=\"%2811%5E128%29%2F43\"   DISABLED_style= \"max-width:90%; height:auto;\" > leads to some quotient with <font color=red>remainder 35</font>. <BR>\n" );
document.write( "Luckily we don't need to worry about the quotient.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "--------------------------------------------------------------------------\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Need a way to do this without using Fermat's Little Theorem?\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Let's look at powers of 11 mod 43 to see if we can spot any patterns.<ul><li>11^1 = 11 (mod 43)</li><li>11^2 = 121 = 35 (mod 43) ... refer to the previous section</li><li>11^3 = 11*11^2 = 11*35 = 385 = 41 (mod 43) ... since 385/43 = 8 remainder 41</li><li>11^4 = 11*11^3 = 11*41 = 451 = 21 (mod 43) ... since 451/43 = 10 remainder 21</li></ul>Here's a table summarizing the pattern so far.<BR>\n" );
document.write( "<TABLE  border = \"1\" cellpadding = \"5\">\n" );
document.write( "<tr><TD >n</TD><TD >11^n mod 43</TD></tr><tr><TD >1</TD><TD >11</TD></tr><tr><TD >2</TD><TD >35</TD></tr><tr><TD >3</TD><TD >41</TD></tr><tr><TD >4</TD><TD >21</TD></tr>\n" );
document.write( "</TABLE><BR>\n" );
document.write( "Let's extend that table somewhat<BR>\n" );
document.write( "<TABLE  border = \"1\" cellpadding = \"5\">\n" );
document.write( "<tr><TD >n</TD><TD >11^n mod 43</TD></tr><tr><TD >1</TD><TD >11</TD></tr><tr><TD >2</TD><TD >35</TD></tr><tr><TD >3</TD><TD >41</TD></tr><tr><TD >4</TD><TD >21</TD></tr><tr><TD >5</TD><TD >16</TD></tr><tr><TD >6</TD><TD >4</TD></tr><tr><TD >7</TD><TD >1</TD></tr><tr><TD >8</TD><TD >11</TD></tr><tr><TD >9</TD><TD >35</TD></tr><tr><TD >10</TD><TD >41</TD></tr>\n" );
document.write( "</TABLE><BR>\n" );
document.write( "I'll let the student do the scratch work for n = 5 through n = 10.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Notice once reaching remainder 1 (when n = 7), the pattern of remainders repeats.<BR>\n" );
document.write( "That repeating pattern is {11, 35, 41, 21, 16, 4, 1} which consists of 7 items.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The pattern repeats itself every 7 items.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Divide 128 over 7 to find the remainder.<BR>\n" );
document.write( "128/7 = 18 remainder 2\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The \"remainder 2\" tells us to look at the 2nd slot of the pattern {11, <font color=red>35</font>, 41, 21, 16, 4, 1} which is <font color=red>35</font><BR>\n" );
document.write( "In other words, 11^2 and 11^128 have the same remainder when in mod 43.\r<BR>\n" );
document.write( "<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.1205778.html<BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );