0

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.

Lilludzia
  • 5
  • The following works, though it is inefficient for larger numbers. Try $u=0,1,2,3,4$. Or multiply both sides by the modular inverse of $3$, which is $2$. – André Nicolas Apr 02 '14 at 21:18
  • This means $3*u=1 \pmod{5}$ or in this case $u=2$ Anyway easy way to find it is manipulating signs $3u=1\pmod{5}\-2u=-4\pmod{5}\u=2\pmod{5}$ – kingW3 Apr 02 '14 at 21:20
  • @kingW3 right, i see what u meant. Do you think this method works for large number? like when it is some 4-digit number to mod 3-digit number, the division would be more difficult and more challenge to find the manipulating signs dont you think? – Lilludzia Apr 02 '14 at 21:33
  • Well not really you'll probably get some factors they share(2 or 3 for example) then you divide then again you change sign and when you change sign you change it's divisors(most the time) – kingW3 Apr 02 '14 at 21:34

2 Answers2

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.

SantiagoC
  • 640
0

$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?

Mark Bennet
  • 100,194