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: 12x20(mod28)



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 x0=2 and y0=1. The general solution is defined by: x0+t(nd)

which in turn gives 2+7t in our case. But how can we have a negative remainder if x=2(mod7) which can't happen.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...