document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1208759>Question 1208759</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Find the smallest integer which will divide over 45, 72, and 999 leaving remainder as 5, 2, and 9. </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #847192 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=847192\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <font color=black size=3><BR>\n" );
document.write( "The goal is to solve this system of congruences<BR>\n" );
document.write( "x = 5 (mod 45)<BR>\n" );
document.write( "x = 2 (mod 72)<BR>\n" );
document.write( "x = 9 (mod 999)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Recall that if a = b (mod n) then a-b = nk for some integer k.<BR>\n" );
document.write( "Rearranging things gives a = nk + b.<BR>\n" );
document.write( "Use this idea to transform the first two equations into x = 45k+5 and x = 72m+2. We cannot re-use k.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Both equations involve x, so equate the right hand sides and we get,<BR>\n" );
document.write( "72m+2 = 45k+5<BR>\n" );
document.write( "72m-45k = 5-2<BR>\n" );
document.write( "9(8m-5k) = 3<BR>\n" );
document.write( "9(integer-integer) = 3<BR>\n" );
document.write( "9*(integer) = 3<BR>\n" );
document.write( "integer = 3/9<BR>\n" );
document.write( "integer = 1/3<BR>\n" );
document.write( "which is a contradiction. The value 1/3 = 0.33333... is not in the set of integers.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Therefore the first two equations of the original system do not have a solution.<BR>\n" );
document.write( "Overall the entire system doesn't have a solution either.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "--------------------\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "I used a Python script to check integers from x = 1 to x = 10,000,000 and couldn't find any solutions. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This numeric approach of course doesn't prove there aren't any solutions, since there are infinitely many integers to check, but it's useful to get partial backup confirmation.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "A spreadsheet is another alternative verification route.<BR>\n" );
document.write( "You may be asking yourself \"Can we use Chinese Remainder Theorem?\"<BR>\n" );
document.write( "The answer would be \"No because the mod values 45, 72, and 999 are not pairwise coprime.\"\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "------------------------------------------------------------<BR>\n" );
document.write( "------------------------------------------------------------\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Answer: <font color=red>No solutions</font><BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );