Find all numbers $r$ for which the system of congruences:
x == r mod 6
x == 9 mod 20
x == 4 mod 45
has a solution.
as google will provide, there are many similar exercises online. You might start here:
http://math.stackexchange.com/questions/79282/solving-simultaneous-congruences
To find the numbers $r$ for which the given system of congruences has a solution, we can use the Chinese Remainder Theorem (CRT).
The Chinese Remainder Theorem states that if we have a system of congruences in the form:
x ≡ a (mod m)
x ≡ b (mod n)
x ≡ c (mod p)
with pairwise coprime moduli m, n, and p, then the system has a unique solution modulo the product of the moduli (in this case, mnp).
In the given system, the moduli 6, 20, and 45 are not pairwise coprime. However, we can still apply the Chinese Remainder Theorem by breaking down the problem into smaller systems with pairwise coprime moduli:
System 1:
x ≡ r (mod 6)
x ≡ 9 (mod 20)
System 2:
x ≡ r (mod 6)
x ≡ 4 (mod 45)
System 3:
x ≡ 9 (mod 20)
x ≡ 4 (mod 45)
We can solve each of these smaller systems independently using the Chinese Remainder Theorem.
For System 1, the moduli 6 and 20 are coprime because their greatest common divisor (GCD) is 2. Hence, this smaller system has a solution for any value of r.
For System 2, the moduli 6 and 45 are coprime because their GCD is 3. Therefore, this smaller system also has a solution for any value of r.
For System 3, the moduli 20 and 45 are not coprime since their GCD is 5. This means that System 3 may or may not have solutions depending on the congruence conditions.
To summarize, in order for the original system of congruences to have a solution, all three smaller systems must have solutions. Therefore, any value of r will work except those that lead to System 3 having no solution.
To determine which values of r lead to System 3 having no solution, we can set up a linear Diophantine equation using the modulo conditions:
9 + 20k = 4 + 45m
Subtracting the common term on both sides:
20k - 45m = -5
We can solve this equation using the Extended Euclidean Algorithm or by inspection. The general solution for this equation is:
k = 27t + 9
m = 12t + 4
Where t is an integer.
This means that for every integer t, there exists a solution to System 3. Therefore, all values of r will work for the original system of congruences.
In conclusion, the original system of congruences has a solution for all real numbers r.