### roll_no_1's blog

By roll_no_1, history, 9 months ago, ,

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 ?

 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 ?

•
• +14
•

 » 9 months ago, # |   0 if modulo is prime number you can write (a*b*power(c,modulo-2))%modulo
•  » » 9 months ago, # ^ |   0 this expression gives 0 if you didn't notice, but the answer without the inverse modulo is 3.
 » 9 months ago, # |   +10 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.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +3 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 ?
•  » » » 9 months ago, # ^ |   +3 Yes, that's what I mean.
•  » » » » 9 months ago, # ^ |   +3 I think that will do, thanks.
 » 9 months ago, # |   +16 Euler theorem works just on coprime numbers a and mod.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Do you mean to say Extended Euler algorithm ? because that does not relate to my question
•  » » » 9 months ago, # ^ |   0
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 I could not get what you're trying to say. How is Euler's theorem related to this ?
 » 9 months ago, # | ← Rev. 3 →   -14 Sorry, my solution was wrong.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +4 Why do you downvote my comment? Is my solution wrong?UPD:Yes it was wrong. I am sorry.
•  » » 9 months ago, # ^ | ← Rev. 4 →   +10 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).I didn't downvote your comment.
•  » » » 9 months ago, # ^ |   +9 Thank you very much for answering and not downvoting! :)
 » 9 months ago, # |   0 Auto comment: topic has been updated by roll_no_1 (previous revision, new revision, compare).