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.
|
|
|
