Doing modular division when denominator and modulus not coprime

Revision en1, by shpvb, 2019-06-25 22:46:05

I looked for it and got a source: Link

But this method may not work when the denominator is a multiple of modulus.

For example, (8/8) % 4 should be 1, but applying this approach it gets gcd(4, 8) = 4 and hence find ((8/4)/(8/4))%(4/4) which results in 0.

Similarly for (80/8) % 4 should be 2 but this results in 0.

So what can be a generalized approach towards this?

Tags #modular_theory, modular arithmetic

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English shpvb 2019-06-25 22:46:05 571 Initial revision (published)