Discrete Math Quiz: Chinese Remainder Theorem

14 questions · exam conditions

0:00

Chinese Remainder TheoremQuestion 1 of 14

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?

Since

\gcd(9,15) = 3

and

3 \nmid 2

, conclude that the system has no solution and stop the calculation process

Divide the entire congruence by

\gcd(9,15) = 3

to obtain

3s ≡ \frac{2}{3} \pmod{5}

, which requires fractional arithmetic

Recognize that

\gcd(9,15) = 3

and

3 \nmid 2

, so the original system is inconsistent and has no integer solutions

Find the multiplicative inverse of

9

modulo

15

by using the extended Euclidean algorithm, ignoring the gcd condition entirely

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Chinese Remainder Theorem

Practice Chinese Remainder Theorem in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Chinese Remainder Theorem, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

Since $\gcd(9,15) = 3$ and $3 \nmid 2$ , conclude that the system has no solution and stop the calculation process
Divide the entire congruence by $\gcd(9,15) = 3$ to obtain $3s ≡ \frac{2}{3} \pmod{5}$ , which requires fractional arithmetic
Recognize that $\gcd(9,15) = 3$ and $3 \nmid 2$ , so the original system is inconsistent and has no integer solutions (correct answer)
Find the multiplicative inverse of $9$ modulo $15$ by using the extended Euclidean algorithm, ignoring the gcd condition entirely

Explanation: 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

Question 2

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?

$x ≡ 53 \pmod{60}$ after solving $x ≡ 5 \pmod{12}$ and $x ≡ 3 \pmod{5}$ using standard CRT methods (correct answer)
$x ≡ 17 \pmod{60}$ since this is the smallest positive value satisfying all three original congruence conditions
$x ≡ 29 \pmod{60}$ obtained by systematically applying CRT to the reduced system with moduli $12$ and $5$
$x ≡ 41 \pmod{60}$ which represents the unique solution when combining the intermediate result with the third constraint

Explanation: 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.

Question 3

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$ ?

$y_1 = 2$ since $11 ≡ 4 \pmod{7}$ and $4 \cdot 2 = 8 ≡ 1 \pmod{7}$ (correct answer)
$y_1 = 5$ since we need the multiplicative inverse of $11$ modulo $7$ , which is $5$
$y_1 = 6$ since $11 ≡ 4 \pmod{7}$ and $4 \cdot 6 = 24 ≡ 3 \pmod{7}$
$y_1 = 3$ since $11 \cdot 3 = 33$ and $33 ≡ 5 \pmod{7}$ , matching our target remainder

Explanation: 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.

Question 4

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?

The system has no solution since $\gcd(5,6) = 1$ and $\gcd(7,6) = 1$ but the original solution fails the new constraint
The system has a unique solution modulo $210$ since all three moduli are pairwise coprime and $x = 17$ satisfies all conditions
The system has no solution since $17 ≡ 5 \pmod{6}$ but we need $x ≡ 1 \pmod{6}$ , creating an inconsistency (correct answer)
The system has infinitely many solutions since the Chinese Remainder Theorem doesn't apply when more than two congruences are present

Explanation: 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.

Question 5

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$ ?

$a = 16$ and $b = 4$ which reduces to $a = 4$ and $b = 4$ after taking appropriate modular reductions
$a = 8$ and $b = 12$ since these values satisfy the gcd compatibility requirement and give the stated solution
$a = 4$ and $b = 8$ since $16 ≡ 4 \pmod{12}$ and we need $b ≡ 4 \pmod{\gcd(12,20)}$ for consistency
$a = 4$ and $b = 16$ since $16 ≡ 4 \pmod{12}$ and $16 ≡ 16 \pmod{20}$ with proper compatibility conditions (correct answer)

Explanation: 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.

Question 6

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?

$1001y_1 ≡ 143 \pmod{7}$ which reduces to $0 \cdot y_1 ≡ 3 \pmod{7}$ giving no solution for $y_1$
$143y_1 ≡ 1 \pmod{1001}$ since we need the multiplicative inverse of $M_1$ modulo the total product $M$
$7y_1 ≡ 1 \pmod{143}$ since we're finding the inverse of $m_1$ modulo $M_1$ in the CRT construction
$143y_1 ≡ 1 \pmod{7}$ which simplifies to $3y_1 ≡ 1 \pmod{7}$ since $143 = 20 \cdot 7 + 3$ (correct answer)

