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.
The answer must appear on all these lists:
498, 493, 488, 483,... 13, 8, 3.
492, 483, 474, 465,... 24, 15, 6.
492, 481, 470, 459,... 30, 19, 8.
It must end in 8 or 3 to be on the first list.
Numbers in the second list that end in 8 or 3 are:
483, 438, 393, 348, 303, 258, 213, 168, 123, 78, 33.
Numbers on the third list that end in 3 or 8 are:
448, 393, 338, 283, 228, 173, 118, 63, 8
393 is the only number on all lists.
This is rather a "brute force" method, but it works.
To find a positive integer that satisfies all these conditions, we can use the Chinese Remainder Theorem, which states that if we have a set of congruences with pairwise coprime moduli, there will always be a unique solution modulo the product of the moduli.
Let's set up the congruences:
x ≡ 3 (mod 5)
x ≡ 6 (mod 9)
x ≡ 8 (mod 11)
First, let's find the product of the moduli: 5 * 9 * 11 = 495.
To find the unique solution modulo 495, we can start by finding the solutions modulo each modulus individually.
For x ≡ 3 (mod 5):
The solutions are 3, 8, 13, 18, ...
For x ≡ 6 (mod 9):
The solutions are 6, 15, 24, 33, ...
For x ≡ 8 (mod 11):
The solutions are 8, 19, 30, 41, ...
Now, we need to find a solution that satisfies all three congruences. To do this, we can check each solution modulo 495 (the product of the moduli) until we find one that satisfies all the congruences.
Let's take the first solution from each congruence and check:
x = 3 (mod 5)
x = 6 (mod 9)
x = 8 (mod 11)
Checking modulo 495, we have:
3 ≡ 3 (mod 5)
3 ≡ 6 (mod 9)
3 ≡ 8 (mod 11)
This is not a valid solution since 3 is not congruent to 6 modulo 9. Let's try the next solution:
x = 8 (mod 5)
x = 15 (mod 9)
x = 8 (mod 11)
Checking modulo 495, we have:
8 ≡ 3 (mod 5)
15 ≡ 6 (mod 9)
8 ≡ 8 (mod 11)
This is also not a valid solution since 8 is not congruent to 15 modulo 9.
We will continue this process until we find a valid solution that satisfies all three congruences modulo 495.