Need help! I'm having some problem with understanding this equation! We have a similiar example in the book, but I dont really get what they mean.
So here is the question. Given 3u = 1 (mod 5), find u?
I mean, as far as I understand, 3 = 3 (mod 5), right? So how about "u"?
Could you help me with understanding this please? A general formula or way of solving might be useful, so I can apply it into other similiar equations as well as the harder ones.
Answer
In this case, what you want to notice is that $3$ can be inverted modulo $5$. Notice that $3*2 = 6 = 1$ (mod 5). So $u = 2$ would be your answer. As for how to get the answer in general, notice that $5$ and $3$ are coprime. So, there must be a linear combination $3u+5v = 1$, which you get using Euclid's algorithm. Now, notice that $3u+5v = 3u$ (mod 5) so thats how you get the answer. In conclusion, you can solve the problem $ax = 1$ (mod $b$) if and only if $a$ and $b$ are coprime.
No comments:
Post a Comment