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.
See solution to the same problem at:
http://www.jiskha.com/display.cgi?id=1343870416
I'm thinking of a number.
When I divide it by 2, the remainder is 1.
When I divide it by 3, the remainder is 2.
When I divide it by 4, the remainder is 3.
When I divide it by 5, the remainder is 4.
When I divide it by 6, the remainder is 5.
When I divide it by 7, the remainder is 6.
When I divide it by 8, the remainder is 7.
When I divide it by 9, the remainder is 8.
When I divide it by 10, the remainder is 9.
What is the smallest number with such a property?
To find the least positive integer that satisfies these conditions using the Chinese Remainder Theorem, we need to follow these steps:
Step 1: List the remainders and their corresponding divisors:
Remainder | Divisor
---------------------
3 | 7
4 | 9
8 | 11
Step 2: Compute the product of all the divisors:
N = 7 * 9 * 11 = 693
Step 3: Find the divisors for each remainder:
For remainder 3:
- Compute the product of all the divisors except for 7: 9 * 11 = 99.
- Find the modular inverse of 99 modulo 7.
- Let's find the value of x such that (99 * x) % 7 = 1.
- When we try different values of x, we find that x = 4 satisfies the equation.
- Multiply the remainder (3) by the product (99) and the modular inverse (4):
- 3 * 99 * 4 = 1188
For remainder 4:
- Compute the product of all the divisors except for 9: 7 * 11 = 77.
- Find the modular inverse of 77 modulo 9.
- Let's find the value of x such that (77 * x) % 9 = 1.
- When we try different values of x, we find that x = 5 satisfies the equation.
- Multiply the remainder (4) by the product (77) and the modular inverse (5):
- 4 * 77 * 5 = 1540
For remainder 8:
- Compute the product of all the divisors except for 11: 7 * 9 = 63.
- Find the modular inverse of 63 modulo 11.
- Let's find the value of x such that (63 * x) % 11 = 1.
- When we try different values of x, we find that x = 5 satisfies the equation.
- Multiply the remainder (8) by the product (63) and the modular inverse (5):
- 8 * 63 * 5 = 2520
Step 4: Add up the results from all the remainders:
1188 + 1540 + 2520 = 5258
Step 5: Find the smallest positive integer that satisfies the given conditions:
To find the smallest positive integer equivalent to 5258 modulo 693, we can repeatedly subtract 693 from 5258 until we reach the smallest non-negative value. This can be done by dividing 5258 by 693 and taking the remainder:
5258 % 693 = 191
So, the least positive integer that satisfies the conditions is 191.
Therefore, 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 is 191.