I know this may seem like a math question but i just saw this in a contest and I really want to know how to solve it.
We have
a (mod c)
and
b (mod c)
and we're looking for the value of the quotient
(a/b) (mod c)
Any ideas?
+10
A:
In the ring of integers modulo C, these equations are equivalent:
A / B (mod C)
A * (1/B) (mod C)
A * B-1(mod C).
Thus you need to find B-1, the multiplicative inverse of B modulo C. You can find it using e.g. extended Euclidian algorithm.
Note that not every number has a multiplicative inverse for the given modulus.
Specifically, B-1 exists if and only if gcd(B, C) = 1 (i.e. B and C are coprime).
See also
Modular multiplicative inverse: Example
Suppose we want to find the multiplicative inverse of 3 modulo 11.
That is, we want to find
x = 3-1(mod 11)
x = 1/3 (mod 11)
3x = 1 (mod 11)
Using extended Euclidian algorithm, you will find that:
x = 4 (mod 11)
Thus, the modular multiplicative inverse of 3 modulo 11 is 4. In other words:
A / 3 == A * 4 (mod 11)
Naive algorithm: brute force search
One way to solve this:
3x = 1 (mod 11)
Is to simply try x for all values 0..11, and see if the equation holds true. For small modulus, this algorithm may be acceptable, but extended Euclidian algorithm is much better asymptotically.
polygenelubricants
2010-08-20 12:05:26
That's like me saying A-B is A+(-B)...true, but not productive.
rownage
2010-08-20 12:09:36
Sorry but i just didn't understand that. can you please explain more?
AKGMA
2010-08-20 12:10:01
@rownage It IS productive, because division is not simple in modular arithmetic. The only way to actually perform division is to find the multiplicative inverse. A google search for modular division wouldn't be nearly as helpful as a google search for multiplicative inverse. Just because a property is simple for normal mathematics doesn't mean the property is even true in more elaborate situations such as this.
Dave McClelland
2010-08-20 12:14:25
so it isn't (a*b^-1)(mod c), but rather a*b^-1(mod c)?
rownage
2010-08-20 12:21:34
@rownage: `a * b^-1 (mod c)` is mathematical notation. Using C-notation, that would be equivalent to `(a * inverseOfB) % c`
BlueRaja - Danny Pflughoeft
2010-08-20 15:27:40
sorry but what if b%c==0?
AKGMA
2010-08-20 17:39:35
I mean b=0(mod c)
AKGMA
2010-08-20 17:39:50
`B = 0 (mod C)` means `B` and `C` are not coprimes. Inverse does not exist in this case.
polygenelubricants
2010-08-20 17:49:56
+1
A:
There are potentially many answers. When all you have is k = B mod C, then B could be any k+CN for all integer N.
This means B could potentially be very large. So large, in fact, to make A/B into zero.
However, that's just one way to respond.
Ian
2010-08-20 12:10:38
No, B could never be large enough to make A/B into zero. It could be very large and A/B would be extremely small but it would never actually be zero. You can say it tends to zero as B tends to infinity though so your general idea was right. I'm just a mathematician so like to be precise. :) But that observation of taking a fixed A and varying B does admirably demonstrate the fact there are multiple valid answers. Its interesting to wonder if the correct answer is meant to be a function of m,n or if it just a badly specified question... +1 overall anyway. ;-)
Chris
2010-08-20 12:17:00
Eh? are you two using real numbers in an equation that specified "mod C"? In princple of course it's possible to specify a number system that works that way, but the normal convention is that you're working with integers modulo some integer, so no matter how large B is, it is also some value 0 <= n < C (the numbers represent infinite sets of integers), and while A/B will always have an integer result. Division is always defined as the inverse of multiplication, so where multiplication behaves differently (e.g. by giving a modulo C result), division behaves differently to match.
Steve314
2010-08-20 12:28:53
Specific example: Mod-6 arithmetic. 3/2 is undefined. Why? Nothing you can multiply by two will yield an odd number, given the even modulus. Is that what you mean? Us computer guys are used to dealing with mod-2^32 arithmetic, except that division is defined as an approximation so that |b*(a/b)| <= |a|.Oh, and one other thing: He didn't say he was working in modular arithmetic; he said he had some numbers modulo another number. This is maybe splitting hairs, but should the presence of a modulus operation be enough to conclude that the entire problem is about modular arithmetic?
Ian
2010-08-20 14:01:55
A:
Can anyone provide me with a sample C++ code? I found out that b and c are coprime but i just can't code it. sorry for not adding the tag: HOMEWORK!
AKGMA
2010-08-20 17:04:07
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm : read it and try to understand it. Precisely because this is homework, no one should just give you the code.
polygenelubricants
2010-08-20 17:07:51
I really tried. actually this is a contest question. I test it and it works well but when i submit it i get wrong answer!
AKGMA
2010-08-20 17:11:56
Please do not use Answers as if they were a regular web forum for additional comments. This site is designed to be a Question and Answer oriented site. Please *edit* your original question. Improving the question will result in everyone being able to answer your question better.
mctylr
2010-08-20 17:21:10
For your own ethics, if you are a _participant in the contest_, please refrain from using this site until the contest is over. Then, feel few to ask for help in learning what the correct answer is. If you mean a "bonus question" for homework, that is okay, you can ask for help in learning to understand the question and the answer. Good luck.
mctylr
2010-08-20 17:21:53
@AKGMA: You tried? Post some code and let's see what went wrong then.
polygenelubricants
2010-08-20 17:28:27
I found what was wrong. When b%c==0 it gives silly answers!What is the answer in this case then?
AKGMA
2010-08-20 17:42:15