Solving linear congruences (intro) - Discrete Math

The linear congruence $12x \equiv 8 \pmod{20}$ can be simplified before solving. What is the correct simplified form and its smallest positive solution?
Answer: $3x \equiv 2 \pmod{5}$ ; solution $x = 4$ 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.
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}$ ?
Answer: $\frac{m}{d} = 5$ 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)}$ .
The linear congruence $12x \equiv 8 \pmod{20}$ is equivalent to which of the following simplified congruences?
Answer: $3x \equiv 2 \pmod{5}$ 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.
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?
Answer: Divide by 3: $3x \equiv 2 \pmod{5}$ ; solution $x \equiv 4 \pmod{5}$ 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.
The linear congruence $8x \equiv 12 \pmod{20}$ requires careful analysis. Which statement about this congruence is correct?
Answer: It simplifies to $2x \equiv 3 \pmod{5}$ with solution $x \equiv 4 \pmod{5}$ 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.
The congruence $21x \equiv 14 \pmod{35}$ has multiple solutions. After reducing to lowest terms, how many distinct solutions exist modulo 35?
Answer: 7 solutions modulo 35 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.
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?
Answer: Need inverse of 3 mod 5; answer is $x \equiv 4 \pmod{5}$ 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.
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?
Answer: $x = 9$ 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$ .
Consider the congruence $4x \equiv 6 \pmod{10}$ . Which statement correctly describes the solution set?
Answer: The congruence has exactly two solutions modulo $10$ First check if solutions exist: $\gcd(4,10) = 2$ . Since $2$ divides $6$ , solutions exist. The number of solutions modulo $10$ is $\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$ is $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.
If $\gcd(a,15) = 3$ and the congruence $ax \equiv 9 \pmod{15}$ has solutions, how many solutions does it have modulo $15$ ?
Answer: $3$ solutions 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.
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:
Answer: $x \in \{11, 23, 35\}$ 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.
For which value of $a$ does the linear congruence $6x \equiv a \pmod{15}$ have exactly one solution modulo 15?
Answer: The congruence never has exactly one solution modulo 15 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.
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?
Answer: $x \equiv 4, 9, 14, 19, 24, 29, 34 \pmod{35}$ 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.
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$ ?
Answer: $t = 5$ 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.
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?
Answer: The error is not checking divisibility; since gcd(4,10) = 2 divides 6, solutions exist by reduction 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.
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$ ?
Answer: $x = 9$ 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.
For which value of $a$ does the congruence $6x \equiv a \pmod{9}$ have exactly three solutions modulo $9$ ?
Answer: $a = 3$ 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.
For what values of $k$ does the system of congruences $x \equiv 5 \pmod{8}$ and $x \equiv k \pmod{12}$ have a solution?
Answer: $k \equiv 1, 5, 9 \pmod{12}$ 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}$ ).

Start this quiz