Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

roll_no_1's blog

A silly question...
By roll_no_1, history, 6 years ago, In English

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 ?

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if modulo is prime number you can write (a*b*power(c,modulo-2))%modulo

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this expression gives 0 if you didn't notice, but the answer without the inverse modulo is 3.

    → Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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 ?

    → Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Euler theorem works just on coprime numbers a and mod.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -14 Vote: I do not like it

Sorry, my solution was wrong.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by roll_no_1 (previous revision, new revision, compare).

→ Reply