Discrete Math Quiz: Solving Linear Congruences

18 questions · exam conditions

0:00

Solving Linear CongruencesQuestion 1 of 18

If $ax \equiv b \pmod{m}$ has solutions, and after finding one solution $x_0$ , the general solution is $x \equiv x_0 + \frac{m}{d} \cdot t \pmod{m}$ where $d = \gcd(a,m)$ . For the congruence $18x \equiv 12 \pmod{30}$ , what is the value of $\frac{m}{d}$ ?

\frac{m}{d} = 2

\frac{m}{d} = 5

\frac{m}{d} = 6

\frac{m}{d} = 10

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Solving Linear Congruences

Practice Solving Linear Congruences 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 Solving Linear Congruences, 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

$\frac{m}{d} = 2$
$\frac{m}{d} = 5$ (correct answer)
$\frac{m}{d} = 6$
$\frac{m}{d} = 10$

Explanation: Here

a = 18

m = 30

, so

d = \gcd(18,30) = 6

. Therefore

\frac{m}{d} = \frac{30}{6} = 5

. This means solutions are spaced 5 units apart modulo 30, and there are 6 distinct solutions modulo 30. Choice A uses

d = 15

incorrectly. Choice C uses

d

itself instead of

\frac{m}{d}

. Choice D uses

\frac{m}{\gcd(a,b)}

instead of

\frac{m}{\gcd(a,m)}

Question 2

A student attempts to solve $4x \equiv 6 \pmod{10}$ by finding $4^{-1} \pmod{10}$ and concludes no solution exists because gcd(4,10) ≠ 1. What is the error in this reasoning, and what is the correct approach?

The error is assuming no inverse exists; $4^{-1} \equiv 6 \pmod{10}$ and $x \equiv 9 \pmod{10}$
The error is not checking divisibility; since gcd(4,10) = 2 divides 6, solutions exist by reduction (correct answer)
The error is computational; $4^{-1} \equiv 4 \pmod{10}$ exists and gives $x \equiv 4 \pmod{10}$
No error exists; the congruence truly has no solutions since gcd(4,10) = 2 ≠ 1

Explanation: The student's error is applying the wrong test. When gcd(a,m) ≠ 1, we cannot find a multiplicative inverse of

a

modulo

m

, but this doesn't mean the congruence

ax \equiv b \pmod{m}

has no solutions. The correct test is whether gcd(a,m) divides

b

. Here gcd(4,10) = 2, and since 2 divides 6, solutions exist. We reduce by dividing by 2:

2x \equiv 3 \pmod{5}

. Since

2 \cdot 3 \equiv 1 \pmod{5}

, we get

x \equiv 3 \cdot 3 \equiv 4 \pmod{5}

. The solutions modulo 10 are

\{4,9\}

. Choice A incorrectly claims an inverse exists. Choice C makes a computational error. Choice D accepts the wrong reasoning.

Question 3

If $x_1$ is a particular solution to $ax \equiv b \pmod{m}$ , then all solutions are given by $x \equiv x_1 + kt \pmod{m}$ where $t = \frac{m}{\gcd(a,m)}$ and $k$ ranges over integers. For $6x \equiv 9 \pmod{15}$ , what is the value of $t$ ?

$t = 3$
$t = 5$ (correct answer)
$t = 6$
$t = 15$

Explanation: Here

a = 6

and

m = 15

, so

\gcd(6,15) = 3

. Therefore

t = \frac{m}{\gcd(a,m)} = \frac{15}{3} = 5

. This means that if

x_1

is one solution, then

x_1, x_1+5, x_1+10

are the three distinct solutions modulo 15. Choice A gives the gcd itself rather than the quotient. Choice C uses the coefficient

a

instead of the correct formula. Choice D uses the modulus

m

instead of the quotient.

Question 4

For what values of $k$ does the system of congruences $x \equiv 5 \pmod{8}$ and $x \equiv k \pmod{12}$ have a solution?

$k \equiv 1 \pmod{4}$ or $k \equiv 5 \pmod{4}$
$k \equiv 5 \pmod{4}$ only
$k \equiv 1, 5, 9 \pmod{12}$ (correct answer)
All values of $k$ work

Explanation: For the system to have a solution, we need

5 \equiv k \pmod{\gcd(8,12)} = \gcd(8,12) = 4

. So we need

5 \equiv k \pmod{4}

, which means

k \equiv 1 \pmod{4}

