Chinese remainder theorem (intro) - Discrete Math

1. Consider solving $x ≡ 3 \pmod{8}$ and $x ≡ 7 \pmod{12}$ using CRT. Since $\gcd(8,12) = 4$, we first check compatibility. Given that the system has a solution, what is $x \bmod{6}$?
   Answer: $x ≡ 1 \pmod{6}$ since the unique solution modulo $24$ can be reduced to find the remainder when divided by $6$ First verify compatibility: $3 ≡ 3 \pmod{4}$ and $7 ≡ 3 \pmod{4}$, so the system has a solution. From $x ≡ 3 \pmod{8}$, we have $x = 8k + 3$. Substituting into the second: $8k + 3 ≡ 7 \pmod{12}$, so $8k ≡ 4 \pmod{12}$, which gives $2k ≡ 1 \pmod{3}$. Since $2 \cdot 2 = 4 ≡ 1 \pmod{3}$, we have $k ≡ 2 \pmod{3}$. So $k = 3j + 2$ and $x = 8(3j + 2) + 3 = 24j + 19$. Thus $x ≡ 19 \pmod{24}$. Finally, $19 = 3 \cdot 6 + 1$, so $x ≡ 1 \pmod{6}$. The other options give incorrect remainders.
2. The system $x ≡ a \pmod{6}$ and $x ≡ b \pmod{10}$ has a unique solution modulo $30$ when $a = 2$ and $b = 12$. If we change $b$ to $b' = 22$, what happens to the system?
   Answer: The system has a unique solution modulo $30$ since $2 ≡ 0 \pmod{2}$ and $22 ≡ 0 \pmod{2}$, satisfying compatibility requirements Since $\gcd(6,10) = 2$, we need $a ≡ b' \pmod{2}$ for a solution to exist. We have $a = 2 ≡ 0 \pmod{2}$ and $b' = 22 ≡ 0 \pmod{2}$. Since both are congruent to $0$ modulo $2$, the compatibility condition is satisfied and there is a unique solution modulo $\text{lcm}(6,10) = 30$. A is wrong because $22 ≡ 0 \pmod{2}$, not $2 \pmod{2}$. B is wrong because $2 ≡ 0 \pmod{2}$, not $2 \pmod{2}$. D is wrong because when the compatibility condition is met, there is exactly one solution modulo the lcm.
3. A system of congruences has solutions $x \equiv 2 \pmod{5}$ and $x \equiv 3 \pmod{7}$. If we add a third congruence $x \equiv a \pmod{11}$ where $0 \leq a \leq 10$, which value of $a$ would make the system inconsistent?
   Answer: No value of $a$ can make the system inconsistent due to pairwise coprimality The Chinese Remainder Theorem guarantees a unique solution modulo $5 \cdot 7 \cdot 11 = 385$ when the moduli are pairwise coprime. Since $\gcd(5,7) = \gcd(5,11) = \gcd(7,11) = 1$, any value of $a$ from 0 to 10 will result in a consistent system. The solution to the first two congruences is $x \equiv 17 \pmod{35}$, and adding any third congruence with modulus 11 will have exactly one solution modulo 385. Choice A is incorrect because it mentions $\gcd(5,7,11)$ which is not the relevant condition. Choice B incorrectly assumes a contradiction based on the value equaling a modulus. Choice C incorrectly suggests CRT conditions can be violated.
4. A student solving $x ≡ 4 \pmod{9}$ and $x ≡ 6 \pmod{15}$ writes $x = 9s + 4$ for some integer $s$, then substitutes to get $9s + 4 ≡ 6 \pmod{15}$. Simplifying gives $9s ≡ 2 \pmod{15}$. What is the next step?
   Answer: Recognize that $\gcd(9,15) = 3$ and $3 \nmid 2$, so the original system is inconsistent and has no integer solutions The congruence $9s ≡ 2 \pmod{15}$ has a solution if and only if $\gcd(9,15)$ divides $2$. Since $\gcd(9,15) = 3$ and $3 \nmid 2$, this congruence has no solution. This means the original system is inconsistent. We can verify: if a solution existed, we'd need $4 ≡ 6 \pmod{\gcd(9,15)} = 4 ≡ 6 \pmod{3}$, but $4 ≡ 1 \pmod{3}$ while $6 ≡ 0 \pmod{3}$. A restates the same conclusion but suggests stopping calculation rather than understanding the inconsistency. B incorrectly suggests fractional congruences. D ignores the fundamental issue that $9$ has no multiplicative inverse modulo $15$.
