0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Apr 2 '14 at 21:18
  • $\begingroup$ 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}$ $\endgroup$ – kingW3 Apr 2 '14 at 21:20
  • $\begingroup$ @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? $\endgroup$ – Lilludzia Apr 2 '14 at 21:33
  • $\begingroup$ 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) $\endgroup$ – kingW3 Apr 2 '14 at 21:34
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ oh so you mean, because 5 * 1 = 5, therefore, we take 5 - 3 = 2? $\endgroup$ – Lilludzia Apr 2 '14 at 21:34
  • $\begingroup$ @Lilludzia I mean that because $-9\equiv 1$ we can say $-3\equiv \frac 13$ and since $-3\equiv 2$ we can say $2\equiv \frac 13$ $\endgroup$ – Mark Bennet Apr 2 '14 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.