Explanation: 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.

Question 7

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?

The gcd calculation is wrong since $\gcd(14,21) = 1$ , so the standard CRT applies and a unique solution exists
The compatibility check is wrong since $3 ≡ 3 \pmod{7}$ and $8 ≡ 1 \pmod{7}$ , and $3 ≢ 1 \pmod{7}$ means no solution (correct answer)
The student should have checked $3 ≡ 8 \pmod{7}$ but computed $8 \bmod 7$ incorrectly as $8$ instead of $1$
No computational error was made, but the student failed to show the specific modular arithmetic: $3 ≡ 3 \pmod{7}$ and $8 ≡ 1 \pmod{7}$

Explanation: 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.

Question 8

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?

There is no such value of $a$ since $\gcd(5,7,11) = 1$
$a = 5$ since this creates a contradiction with the modulus 5
$a = 9$ since this violates the Chinese Remainder Theorem conditions
No value of $a$ can make the system inconsistent due to pairwise coprimality (correct answer)

Explanation: 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.

Question 9

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?

1019
1211 (correct answer)
1403
1595

Explanation: 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

Question 10

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?

The reasoning is correct since $7 ≡ 1 \pmod{3}$ while $4 ≡ 1 \pmod{3}$ , creating the required incompatibility for no solution
The reasoning is incorrect since $7 ≡ 1 \pmod{3}$ and $4 ≡ 1 \pmod{3}$ , so the compatibility condition is satisfied (correct answer)
The reasoning is flawed because the Chinese Remainder Theorem doesn't apply when moduli share common factors like $15$ and $21$
The reasoning is partially correct but incomplete since we also need to check whether $\gcd(15,21)$ divides the difference $7-4$

Explanation: 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)}

Question 11

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}$ ?

$x ≡ 1 \pmod{6}$ since the unique solution modulo $24$ can be reduced to find the remainder when divided by $6$ (correct answer)
$x ≡ 3 \pmod{6}$ since this matches the remainder from the first congruence and satisfies the compatibility conditions
$x ≡ 5 \pmod{6}$ since the CRT solution modulo $\text{lcm}(8,12) = 24$ gives a remainder of $5$ when divided by $6$
$x ≡ 7 \pmod{6}$ which simplifies to $x ≡ 1 \pmod{6}$ since $7 ≡ 1 \pmod{6}$ from the second congruence

Explanation: 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.

Question 12

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?

The system still has a unique solution modulo $30$ since $22 ≡ 2 \pmod{\gcd(6,10)} = 2 \pmod{2}$ , maintaining compatibility
The system has no solution since $2 ≡ 2 \pmod{2}$ but $22 ≡ 0 \pmod{2}$ , violating the compatibility condition
The system has a unique solution modulo $30$ since $2 ≡ 0 \pmod{2}$ and $22 ≡ 0 \pmod{2}$ , satisfying compatibility requirements (correct answer)
The system becomes indeterminate since changing $b$ to an even value creates multiple solutions within the modulo $30$ range

Explanation: 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.

Question 13

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$ ?

All values of $a$ and $b$ since $\text{lcm}(12,18) = 36$ guarantees a unique solution modulo $36$ regardless of remainders
Only when $a ≡ b \pmod{6}$ since $\gcd(12,18) = 6$ requires the remainders to be congruent modulo the gcd (correct answer)
Only when $a$ and $b$ are both even since the system involves even moduli and requires compatible parity conditions
No values of $a$ and $b$ since the moduli $12$ and $18$ are not coprime, violating the Chinese Remainder Theorem

Explanation: 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.

Question 14

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$ ?

91, since the solution modulo 60 is 31 (correct answer)
111, since the solution modulo 60 is 51
131, since the solution modulo 60 is 71 reduced
151, since the solution modulo 60 is 91 reduced

Explanation: 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