Friday, 9 January 2015

elementary number theory - 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 http://www.a-calculator.com/congruence/#faq-formula



$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.

Answer



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.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...