5. A student attempts to solve $x ≡ 3 \pmod{14}$ and $x ≡ 8 \pmod{21}$ by first reducing to $x ≡ 3 \pmod{14}$ and $x ≡ 8 \pmod{21}$, then noting that $\gcd(14,21) = 7$. The student concludes the system has no solution because $3 ≢ 8 \pmod{7}$. What is the error in the student's reasoning process?
   Answer: The compatibility check is wrong since $3 ≡ 3 \pmod{7}$ and $8 ≡ 1 \pmod{7}$, and $3 ≢ 1 \pmod{7}$ means no solution The student correctly found $\gcd(14,21) = 7$. For compatibility, we need $3 ≡ 8 \pmod{7}$. Computing: $3 ≡ 3 \pmod{7}$ and $8 = 1 \cdot 7 + 1 ≡ 1 \pmod{7}$. Since $3 ≢ 1 \pmod{7}$, the system has no solution. The student's conclusion is correct, but choice B correctly identifies that the error was in not explicitly showing the modular arithmetic calculations that justify the incompatibility. A is wrong because $\gcd(14,21) = 7 ≠ 1$. C suggests an arithmetic error that wasn't made. D incorrectly suggests the reasoning was complete when the specific calculations were omitted.
6. Consider the system $x ≡ a \pmod{12}$ and $x ≡ b \pmod{20}$ where $a$ and $b$ are chosen so that a solution exists. If the solution is $x ≡ 16 \pmod{60}$, which of the following could be the values of $a$ and $b$?
   Answer: $a = 4$ and $b = 16$ since $16 ≡ 4 \pmod{12}$ and $16 ≡ 16 \pmod{20}$ with proper compatibility conditions When you encounter a system of linear congruences, you're working with the Chinese Remainder Theorem. The key insight is that if $x ≡ 16 \pmod{60}$, then this value of $x$ must also satisfy both original congruences when you reduce modulo 12 and 20 respectively. Let's check what $x = 16$ gives us in each modulus. For the first congruence: $16 ≡ 4 \pmod{12}$ (since $16 = 12 + 4$). For the second congruence: $16 ≡ 16 \pmod{20}$ (since $16 < 20$). Therefore, we need $a = 4$ and $b = 16$. Let's verify why the other options fail. Option A claims $a = 16$ and $b = 4$, but $16 ≡ 4 \pmod{12}$, so $a$ should be 4, not 16. More critically, if $b = 4$, then $x ≡ 4 \pmod{20}$, which contradicts our solution where $x ≡ 16 \pmod{20}$. Option B suggests $a = 8$ and $b = 12$, but $16 ≢ 8 \pmod{12}$ and $16 ≢ 12 \pmod{20}$. Option C proposes $b = 8$, but $16 ≢ 8 \pmod{20}$. Only option D gives the correct values: $a = 4$ and $b = 16$, which directly correspond to reducing our solution $x ≡ 16 \pmod{60}$ under each modulus. Strategy tip: When verifying solutions to congruence systems, always check that your proposed solution satisfies each individual congruence by direct substitution and modular reduction.
7. A number leaves remainder 3 when divided by 8, remainder 5 when divided by 9, and remainder 7 when divided by 11. What is the smallest positive integer greater than 1000 that satisfies these conditions?
   Answer: 1211 We solve $x \equiv 3 \pmod{8}$, $x \equiv 5 \pmod{9}$, $x \equiv 7 \pmod{11}$. Since $\gcd(8,9) = \gcd(8,11) = \gcd(9,11) = 1$, CRT applies. The solution exists modulo $8 \cdot 9 \cdot 11 = 792$. Using CRT: $M_1 = 99$, $M_2 = 88$, $M_3 = 72$. We need $99y_1 \equiv 1 \pmod{8}$: $99 \equiv 3 \pmod{8}$, so $3y_1 \equiv 1 \pmod{8}$, giving $y_1 = 3$ since $3 \cdot 3 = 9 \equiv 1 \pmod{8}$. For $88y_2 \equiv 1 \pmod{9}$: $88 \equiv 7 \pmod{9}$, so $7y_2 \equiv 1 \pmod{9}$, giving $y_2 = 4$ since $7 \cdot 4 = 28 \equiv 1 \pmod{9}$. For $72y_3 \equiv 1 \pmod{11}$: $72 \equiv 6 \pmod{11}$, so $6y_3 \equiv 1 \pmod{11}$, giving $y_3 = 2$ since $6 \cdot 2 = 12 \equiv 1 \pmod{11}$. Thus $x \equiv 3 \cdot 99 \cdot 3 + 5 \cdot 88 \cdot 4 + 7 \cdot 72 \cdot 2 = 891 + 1760 + 1008 = 3659 \equiv 419 \pmod{792}$. The smallest value greater than 1000 is $419 + 792 = 1211$.
