Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Modular Inverse | Reply
I noticed Petr uses modular inverse a lot when doing problems that have solutions mod some prime. I was wondering what he uses them for and why they are useful. Most of the time I read his code and follow it up until he starts using mod Inv and then I'm lost. Anyone care to explain?
Re: Modular Inverse (response to post by tehqin) | Reply
Inverses are useful for dividing...


Why the minuses? You people always minus me!
Re: Modular Inverse (response to post by tehqin) | Reply
Imagine you want to calculate a/b mod p,where a divides b, and b is prime to p, i.e gcd(b,p)=1,then:
(a/b)mod p=a*inv(b,p) mod p.So you get ride of dividing! this is most useful when a and b are really big numbers.
for example when you want to find n!/k! mod a prime number p,when k<p.you can easily solve this even when n and k are of order of million.>
Re: Modular Inverse (response to post by tehqin) | Reply
Try this jewel of a thread: http://forums.topcoder.com/;jsessionid=E73D10D2028B213BD1C7EFA53C64F262?module=Thread&threadID=567836&start=0&mc=5#767654

Hope it helps :)
Re: Modular Inverse (response to post by obi1kenobi) | Reply
Wow thank you, there have been many times where I wanted to divide under modulus but couldn't! This will definitely come in handy for future competitions.
Re: Modular Inverse (response to post by Hadi_Asiaie) | Reply
Is there a way to replace division so it works under modulus when you are modding by something that is not co-prime to b?
Re: Modular Inverse (response to post by tehqin) | Reply
Basic answer - no. If you need to calculate a / b mod c then you need at least to know a mod (c * gcd(c, b))
Re: Modular Inverse (response to post by ltaravilse) | Reply
Not sure why you got minused here, because technically your answer was correct, albeit short.
Re: Modular Inverse (response to post by tehqin) | Reply
If the modulus is not prime, the existence of the inverse is not guaranteed, at least as far as my understanding of math goes. Fortunately, 99% of competition tasks provide prime moduli, so that shouldn't be too much of a problem.
Re: Modular Inverse (response to post by ltaravilse) | Reply
Maybe because your answer "Inverses are useful for dividing..." doesn't add much knowledge to the poster of the original question....
RSS