solving (a/b) mod m

Revision en1, by mapvr3, 2018-01-03 07:25:26
(a/b) (mod P) = (a * b^-1) (mod P) = (a (mod P) * b^-1 (mod P)) (mod P).

Now, by Fermat's theorem, b-1 (mod P) will be b^P-2 (mod P). Of course, for this b and P must be co-prime to each other and P must be a prime. So, (a/b) (mod P) = (a (mod P) * b^P-2 (mod P)) (mod P). works only if P is prime and a,b are coprime to P

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English mapvr3 2018-01-03 07:25:26 379 Initial revision (published)