solving (a/b) mod m

Правка en1, от 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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский mapvr3 2018-01-03 07:25:26 379 Initial revision (published)