A silly question...

Revision en2, by roll_no_1, 2018-06-22 19:58:35

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 ?

Tags maths, modular arithmetic, calculation, modular inverse


  Rev. Lang. By When Δ Comment
en2 English roll_no_1 2018-06-22 19:58:35 526 Tiny change: 'this one ?' -> 'this one ?\n\n[Edit][user:Megumi_Tadokoro] '
en1 English roll_no_1 2018-06-22 08:28:04 462 Initial revision (published)