math

posted by .

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

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. Math - repost for Anonymous

    Can someone show me the steps to these questions (I will provide the correct answers)?
  2. math

    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 …
  3. Algebra 2

    Find a positive integer smaller than 500 that has a remainder of 3 when divided by 5, a remainder of 6 when divided by 9, and a remainder of 8 when divided by 11.
  4. number theory

    Find the least positive integer that leaves the remainder 3 when divided by 7, remainder 4 when divided by 9, and remainder 8 when divided by 11
  5. Math

    Find the least positive integer that leaves the remainder 3 when divided by 7, remainder 4 when divided by 9, and remainder 8 when divided by 11. Using the Chinese Remainder Theorem.
  6. Math

    How many integers bewteen 200 and 500 inclusive leave a remainder 1 when divided by 7 and a remainder 3 when divided by 4?
  7. Math

    How many integers between 200 and 500 inclusive leave a remainder 1 when divided by 7 and a remainder 3 when divided by 4?
  8. Math

    Find the smallest positive integer that leaves a remainder of 5 when divided by 7, a remainder of 6 when divided by 11, and a remainder of 4 when divided by 13.
  9. math

    1.) when the expression 4x^2-3x-8 is divided by x-a, the remainder is 2. find the value of a. 2.) the polynomial 3x^3+mx^2+nx+5 leaves a remainder of 128 when divided by x-3 and a remainder of 4 when divided by x+1. calculate the remainder …
  10. Math adv function

    An unknown polynomial f(x) of degree 37 yields a remainder of 1 when divided by x – 1, a remainder of 3 when divided by x – 3, a remainder of 21 when divided by x – 5. Find the remainder when f(x) is divided by (x – 1)(x – …

More Similar Questions