Post a New Question

math

posted by on .

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

  • math - ,

    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

Answer This Question

First Name:
School Subject:
Answer:

Related Questions

More Related Questions

Post a New Question