. Among values

0 \leq k \leq 11

, we have

k \in \{1,5,9\}

. Choice A incorrectly includes

k \equiv 5 \pmod{4}

, but

5 \equiv 1 \pmod{4}

. Choice B is too restrictive. Choice D is incorrect since not all values work (e.g.,

k = 0

doesn't work since

5 \not\equiv 0 \pmod{4}

Question 5

If $\gcd(a,15) = 3$ and the congruence $ax \equiv 9 \pmod{15}$ has solutions, how many solutions does it have modulo $15$ ?

$1$ solution
$15$ solutions
$5$ solutions
$3$ solutions (correct answer)

Explanation: When you encounter a linear congruence

ax \equiv b \pmod{m}

, the number of solutions depends on the relationship between

\gcd(a,m)

and

b

. If

\gcd(a,m)

divides

b

, then there are exactly

\gcd(a,m)

solutions modulo

m

. In this problem, we're given

\gcd(a,15) = 3

and the congruence

ax \equiv 9 \pmod{15}

. First, let's verify that solutions exist: since

3

divides

9

(because

9 = 3 \times 3

), the congruence indeed has solutions. Now we can apply the theorem: the number of solutions modulo

15

equals

\gcd(a,15) = 3

. This happens because when

\gcd(a,m) = d > 1

, we can reduce the congruence by dividing through by

d

, which creates

d

distinct solution classes modulo

m

. Looking at the wrong answers: Choice A suggests only

1

solution, which would only be true if

\gcd(a,15) = 1

, meaning

a

and

15

were coprime. Choice B claims

15

solutions, but you can never have more solutions than the modulus itself, and this would require every residue class to be a solution. Choice C suggests

5

solutions, which might tempt you if you incorrectly calculated

15/3 = 5

, but that's not how the theorem works. Remember this key principle: for linear congruences

ax \equiv b \pmod{m}

, when solutions exist, the number of solutions always equals

\gcd(a,m)

. Check divisibility first, then apply this formula directly.

Question 6

The congruence $15x \equiv 10 \pmod{25}$ can be solved by first reducing it. After proper reduction, what multiplicative inverse is needed, and what is the final answer?

Need inverse of 3 mod 5; answer is $x \equiv 4 \pmod{5}$ (correct answer)
Need inverse of 15 mod 25; answer is $x \equiv 10 \pmod{25}$
Need inverse of 3 mod 5; answer is $x \equiv 19 \pmod{25}$
Need inverse of 5 mod 25; answer is $x \equiv 2 \pmod{5}$

Explanation: First, we find gcd(15,10,25) = 5 and divide the entire congruence by 5:

3x \equiv 2 \pmod{5}

. We need the multiplicative inverse of 3 modulo 5. Since

3 \cdot 2 = 6 \equiv 1 \pmod{5}

, we have

3^{-1} \equiv 2 \pmod{5}

. Therefore

x \equiv 2 \cdot 2 \equiv 4 \pmod{5}

. Choice B attempts to solve without reduction. Choice C identifies the correct inverse but gives an incorrect final answer. Choice D incorrectly identifies which inverse is needed after reduction.

Question 7

For which value of $a$ does the linear congruence $6x \equiv a \pmod{15}$ have exactly one solution modulo 15?

The congruence never has exactly one solution modulo 15 (correct answer)
$a = 3$ gives exactly one solution modulo 15
$a = 6$ gives exactly one solution modulo 15
$a = 9$ gives exactly one solution modulo 15

Explanation: Since gcd(6,15) = 3, the congruence

6x \equiv a \pmod{15}

has solutions if and only if

3 | a

. When solutions exist, there are exactly gcd(6,15) = 3 distinct solutions modulo 15. The congruence cannot have exactly one solution modulo 15 because when it has solutions, it always has exactly 3 solutions. Choices B, C, and D incorrectly assume that certain values of

a

can yield a unique solution, but this violates the fundamental theorem about the number of solutions to linear congruences.

Question 8

The congruence $21x \equiv 14 \pmod{35}$ has multiple solutions. After reducing to lowest terms, how many distinct solutions exist modulo 35?

1 solution modulo 35
5 solutions modulo 35
7 solutions modulo 35 (correct answer)
No solutions exist

Explanation: First find gcd(21,35) = 7. Since 7 divides 14, solutions exist. The number of solutions modulo 35 is gcd(21,35) = 7. To find them, we first reduce: divide by 7 to get

3x \equiv 2 \pmod{5}

. Since gcd(3,5) = 1, this has exactly one solution modulo 5. We find

3^{-1} \equiv 2 \pmod{5}

, so

x \equiv 4 \pmod{5}

. The 7 solutions modulo 35 are:

x \equiv 4, 9, 14, 19, 24, 29, 34 \pmod{35}

. Choice A assumes the reduced congruence gives the total count. Choice B incorrectly uses gcd(21,14). Choice D incorrectly concludes no solutions exist.

Question 9

The linear congruence $12x \equiv 8 \pmod{20}$ can be simplified before solving. What is the correct simplified form and its smallest positive solution?

$3x \equiv 2 \pmod{5}$ ; solution $x = 4$ (correct answer)
$6x \equiv 4 \pmod{10}$ ; solution $x = 4$
$3x \equiv 2 \pmod{5}$ ; solution $x = 9$
$4x \equiv 2 \pmod{5}$ ; solution $x = 3$

Explanation: We can divide the entire congruence by gcd(12,8,20) = 4 to get

3x \equiv 2 \pmod{5}

. To solve this, we need the multiplicative inverse of 3 modulo 5. Since

3 \cdot 2 = 6 \equiv 1 \pmod{5}

, we have

3^{-1} \equiv 2 \pmod{5}

. Therefore

x \equiv 2 \cdot 2 \equiv 4 \pmod{5}

, giving the smallest positive solution

x = 4

. Choice B fails to simplify completely. Choice C uses the correct simplified form but makes an error in finding the inverse. Choice D incorrectly simplifies the original congruence.

Question 10

Consider $9x \equiv 6 \pmod{15}$ . This congruence can be simplified, but one must be careful about the modulus. What is the correct approach and final answer?

Cannot be simplified; solve $9x \equiv 6 \pmod{15}$ directly
Divide by 3: $3x \equiv 2 \pmod{15}$ ; solution $x \equiv 4 \pmod{15}$
Divide by 3: $3x \equiv 2 \pmod{5}$ ; solution $x \equiv 4 \pmod{5}$ (correct answer)
Divide by 9: $x \equiv \frac{2}{3} \pmod{15}$ ; solution undefined

Explanation: When solving linear congruences, you can often simplify by dividing out common factors, but you must adjust the modulus correctly to maintain equivalence. For

9x \equiv 6 \pmod{15}

, notice that

\gcd(9, 6, 15) = 3

. Since 3 divides all terms, you can divide the entire congruence by 3. This gives you

3x \equiv 2 \pmod{?}

, but here's the crucial part: the modulus must also be divided by 3, becoming

3x \equiv 2 \pmod{5}

. To solve

3x \equiv 2 \pmod{5}

, you need the multiplicative inverse of 3 modulo 5. Since

3 \cdot 2 = 6 \equiv 1 \pmod{5}

, the inverse is 2. Multiplying both sides by 2:

x \equiv 2 \cdot 2 \equiv 4 \pmod{5}

. This makes C correct. Option A is wrong because the congruence can indeed be simplified when there's a common factor. Option B makes the critical error of dividing the coefficients by 3 but keeping the original modulus 15 unchanged—this fundamentally alters the congruence relationship. While B's final answer

x \equiv 4 \pmod{15}

happens to contain solutions, it's not the complete solution set. Option D attempts invalid division since 9 and 15 aren't coprime, and fractions don't work directly in modular arithmetic without finding multiplicative inverses. Key strategy: When simplifying linear congruences by dividing out common factors, always divide the modulus by the same factor. The solutions to the simplified congruence will be the same as the original, just with a smaller modulus.

Question 11

If $5x \equiv 7 \pmod{12}$ and we know that $5 \cdot 5 \equiv 1 \pmod{12}$ , then all solutions to the congruence in the range $0 \leq x < 36$ are:

$x \in \{5, 17, 29\}$
$x \in \{7, 19, 31\}$
$x \in \{11, 23, 35\}$ (correct answer)
$x \in \{11, 23\}$ only

Explanation: When you encounter linear congruences like

5x \equiv 7 \pmod{12}

, you need to find the multiplicative inverse of the coefficient to isolate

x

. The problem helpfully tells you that

5 \cdot 5 \equiv 1 \pmod{12}

, meaning 5 is the multiplicative inverse of 5 modulo 12. To solve for

x

, multiply both sides by 5:

5 \cdot 5x \equiv 5 \cdot 7 \pmod{12}

25x \equiv 35 \pmod{12}

Since

25 \equiv 1 \pmod{12}

and

35 \equiv 11 \pmod{12}

x \equiv 11 \pmod{12}

This means

x = 11 + 12k

for any integer

k

. In the range

0 \leq x < 36

When $k = 0$ : $x = 11$
When $k = 1$ : $x = 23$
When $k = 2$ : $x = 35$

So the complete solution set is

\{11, 23, 35\}

, which is answer C. Let's check why the other options fail: Answer A gives

\{5, 17, 29\}

, but

5 \cdot 5 = 25 \equiv 1 \pmod{12}

, not 7. Answer B gives

\{7, 19, 31\}

, but

5 \cdot 7 = 35 \equiv 11 \pmod{12}

, not 7. Answer D only includes

\{11, 23\}

but misses

x = 35

, which is still in the specified range. Study tip: Always find all solutions within the given range by adding the modulus repeatedly to your base solution. Don't stop early—check that your largest solution is still less than the upper bound.

Question 12

The linear congruence $8x \equiv 12 \pmod{20}$ requires careful analysis. Which statement about this congruence is correct?

It has no solutions because gcd(8,20) = 4 does not divide 12
It has exactly 4 solutions modulo 20: $\{4, 9, 14, 19\}$
It has exactly 4 solutions modulo 20: $\{3, 8, 13, 18\}$
It simplifies to $2x \equiv 3 \pmod{5}$ with solution $x \equiv 4 \pmod{5}$ (correct answer)

Explanation: First, gcd(8,20) = 4. Since 4 divides 12, solutions exist. We can divide the entire congruence by 4:

2x \equiv 3 \pmod{5}

. To solve this, we need

2^{-1} \pmod{5}

. Since

2 \cdot 3 = 6 \equiv 1 \pmod{5}

, we have

2^{-1} \equiv 3

. Thus

x \equiv 3 \cdot 3 \equiv 9 \equiv 4 \pmod{5}

. The complete solution set modulo 20 is

\{4, 9, 14, 19\}

. Choice A incorrectly claims no solutions exist. Choice B gives the correct solution set but doesn't explain the simplification. Choice C gives an incorrect solution set.

Question 13

Consider the linear congruence $7x \equiv 3 \pmod{15}$ . After finding the multiplicative inverse of $7$ modulo $15$ , what is the smallest non-negative solution for $x$ ?

$x = 6$
$x = 9$ (correct answer)
$x = 21$
$x = 12$

Explanation: First, we need to find the multiplicative inverse of 7 modulo 15. Using the extended Euclidean algorithm: gcd(7,15) = 1, so the inverse exists. We find that

7 \cdot 13 \equiv 91 \equiv 1 \pmod{15}

, so

7^{-1} \equiv 13 \pmod{15}

. Multiplying both sides of the original congruence by 13:

x \equiv 13 \cdot 3 \equiv 39 \equiv 9 \pmod{15}

. Choice A results from incorrectly using 6 as the inverse of 7. Choice C is the unreduced form of 39. Choice D results from using 12 as the inverse of 7.

Question 14

Consider the congruence $4x \equiv 6 \pmod{10}$ . Which statement correctly describes the solution set?

The congruence has a unique solution modulo $10$
The congruence has exactly two solutions modulo $10$ (correct answer)
The congruence has no solutions
The congruence has exactly five solutions modulo $10$

Explanation: First check if solutions exist:

\gcd(4,10) = 2

. Since

2

divides

6

, solutions exist. The number of solutions modulo

10

\gcd(4,10) = 2

. To find them, reduce by dividing by

2

2x \equiv 3 \pmod{5}

. Since

\gcd(2,5) = 1

, this has a unique solution modulo

5

. The inverse of

2

modulo

5

3

(since

2 \cdot 3 = 6 \equiv 1 \pmod{5}

), so

x \equiv 3 \cdot 3 \equiv 9 \equiv 4 \pmod{5}

. The solutions modulo

10

are

x \in \{4, 9\}

. Choice A is wrong because there are two solutions, not one. Choice C is wrong because solutions exist. Choice D is wrong because there are only two solutions.

Question 15

Consider the linear congruence $7x \equiv 3 \pmod{15}$ . After determining whether this congruence has solutions, what is the smallest positive integer $x$ that satisfies it?

$x = 6$
$x = 9$ (correct answer)
$x = 12$
No solution exists

Explanation: First, we check if solutions exist by finding

\gcd(7,15) = 1

. Since

\gcd(7,15) = 1

divides

3

, solutions exist. To solve

7x \equiv 3 \pmod{15}

, we need the multiplicative inverse of

7

modulo

15

. Using the extended Euclidean algorithm:

15 = 2 \cdot 7 + 1

, so

1 = 15 - 2 \cdot 7

. This means

7^{-1} \equiv -2 \equiv 13 \pmod{15}

. Therefore

x \equiv 3 \cdot 13 \equiv 39 \equiv 9 \pmod{15}

. Choice A gives

7 \cdot 6 = 42 \equiv 12 \pmod{15}

. Choice C gives

7 \cdot 12 = 84 \equiv 9 \pmod{15}

. Choice D is incorrect since

\gcd(7,15) = 1

divides

3

Question 16

The linear congruence $12x \equiv 8 \pmod{20}$ is equivalent to which of the following simplified congruences?

$3x \equiv 2 \pmod{5}$ (correct answer)
$3x \equiv 2 \pmod{20}$
$6x \equiv 4 \pmod{10}$
$4x \equiv 8 \pmod{5}$

Explanation: To simplify

12x \equiv 8 \pmod{20}

, we first find

\gcd(12, 8, 20) = 4

. Dividing through by

4

\frac{12}{4}x \equiv \frac{8}{4} \pmod{\frac{20}{4}}

, which gives

3x \equiv 2 \pmod{5}

. Choice B fails to reduce the modulus. Choice C only divides by

2

instead of

4

, giving

6x \equiv 4 \pmod{10}

. Choice D incorrectly computes the coefficients after division.

Question 17

For which value of $a$ does the congruence $6x \equiv a \pmod{9}$ have exactly three solutions modulo $9$ ?

$a = 0$
$a = 3$ (correct answer)
$a = 6$
$a = 1$

Explanation: Since

\gcd(6,9) = 3

, the congruence

6x \equiv a \pmod{9}

has solutions if and only if

3

divides

a

. When solutions exist, there are exactly

\gcd(6,9) = 3

solutions modulo

9

. For

a = 3

: since

3

divides

3

, we get

3

solutions. The simplified congruence is

2x \equiv 1 \pmod{3}

, giving

x \equiv 2 \pmod{3}

, so

x \in \{2, 5, 8\}

modulo

9

. Choice A gives

3

solutions but asks for

a = 0

. Choice C gives

3

solutions but

a = 6

. Choice D: since

3

does not divide

1

, there are no solutions.

Question 18

The congruence $21x \equiv 14 \pmod{35}$ simplifies to $3x \equiv 2 \pmod{5}$ . What is the complete solution set for $x$ in the original congruence?

$x \equiv 4 \pmod{5}$
$x \equiv 9, 16, 23, 30, 2 \pmod{35}$
$x \equiv 4 \pmod{35}$
$x \equiv 4, 9, 14, 19, 24, 29, 34 \pmod{35}$ (correct answer)

Explanation: When you encounter a linear congruence that simplifies to a smaller modulus, you need to find all solutions in the original modulus. The key insight is that solutions repeat in a predictable pattern based on the greatest common divisor. Starting with the simplified congruence

3x \equiv 2 \pmod{5}

, you can solve this by finding the multiplicative inverse of 3 modulo 5. Since

3 \cdot 2 = 6 \equiv 1 \pmod{5}

, the inverse is 2. Multiplying both sides by 2 gives

x \equiv 4 \pmod{5}

. This means

x = 4, 9, 14, 19, 24, 29, 34

are all solutions modulo 35. Here's why: when you simplified

21x \equiv 14 \pmod{35}

by dividing by

\gcd(21, 14, 35) = 7

, you created a congruence with fewer solutions. The original congruence has solutions that are spaced

\frac{35}{7} = 5

units apart, giving you exactly 7 solutions in the range 0 to 34. Answer choice A gives only the simplified solution

x \equiv 4 \pmod{5}

, missing that you need all solutions modulo 35. Choice B lists random values that don't follow the pattern of adding 5 repeatedly. Choice C suggests only one solution modulo 35, but when

\gcd(21, 35) = 7 > 1

, there are multiple solutions. Remember: when a linear congruence simplifies due to a common factor, the number of solutions in the original modulus equals that common factor. Always check your pattern by substituting back into the original congruence.