Solving the Linear Congruence $6x \equiv 3 \pmod{9}$

We are asked to find the incongruent solutions modulo 9 for the linear congruence $6x \equiv 3 \pmod{9}$.

A linear congruence of the form $ax \equiv b \pmod{m}$ has solutions if and only if the greatest common divisor (GCD) of $a$ and $m$ divides $b$. If solutions exist, the number of incongruent solutions modulo $m$ is equal to $\text{gcd}(a, m)$.

In our case, $a=6$, $b=3$, and $m=9$.

Step 1: Calculate the GCD of $a$ and $m$.

We need to find $\text{gcd}(6, 9)$.

• The divisors of 6 are 1, 2, 3, 6.
• The divisors of 9 are 1, 3, 9.
• The common divisors are 1 and 3.
• The greatest common divisor is 3. So, $\text{gcd}(6, 9) = 3$.

Step 2: Check for Solvability.

The condition for solvability is that $\text{gcd}(a, m)$ must divide $b$. Here, $\text{gcd}(6, 9) = 3$ and $b = 3$. Since 3 divides 3, the congruence $6x \equiv 3 \pmod{9}$ has solutions.

Step 3: Determine the Number of Solutions.

The number of incongruent solutions modulo $m$ is $\text{gcd}(a, m)$. Since $\text{gcd}(6, 9) = 3$, there will be 3 incongruent solutions modulo 9.

Step 4: Solve the Congruence.

Since $\text{gcd}(6, 9) = 3$ divides 3, we can divide the entire congruence $6x \equiv 3 \pmod{9}$ by 3. Dividing the coefficients and the modulus by the GCD, we get:

$\frac{6}{3}x \equiv \frac{3}{3} \pmod{\frac{9}{3}}$

$2x \equiv 1 \pmod{3}$

Now we need to solve this simpler linear congruence $2x \equiv 1 \pmod{3}$. We need to find the value of $x$ modulo 3.

We can test values or find the multiplicative inverse of 2 modulo 3.

• If $x=0$, $2(0) = 0 \not\equiv 1 \pmod{3}$.
• If $x=1$, $2(1) = 2 \not\equiv 1 \pmod{3}$.
• If $x=2$, $2(2) = 4 \equiv 1 \pmod{3}$.

So, the solution to $2x \equiv 1 \pmod{3}$ is $x \equiv 2 \pmod{3}$.

This means that $x$ must be of the form $x = 3k + 2$ for some integer $k$.

Step 5: Find Solutions Modulo 9.

We need to find the values of $x$ in the range $0 \le x < 9$ that satisfy $x \equiv 2 \pmod{3}$. We substitute integer values for $k$ into the expression $x = 3k + 2$ and find the solutions modulo 9.

• For $k=0$: $x = 3(0) + 2 = 2$. This is a solution modulo 9.
• For $k=1$: $x = 3(1) + 2 = 5$. This is a solution modulo 9.
• For $k=2$: $x = 3(2) + 2 = 8$. This is a solution modulo 9.
• For $k=3$: $x = 3(3) + 2 = 11$. $11 \equiv 2 \pmod{9}$, which is congruent to the first solution. We stop here as we have found 3 solutions, as predicted by the GCD.

The incongruent solutions modulo 9 are 2, 5, and 8.

These solutions satisfy the original congruence $6x \equiv 3 \pmod{9}$:

• For $x=2$: $6(2) = 12$. $12 \equiv 3 \pmod{9}$. (Since $12 - 3 = 9$, which is divisible by 9).
• For $x=5$: $6(5) = 30$. $30 \equiv 3 \pmod{9}$. (Since $30 - 3 = 27$, which is divisible by 9).
• For $x=8$: $6(8) = 48$. $48 \equiv 3 \pmod{9}$. (Since $48 - 3 = 45$, which is divisible by 9).

The incongruent solutions modulo 9 are 2, 5, and 8.

Comparing with the options provided, the correct set of solutions is {2, 5, 8}.

Revision Table: Key Concepts in Linear Congruences

Additional Information: Understanding Modulo Arithmetic and GCD

Modulo Arithmetic:

The expression $a \equiv b \pmod{m}$ means that $a$ and $b$ have the same remainder when divided by $m$. Equivalently, it means that $a - b$ is divisible by $m$. The set of integers modulo $m$, denoted by $\mathbb{Z}_m$ or $\mathbb{Z}/m\mathbb{Z}$, consists of the integers $\{0, 1, 2, \dots, m-1\}$, which represent the possible remainders when an integer is divided by $m$. Linear congruences are equations within this modular system.

Greatest Common Divisor (GCD):

The greatest common divisor of two integers $a$ and $b$, denoted $\text{gcd}(a, b)$, is the largest positive integer that divides both $a$ and $b$ without leaving a remainder. The GCD plays a crucial role in number theory, including determining the solvability and number of solutions for linear congruences and linear Diophantine equations. The Euclidean algorithm is a systematic method for finding the GCD of two integers.

Understanding GCD and modular arithmetic is fundamental to solving problems involving linear congruences like the one solved here ($6x \equiv 3 \pmod{9}$).