Sunday, April 23, 2017

modular arithmetic - Solving system of linear congruences

I have the following:



$$12x+28y=20$$



I'm trying to find solutions to the equation above defined by: $12x\equiv 20\pmod {28}$



The GCD is $d = gcd(28,12)=4$ and since $4 | 20 $, then there are 4 solutions that exist. (please correct me if I'm wrong).



Using the extending Euclidean Algorithm, we find $x_0=-2$ and $y_0=1$. The general solution is defined by: $$x_0+t(\frac nd)$$ which in turn gives $-2+7t$ in our case. But how can we have a negative remainder if $x=-2 \pmod 7$ which can't happen.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...