SOLUTION: 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?

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?
Answer by robertb(5830) (Show Source): You can put this solution on YOUR website!
I will assume that the least number you're asking for is a positive number.
Then we have to find the smallest positive integer n that satisfies the simultaneous system of congruences
n = 4 mod 7,
n = 5 mod 8,
n = 6 mod 9.
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).
(31)(7) + (-3)(8*9) = 31*7 + -3*72 = 1 ==> e1 = -216 (=-3*72)
8*8 + -1*(7*9) = 8*8 + -1*63 = 1 ==>e2 = -63 (=-1*63), and
25*9 + -4*(7*8) = 25*9 + -4*56 = 1 ==> e3 = -224. ( = -4*56)
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.
The least positive integer satisfying n = -2523 mod 504 is 501.
Therefore the final answer is 501.
RELATED QUESTIONS
what number less than 3000 when divided by 10 has a remainder of 9 and when divided by 9... (answered by venugopalramana)

What is the smallest whole number that has a remainder of 1 when divided by 4, a... (answered by RAY100)

What is the lowest number n that when divided by 3 leaves a remainder of 1, when divided... (answered by ikleyn)

find the least natural number that has the remainder 3 when divided by 5. the remainder 5 (answered by greenestamps)

A certain number leaves a remainder of 4 when divided by 5, a remainder of 5 when divided (answered by ikleyn,ankor@dixie-net.com)

I am thinking of a number, when divided by 9 the remainder is 4. When divided by 5 the... (answered by MathLover1,greenestamps)

What is the smallest possible integer that's greater than 100, and leaves a remainder of... (answered by CubeyThePenguin)

Find the smallest possible integer which, when divided by 3 has a remainder of 1, when... (answered by richard1234,Edwin McCravy)

What is the smallest positive integer that gives a remainder of 1 when divided by 4, a... (answered by Edwin McCravy)