document.write( "Question 391281: What is the least number that when divided by 7 has a remainder of 4, and when divided by 8 has a remainder of 5, and when divided by 9 has a remainder of 6? \n" ); document.write( "
Algebra.Com's Answer #277613 by robertb(5830)\"\" \"About 
You can put this solution on YOUR website!
I will assume that the least number you're asking for is a positive number.
\n" ); document.write( "Then we have to find the smallest positive integer n that satisfies the simultaneous system of congruences
\n" ); document.write( "n = 4 mod 7,
\n" ); document.write( "n = 5 mod 8,
\n" ); document.write( "n = 6 mod 9.\r
\n" ); document.write( "\n" ); document.write( "We use the Chinese Remainder Theorem using the extended Euclidean algorithm. (For the statement of the theorem and symbolism go to http://en.wikipedia.org/wiki/Chinese_remainder_theorem).\r
\n" ); document.write( "\n" ); document.write( "(31)(7) + (-3)(8*9) = 31*7 + -3*72 = 1 ==> e1 = -216 (=-3*72)
\n" ); document.write( "8*8 + -1*(7*9) = 8*8 + -1*63 = 1 ==>e2 = -63 (=-1*63), and
\n" ); document.write( "25*9 + -4*(7*8) = 25*9 + -4*56 = 1 ==> e3 = -224. ( = -4*56) \r
\n" ); document.write( "\n" ); document.write( "Then the solution n is the linear combination n = 4*e1 + 5*e2 + 6*e3 = 4*-216 +5*-63 +6*-224 = -2523 mod 504, where 504 = 7*8*9.
\n" ); document.write( "The least positive integer satisfying n = -2523 mod 504 is 501.
\n" ); document.write( "Therefore the final answer is 501. \n" ); document.write( "
\n" );