# 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

## 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 …