8. Consider the system $x ≡ a \pmod{12}$ and $x ≡ b \pmod{18}$. For which values of $a$ and $b$ does this system have exactly one solution modulo $36$?
   Answer: Only when $a ≡ b \pmod{6}$ since $\gcd(12,18) = 6$ requires the remainders to be congruent modulo the gcd Since $\gcd(12,18) = 6$, the system has a solution if and only if $a ≡ b \pmod{6}$. When this condition holds, there is exactly one solution modulo $\text{lcm}(12,18) = 36$. This is the generalized Chinese Remainder Theorem for non-coprime moduli. A is wrong because it ignores the compatibility condition. C is wrong because parity alone isn't sufficient - we need congruence modulo 6. D is wrong because CRT can be extended to non-coprime moduli with the proper compatibility condition.
9. A system of congruences has solutions $x ≡ 2 \pmod{5}$ and $x ≡ 3 \pmod{7}$. If $x = 17$ is the unique solution modulo $35$, what happens when we add the congruence $x ≡ 1 \pmod{6}$ to this system?
   Answer: The system has no solution since $17 ≡ 5 \pmod{6}$ but we need $x ≡ 1 \pmod{6}$, creating an inconsistency First verify that $x = 17$ satisfies the original system: $17 ≡ 2 \pmod{5}$ (since $17 = 3 \cdot 5 + 2$) and $17 ≡ 3 \pmod{7}$ (since $17 = 2 \cdot 7 + 3$). Now check the new constraint: $17 ≡ 5 \pmod{6}$ (since $17 = 2 \cdot 6 + 5$). Since we need $x ≡ 1 \pmod{6}$ but $17 ≡ 5 \pmod{6}$, the system becomes inconsistent. A is wrong because it incorrectly focuses on coprimality without checking the actual constraint. B is wrong because it assumes $x = 17$ works without verification. D is wrong because CRT can handle multiple congruences when moduli are pairwise coprime.
10. A student applies the Chinese Remainder Theorem to solve $x ≡ 3 \pmod{7}$ and $x ≡ 5 \pmod{11}$ by finding $M_1 = 11$, $M_2 = 7$, then computing $y_1$ such that $11y_1 ≡ 1 \pmod{7}$. What is the value of $y_1$?
    Answer: $y_1 = 2$ since $11 ≡ 4 \pmod{7}$ and $4 \cdot 2 = 8 ≡ 1 \pmod{7}$ We need $11y_1 ≡ 1 \pmod{7}$. Since $11 ≡ 4 \pmod{7}$, we need $4y_1 ≡ 1 \pmod{7}$. Testing: $4 \cdot 2 = 8 ≡ 1 \pmod{7}$, so $y_1 = 2$. B is wrong because $4 \cdot 5 = 20 ≡ 6 \pmod{7} ≠ 1$. C is wrong because $4 \cdot 6 = 24 ≡ 3 \pmod{7} ≠ 1$. D is wrong because it confuses the process - we need the coefficient that makes the product ≡ 1, not ≡ 5.
11. In a CRT problem with $x ≡ a_1 \pmod{m_1}$, $x ≡ a_2 \pmod{m_2}$, and $x ≡ a_3 \pmod{m_3}$ where $m_1 = 7$, $m_2 = 11$, $m_3 = 13$, a student computes $M = 1001$ and $M_1 = 143$. What should $y_1$ satisfy?
    Answer: $143y_1 ≡ 1 \pmod{7}$ which simplifies to $3y_1 ≡ 1 \pmod{7}$ since $143 = 20 \cdot 7 + 3$ When solving systems of linear congruences using the Chinese Remainder Theorem (CRT), you need to find multiplicative inverses as part of the construction. The key insight is understanding what $y_1$ represents and which modular equation it must satisfy. In CRT, after computing $M = m_1 \cdot m_2 \cdot m_3 = 7 \cdot 11 \cdot 13 = 1001$ and $M_1 = \frac{M}{m_1} = \frac{1001}{7} = 143$, you need $y_1$ to be the multiplicative inverse of $M_1$ modulo $m_1$. This means $M_1 \cdot y_1 ≡ 1 \pmod{m_1}$, or $143y_1 ≡ 1 \pmod{7}$. Since $143 = 20 \cdot 7 + 3$, we have $143 ≡ 3 \pmod{7}$, so this reduces to $3y_1 ≡ 1 \pmod{7}$. Answer D correctly identifies this relationship. Answer A incorrectly sets up $My_1 ≡ M_1 \pmod{m_1}$ instead of $M_1y_1 ≡ 1 \pmod{m_1}$, and the resulting equation $0 \cdot y_1 ≡ 3 \pmod{7}$ has no solution, which should signal this approach is wrong. Answer B confuses the modulus - you don't need the inverse of $M_1$ modulo the entire product $M$, but modulo the individual $m_1$. Answer C reverses the roles, trying to find the inverse of $m_1$ modulo $M_1$ instead of $M_1$ modulo $m_1$. Study tip: In CRT problems, always remember that $y_i$ satisfies $M_i \cdot y_i ≡ 1 \pmod{m_i}$ - you're finding the inverse of the "big" number modulo the "small" modulus.
