7
How do you compute pq^−1 mod M?
source link: https://codeforces.com/blog/entry/110733
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
How do you compute pq^−1 mod M?
Recently, I saw a problem asking to output the fractional answer p/q as pq^−1 mod M, where p and q are relatively prime in the fraction and M was some prime modulus. My approach was to compute the numerator p and the denominator q separately, and then output p mod M * q^-1 mod M. However, how can I ensure that p and q is relatively prime with this approach? As p and q get gigantic, their factors are lost during the mod, and I can not ensure that p and q are relatively prime.
Thank for reading, and if the question is hard to understand I can clarify.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK