Solving modular arithmetic equation.

Question

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 1

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.

Answer 2

$1$ mod $5$ means $\dots -9, -4, 1, 6, 11, 16, 21 \dots$

To get divisibility by $3$ you choose the representatives $\dots -9, 6, 21 \dots$

Divide by $3$ to get $\dots -3, 2, 7 \dots$

Notice that these are all equivalent to $2$ mod $5$

Can you use the pattern to prove this?