12. If $N$ is the unique solution modulo 60 to the system $x \equiv 7 \pmod{12}$, $x \equiv 11 \pmod{20}$, then what is the value of $N + 60$?
    Answer: 91, since the solution modulo 60 is 31 First, we check if a solution exists: $\gcd(12,20) = 4$ and we need $7 \equiv 11 \pmod{4}$. Since $7 \equiv 3 \pmod{4}$ and $11 \equiv 3 \pmod{4}$, the condition is satisfied. The solution exists modulo $\text{lcm}(12,20) = 60$. From $x \equiv 7 \pmod{12}$, we have $x = 12k + 7$ for some integer $k$. Substituting into the second congruence: $12k + 7 \equiv 11 \pmod{20}$, so $12k \equiv 4 \pmod{20}$, which gives $3k \equiv 1 \pmod{5}$ (dividing by $\gcd(12,20) = 4$). Since $3 \cdot 2 = 6 \equiv 1 \pmod{5}$, we have $k \equiv 2 \pmod{5}$, so $k = 5j + 2$. Therefore $x = 12(5j + 2) + 7 = 60j + 24 + 7 = 60j + 31$. Thus $N = 31$ and $N + 60 = 91$.
13. In applying CRT to find $x$ such that $x ≡ 2 \pmod{3}$, $x ≡ 1 \pmod{4}$, and $x ≡ 3 \pmod{5}$, a student first solves the subsystem $x ≡ 2 \pmod{3}$ and $x ≡ 1 \pmod{4}$, obtaining $x ≡ 5 \pmod{12}$. What is the final answer?
    Answer: $x ≡ 53 \pmod{60}$ after solving $x ≡ 5 \pmod{12}$ and $x ≡ 3 \pmod{5}$ using standard CRT methods We solve $x ≡ 5 \pmod{12}$ and $x ≡ 3 \pmod{5}$. Let $x = 12k + 5$. Then $12k + 5 ≡ 3 \pmod{5}$, so $12k ≡ -2 ≡ 3 \pmod{5}$. Since $12 ≡ 2 \pmod{5}$, we need $2k ≡ 3 \pmod{5}$. Since $2 \cdot 3 = 6 ≡ 1 \pmod{5}$, we have $k ≡ 3 \cdot 3 ≡ 4 \pmod{5}$. So $k = 5j + 4$ and $x = 12(5j + 4) + 5 = 60j + 53$. Thus $x ≡ 53 \pmod{60}$. Verify: $53 = 17 \cdot 3 + 2$, $53 = 13 \cdot 4 + 1$, $53 = 10 \cdot 5 + 3$. The other options give incorrect remainders when checked.
14. Consider the system $x ≡ 7 \pmod{15}$ and $x ≡ 4 \pmod{21}$. A student claims this has no solution because $\gcd(15,21) = 3$ and $7 \not≡ 4 \pmod{3}$. How should we evaluate this reasoning?
    Answer: The reasoning is incorrect since $7 ≡ 1 \pmod{3}$ and $4 ≡ 1 \pmod{3}$, so the compatibility condition is satisfied For the system to have a solution when $\gcd(15,21) = 3 ≠ 1$, we need $7 ≡ 4 \pmod{3}$. Computing: $7 = 2 \cdot 3 + 1$, so $7 ≡ 1 \pmod{3}$. Also $4 = 1 \cdot 3 + 1$, so $4 ≡ 1 \pmod{3}$. Since both remainders are congruent to $1$ modulo $3$, the compatibility condition is satisfied and a solution exists. A is wrong because it states the condition is satisfied but concludes no solution exists. C is wrong because the generalized CRT does apply to non-coprime moduli. D is wrong because checking $\gcd(m_1,m_2) | (a_1-a_2)$ is equivalent to checking $a_1 ≡ a_2 \pmod{\gcd(m_1,m_2)}$.

Start this quiz