Posted by amanda on Sunday, February 22, 2009 at 5:56pm.
You can use the Chinese Remainder Theorem. Notation: If a number X divided by N has a remainder of r, we write
X Mod N = r
("Mod" is shorthand for "Modulo")
So, if we call the solution X, we have:
X Mod 7 = 4
X Mod 8 = 5
X Mod 9 = 6
If you are given some number X and you want to compute X mod 7, then you can subtract from X any multiple of 7 without affecting the result. If there exists a number Y such that
X* Y Mod 7 = 1,
then we call Y the inverse of X and vice versa. E.g. 3*5 Mod 7 = 1, so, Mod 7, the inverse of 3 is 5 and the inverse of 5 is 3. Let's use this notation for the inverse:
[3]_7 = inverse of 3 mod 7 = 5
You can now directly write down the solution of your problem as:
X = 4*8*9[8*9]_7 + 5*7*9[7*9]_8 +
6*7*8[7*8]_9
Let's check that this is the solution. If you compute X Mod 7, the first term will yield 4 because 4 is multiplied by 8*9 and then we multiply by the inverse of 8*9 mod 7, so the 8*9 multiplied by the inverse of 8*9 yields 1 Mod 7 and we are left with 4.
What about the other two terms? Well, they are all proportional to 7, so they yield zero Mod 7.
So, we see that X Mod 7 = 4
Similarly, you can see that x Mod 8 = 5. The first and last terms are proportional to 8 and are thus zero Mod 8. The second term is, Mod 8, equal to 5, because it is 5 times 7*9 times the inverse of 7 * 9.
And similarly, it is easy to see that X Mod 9 = 6.
So, to find X you have to work out the inverses. We have:
8*9 Mod 7 = 2
Note that to compute this you can reduce 8 Mod 7 first which is 1 and 9 Mod 7 = 2, so 8*9 Mod 7 =
1*2 Mod 7 = 2.
The inverse of 8*9 Mod 7 is thus the same as the inverse of 2 Mod 7. Now, we have:
2*3 Mod 7 = 6 Mod 7 = -1 Mod 7
So, 2*(-3) Mod 7 = 1 Mod 7
So, the inverse is -3 Mod 7 = 4
Indeed 2*4 = 8 and 8 Mod 7 = 1
The next term we need to calculate is:
[7*9]_8
Now Mod 8 we have that:
7 Mod 8 = -1 Mod 8
9 Mod 8 = 1
So, we need the inverse of -1, which we can take to be -1 or -1 + 8 = 7.
Finally we have to compute:
[7*8]_9
7 Mod 9 = -2 Mod 9
8 Mod 9 = -1 Mod 9
So 7*8 Mod 9 = 2
The inverse of 2 is, Mod 9, equal to 5 because 2*5 = 10 and Mod 9 we have 10 Mod 9 = 1.
The solution is thus:
X = 4*8*9[8*9]_7 + 5*7*9[7*9]_8 +
6*7*8[7*8]_9 =
X = 4*8*9*4 - 5*7*9 +
6*7*8*5 = 2517
By adding a multiple of 7*8*9 to a solution, you get another solution because 7*8*9 is zero Mod 7, Mod 8 and Mod 9. All possible solutions can be obtained this way. The smalles solution is thus:
2517 Mod (7*8*9) = 501