document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1208760>Question 1208760</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Find an integer x such that when its divided over 5, 7, and 11 gives remainders 2,3, and 10<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 #847193 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=847193\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <font color=black size=3><BR>\n" );
document.write( "Your question is equivalent to solving this system of congruences<BR>\n" );
document.write( "x = 2 (mod 5)<BR>\n" );
document.write( "x = 3 (mod 7)<BR>\n" );
document.write( "x = 10 (mod 11)<BR>\n" );
document.write( "We use the Chinese Remainder Theorem to solve this system.<BR>\n" );
document.write( "The theorem is applicable because the mod values are pairwise coprime.<BR>\n" );
document.write( "GCD(5,7) = 1 and GCD(5,11) = 1 and GCD(7,11) = 1\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Each congruence is of the form x = b (mod n)<BR>\n" );
document.write( "(b1,b2,b3) = (2,3,10) are the right hand side values<BR>\n" );
document.write( "(n1,n2,n3) = (5,7,11) are the modulus values<BR>\n" );
document.write( "N = n1*n2*n3 = 5*7*11 = 385\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "m1 = N/n1 = 385/5 = 77<BR>\n" );
document.write( "m2 = N/n2 = 385/7 = 55<BR>\n" );
document.write( "m3 = N/n3 = 385/11 = 35\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "We'll need to find a multiplicative inverse for {m1,m2,m3} with the corresponding mods {n1,n2,n3} in the order presented.<BR>\n" );
document.write( "m1 = 77 = 2 (mod 5)<BR>\n" );
document.write( "We need to find the multiplicative inverse of 2 mod 5. <BR>\n" );
document.write( "We need to solve 2*y1 = 1 (mod 5). Quick trial and error leads to y1 = 3.<BR>\n" );
document.write( "m2 = 55 = 6 = -1 (mod 7)<BR>\n" );
document.write( "m2*y2 = 1 (mod 7) then solves to y2 = -1 = 6 (mod 7)<BR>\n" );
document.write( "m3 = 35 = 2 (mod 11). Solving m3*y3 = 1 (mod 11) leads to y3 = 6 through use of trial and error\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Recap so far<BR>\n" );
document.write( "(b1,b2,b3) = (2,3,10)<BR>\n" );
document.write( "(n1,n2,n3) = (5,7,11)<BR>\n" );
document.write( "(m1,m2,m3) = (77,55,35)<BR>\n" );
document.write( "(y1,y2,y3) = (3,6,6)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "A solution would be<BR>\n" );
document.write( "x = y1*b1*m1 + y2*b2*m2 + y3*b3*m3<BR>\n" );
document.write( "x = 3*2*77 + 6*3*55 + 6*10*35<BR>\n" );
document.write( "x = 3552<BR>\n" );
document.write( "The set of all solutions fit the congruence x = 3552 (mod 385) <BR>\n" );
document.write( "Recall that N = 385 was the product of the three modulus values.<BR>\n" );
document.write( "3552 = 87 (mod 385)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This leads to x = 87 (mod 385) <BR>\n" );
document.write( "x = 87 (mod 385) can be translated to the equation x = 385k + 87 where k is an integer.<BR>\n" );
document.write( "This describes all possible integer solutions to this system of congruence equations. <BR>\n" );
document.write( "There are infinitely many solutions.<BR>\n" );
document.write( "A few select solutions are {87, 472, 857, 1242}\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "--------------------------------------------------------------------------\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Answer: <BR>\n" );
document.write( "Anything of the form x = 385k + 87 where k is an integer.<BR>\n" );
document.write( "Eg: if k = 0 then x = 87 is one solution of infinitely many.<BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );