Question

The solution set of $8x \equiv 6\left( {\bmod 14} \right),{\text{ }}x \in z$ are;
$\left( 1 \right)\left[ 8 \right] \cup \left[ 6 \right]$
$\left( 2 \right)\left[ 8 \right] \cup \left[ {14} \right]$
$\left( 3 \right)\left[ 6 \right] \cup \left[ {13} \right]$
$\left( 4 \right)\left[ 8 \right] \cup \left[ 6 \right] \cup \left[ {13} \right]$

Answer 1

This question is based on linear congruence. Linear congruence is represented by the form $ax \equiv b\left( {\bmod n} \right)$ ; where $x$ is an unknown integer whose power is $1$ , therefore the expression is called linear congruence in one variable. There are certain steps to solve this type of linear congruent problems which are given below.

Complete step-by-step solution:
Step I : Find ${\text{GCD}}\left( {{\text{a,n}}} \right)$ , let us name it as ${\text{d}}$ .
Step II : Find ratio $\dfrac{b}{d}$ ; if we get a whole number on division then there exists a solution for the given problem.
Step III : Find ${\text{d mod n}}$ ; this gives us how many solutions are possible for the given problem.
Step IV : Divide both the sides by $d$ .
Step V : Multiply both sides by the multiplicative inverse of $a$ i.e. ${a^{ - 1}}$ .
Step VI : The general solution equation is given by , ${x_k} = {x_0} + k\left( {\dfrac{n}{d}} \right)$ ; where k = \left\\{ {0,1,2,3,.......\left( {d - 1} \right)} \right\\}
Now, using these rules let us solve the given problem;
We know the general form of linear congruence is $ax \equiv b\left( {\bmod n} \right)$
$\Rightarrow 8x \equiv 6\left( {\bmod 14} \right){\text{ }}......\left( 1 \right)$ (Given)
Comparing our question and the standard form to get the respective values, we get;
$\Rightarrow a = 8,{\text{ }}b = 6{\text{ and }}m = 14$ ;
Step I : Finding ${\text{GCD}}\left( {8,14} \right)$ ;
$\Rightarrow 8 = 2 \times 2 \times 2$
$\Rightarrow 14 = 2 \times 7$
Therefore, ${\text{GCD}}\left( {8,14} \right) = 2$ ; means $d = 2$ .
Step II : Dividing $\dfrac{b}{d}{\text{ i}}{\text{.e}}{\text{. }}\dfrac{6}{2} = 3$ ; since $3$ is a whole number therefore the given linear congruence problem is solvable. If $b$ is not completely divisible by $d$ , then we can stop here only and say that the given problem is not solvable.
Step III : Finding $d{\text{ mod }}n$ i.e. $2{\text{ mod 14 = 2}}$ ; therefore there will be two solutions for the given problem.
Step IV : Divide both the sides by $d$ which is $2$ , we get;
$\Rightarrow 8x \equiv 6\left( {\bmod 14} \right)$
$\Rightarrow 4x \equiv 3\left( {\bmod 14} \right)......\left( 2 \right)$
Step V: We have to find the multiplicative inverse of $a{\text{ i}}{\text{.e}}{\text{. }}{{\text{4}}^{ - 1}}$, according to the above equation;
$\Rightarrow \left( {4 \times a} \right)\bmod 7 = 1$
Now, we have to find such a value of $a$; for which the above condition is satisfied and that value will be the multiplicative inverse of $4$ .
Therefore, we will get $\Rightarrow a = 2{\text{i}}{\text{.e}}{\text{. }}{{\text{4}}^{ - 1}} = 2$
$\Rightarrow {4^{ - 1}} \times 4 \times x \equiv {4^{ - 1}} \times 3\left( {\bmod 7} \right)$
On simplification, the above expression reduces to;
$\Rightarrow x \equiv {4^{ - 1}} \times 3\left( {\bmod 7} \right)$
Now, put the value of ${4^{ - 1}} = 2$ ;
$\Rightarrow x \equiv 6\left( {\bmod 7} \right)$
Therefore, ${x_0} = 6$ .
Step VI : The general solution is given by, ${x_k} = {x_0} + k\left( {\dfrac{n}{d}} \right)$
Put $k = 1$ , ${x_0} = 6$ and $n = 14$ according to equation $\left( 1 \right)$ , we get;
$\Rightarrow {x_1} = 6 + \left( {\dfrac{{14}}{2}} \right)$
$\Rightarrow {x_1} = 13$
Therefore the two solutions for the given linear congruence relation are ${x_0} = 6{\text{ and }}{x_1} = 13$ .
Hence the correct answer for this question is option $\left( 3 \right)$ i.e. $\left[ 6 \right] \cup \left[ {13} \right]$.

Note: The linear congruence relation $ax \equiv b\left( {\bmod n} \right)$ means that integers $a{\text{ and }}b$ are congruent modulo $n$ if they produce the same remainder on division by $n$ . Ultimately we have to find an integer $x$ that satisfies this condition and those values of $x$ are called congruent solutions for the given linear congruence . The number of congruent solutions depends on the G.C.D. ( greatest common divisor ) as explained above. There can be different congruent solutions belonging to different congruent classes (different values or patterns), those solutions are called incongruent solutions.