Saturday, 14 October 2017

discrete mathematics - Solving Simple Linear Congruence



Im give the equation 2x5(mod9) and am told to solve for the linear congruence. I attempted to this with only the methods taught to me and no more so i cannot use Bezout's Identity or a Diophantine Equation. I can only use Extended Euclid's algorithm and use modular arithmetic from there.




My attempt:



GCD(2,9)



9=(2)4+1 (Find GCD)



1=(1)94(2) (Solve 1 in terms of 9 and 2)



194(2)(mod9) (Rewrite equivalence with new inverse)




94=5 (Finding equivalent positive multiplicative inverse)



(5)2x(5)5(mod9) (Go back to original equation and multiply each side by the inverse)



x=25(mod9) (The left side becomes x because 52(mod9)=1)



x=7 (Result)



I cannot find a single calculator online that confirms this answer. Quite honestly different calculators are giving me different answers so I'm not even quite sure if mine is wrong or not. Is this right or is there something wrong in my steps?


Answer




This particular example is quite easy:
2x54mod9x27mod9


This is easy because we can just divide the two sides of 2x4mod9 by 2 since gcd(2,9)=1.



Note that 2x4mod9 means that 9 divides 2x+4=2(x+2), and so 9 divides x+2.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

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