Question

what is the least common positive integer that meets the following conditions:

divided by 7 with remainder 4
divided by 8 with remainder 5
divided by 9 with remainder 6

i thought you could add 7 and 4 to get 13, then divide 13 and 7 with r=4, but it has to be the same number for all of them. and it's not any numbers between 0 and 215

Answer 1

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