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.
Module inversion is your friend.
Will read the link, thanks. I know modular inverse pow(i,m-2) already, wondering how to make p and q relatively prime.
You don't have to, you can think of multiplying by the modular inversion as of normal division.
Thanks. Where can I find out why this is true?
from eulers theorem:
if q⟂m:
q^-1 :≡ q^(φ(m)-1)
(p*q^-1) * q ≡ p * q^(φ(m)-1) * q ≡ p * q^φ(m) ≡ p
in particular, if m is prime, φ(m) = m-1 and
q^-1 = q^(m-2)
Thank you so much!
It actually doesn't matter — p and q don't have to be relatively prime. Do you understand general multiplicative inversion concept? If not, i think, you have to read something about it (there are plenty of topics). Otherwise, write me back :)
Got it. I dont actually understand multiplicative inverse concept except for the basics like inv(i) = pow(i,M-2). Thanks for the breadcrumbs, will definitely read on it!!
You're welcome!
:( I was unable to find any article that explained why p and q do not have to be relatively prime. Could you lead me to an article that would explain?
I'm not sure that it is mentioned in such articles... I don't really understand, what bothers you: Imagine P/Q, gcd(P, Q) = a. Thus, P/Q = (P / a) / (Q / a). So it is unclear for me why you've even thought about comprimality of P and Q. The only thing you need to be able to divide by K modulo M — coprimality of K and M.
Lets call the numerator you calculate $$$m$$$ and the denominator you calculate $$$n$$$, and call $$$\frac{p}{q}$$$ the simplified form with $$$\frac{p}{q} = \frac{m}{n}$$$. Then, you don't actually have to do anything special since $$$mn^{-1} \equiv pq^{-1} \mod M$$$. Specifically you can just use $$$mn^{-1}$$$ mod $$$M$$$ and ignore the part saying that they have to be relatively prime, since the numbers that are relatively prime will get the same result.
This is because there is some $$$a$$$ such that $$$m = ap$$$ and $$$n = aq$$$. Since $$$a \cdot a^{-1} \equiv 1 \mod M$$$, $$$pq^{-1} \equiv (pq^{-1})\cdot(aa^{-1}) \equiv (pa)\cdot(qa)^{-1} \equiv mn^{-1} \mod M$$$.
Thank you so much guys!! This helps me so much and I understand it now.