This question might sound a little silly, but I was not able to figure the solution to this.
Say, I want to compute an expression of the form (a * b) / c, and I want to do it modulo 13. Now, if a = 13, b = 3, c = 13, then the answer clearly is 3. But if I try to do it this way (((a % 13) * (b % 13)) * inv(c % 13)) % 13, where inv(x) return the multiplicative inverse of x modulo 13, it will not work out. So, how to work around this one ?
[Edit] Magumi_Tadokoro provided a nice workaround for this one in the comments. But there's another thing I would want to ask. The expression above is a very common expression, and the problem mentioned might also have occurred for other similar expressions, but I haven't seen anyone trying to do something special to avoid this in any cf problem. Is it that even the setters do not use this in their problems, so as to avoid making use of this unconventional way of doing this kind of computation in modular arithmetic ?
if modulo is prime number you can write (a*b*power(c,modulo-2))%modulo
this expression gives 0 if you didn't notice, but the answer without the inverse modulo is 3.
The problem is that both a and c is divisible by 13 (which is equal to 13 in this case). If that is the case, then the inverse modulo is not exist. If you want to do it, then you must make sure that every number is not divisible by 13. For example, you can count the number of 13 in the prime factorization (the highest power of 13), while divide the number by 13. Then, you can just do the "inverse multiplying" trick, and multiply it with the number of 13. All of this can be done easily without make you slowing down.
If I am not wrong, you mean something like I count the no. of 13s in the prime factorization of the numerator(say n), and do the same with the denominator(say d). And then check to see if n — d > 0, if it is, the answer if 0, else I must remove every factor of 13 from both the numerator and denominator and apply the standard formula using inverses and direct multiplications modulo 13 ?
Yes, that's what I mean.
I think that will do, thanks.
Euler theorem works just on coprime numbers a and mod.
Do you mean to say Extended Euler algorithm ? because that does not relate to my question
https://en.wikipedia.org/wiki/Euler%27s_theorem
I could not get what you're trying to say. How is Euler's theorem related to this ?
Sorry, my solution was wrong.
Why do you downvote my comment? Is my solution wrong?
UPD:Yes it was wrong. I am sorry.
I think you should divide numerator,denominator and mod by gcd(denominator,mod) if gcd(denominator,mod) divides numerator as inverse of a modulo m exists only if GCD(a,m)=1 (or they are co-prime).
You can check it here:- https://math.stackexchange.com/questions/395207/doing-modular-division-when-denominator-and-modulus-not-coprime.
I didn't downvote your comment.
Thank you very much for answering and not downvoting! :)
Auto comment: topic has been updated by roll_no_1 (previous revision, new revision, compare).