Thursday, 13 March 2014

number theory - Find integer solutions to linear congruence




Find all integer solutions of $2n \equiv 12 \bmod 19$



So I have re-arranged to: $2x-19y=12$ and by the extended Euclidean Algorithm, I get $$x=1 \ $$
$$y=-9$$



However, this is how far I was able to get to and not sure what follow past this point? What exactly are we looking for?


Answer



I would say there are infinitely many. Another way to think of $2n \equiv 12 \pmod{19}$ is that $2n - 12 = 19k$ for some $k \in \mathbb{Z}$. So $n = \frac{19k + 12}{2}$. Thus any even $k$ will produce an integer solution.



EDIT: It might be better to think in terms of equivalence classes for the sake of negative $k$ values. So maybe $[n] = \bigl[\frac{19k + 12}{2}\bigr]$ in $\mathbb{Z}_{19}$. For example: If $k = -2$, then $[n]_{19} = [-13]_{19} = [6]_{19}$.



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