How to solve and get the general solution of a congruence equation
I'm following the tutorial of an online calculator to solve congruence equations
I'm doing the same as they are doing but I never get the same result, I don't know what I'm doing wrong.
the tutorial
$28x\equiv 14 \ $mod $6$
$28$ mod $6$ and $14$ mod $6$ I get
a = $4$ and b = $2$
the linear combination of the $gcd(4,6) =$ $4(-1) + (1)6 = 2$
putting into the formula I get
$\begin{equation*} x_0 = \frac{2(-1)}{2} \; ( \text{mod} \; 6) \end{equation*} = 5$
general solution \begin{equation*} x_n = 5 + \frac{n(6)}{2} \; ( \text{mod} \; 6) \end{equation*}
the final answer is
General form of solutions: 2 + 3k.
Solutions for x less than 6: 2,5.3 Answers
$\begingroup$First of all you can take all the coefficients down by congruence with the modulus.
$$28x\equiv 14 \bmod 6 \quad\to\quad 4x\equiv 2\bmod 6$$
Note that here, in concept, you are not dividing by $7$ - you are taking $28\bmod 6 $ and $14\bmod 6$ (even though the effect is the same).
Then you can put aside the common factor of $2$ from coefficients and modulus (although you may need to bring it back for the solution eventually):
$$4x\equiv 2 \bmod 6 \quad\to\quad 2x\equiv 1\bmod 3$$
Now, by examination, $x\equiv 2\bmod 3$ meaning - if you need to present the result $\bmod 6$ - $x\equiv \{2,5\} \bmod 6$, as per your text book.
Rather than a case where you can solve this last step "by examination" you may need to explicitly find the multiplicative inverse (and in this case that is what the equation amounts to anyway). For small moduli this may be an easy search; in general you can use the extended Euclidean algorithm.
$\endgroup$ 6 $\begingroup$$$28x\equiv 14\mod 6$$ means $$6|28x-14$$
Since $28x-14$ is even for every integer $x$, this is equivalent to $$3|28x-14$$ and therefore $$28x\equiv 14\mod 3$$
Reducing $28$ and $14$ mod $3$ gives $$x\equiv 2\mod 3$$
Hence the positive solutions are $2,5,8,\cdots$
$\endgroup$ 5 $\begingroup$There in no discrepancy: $ $ your solution is $\,x\equiv\, 5,\,5\!+\!3\,\equiv\, 5,\,2\pmod{\!6},\,$ same as claimed.
Remark $ $ Generally, as above, we will need to reduce the results of the formula $\bmod m\,$ if we wish to obtain the least nonnegative representatives of the solutions.
$\endgroup$ 8
