Crt Solution Ffd24D
1. **State the problem:** Solve the system of congruences using the Chinese Remainder Theorem (CRT):
$$x \equiv 11 \pmod{11}$$
$$x \equiv 2 \pmod{12}$$
$$x \equiv 4 \pmod{13}$$
2. **Recall the Chinese Remainder Theorem:**
If the moduli are pairwise coprime, the system has a unique solution modulo the product of the moduli.
3. **Check moduli:**
$$11, 12, 13$$ are pairwise coprime since \(\gcd(11,12)=1\), \(\gcd(11,13)=1\), and \(\gcd(12,13)=1\).
4. **Calculate the product of moduli:**
$$N = 11 \times 12 \times 13 = 1716$$
5. **Calculate partial products:**
$$N_1 = \frac{N}{11} = 156$$
$$N_2 = \frac{N}{12} = 143$$
$$N_3 = \frac{N}{13} = 132$$
6. **Find modular inverses:**
Find \(M_i\) such that \(N_i M_i \equiv 1 \pmod{n_i}\):
- For \(N_1=156\) mod 11:
$$156 \equiv 2 \pmod{11}$$
Solve \(2M_1 \equiv 1 \pmod{11}\) gives \(M_1 = 6\) because \(2 \times 6 = 12 \equiv 1 \pmod{11}\).
- For \(N_2=143\) mod 12:
$$143 \equiv 11 \pmod{12}$$
Solve \(11M_2 \equiv 1 \pmod{12}\) gives \(M_2 = 11\) because \(11 \times 11 = 121 \equiv 1 \pmod{12}\).
- For \(N_3=132\) mod 13:
$$132 \equiv 2 \pmod{13}$$
Solve \(2M_3 \equiv 1 \pmod{13}\) gives \(M_3 = 7\) because \(2 \times 7 = 14 \equiv 1 \pmod{13}\).
7. **Construct solution:**
$$x \equiv \sum_{i=1}^3 a_i N_i M_i \pmod{N}$$
where \(a_1=11, a_2=2, a_3=4\).
Calculate:
$$x \equiv 11 \times 156 \times 6 + 2 \times 143 \times 11 + 4 \times 132 \times 7 \pmod{1716}$$
$$= 11 \times 936 + 2 \times 1573 + 4 \times 924$$
$$= 10296 + 3146 + 3696 = 17138$$
8. **Reduce modulo 1716:**
$$x \equiv 17138 \pmod{1716}$$
Divide 17138 by 1716:
$$17138 = 1716 \times 9 + 1342$$
So,
$$x \equiv 1342 \pmod{1716}$$
**Final answer:**
$$\boxed{x \equiv 1342 \pmod{1716}}$$
This means all integers congruent to 1342 modulo 1716 satisfy the system.