daftdove's blog

How do you compute pq^−1 mod M?
By daftdove, history, 2 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Module inversion is your friend.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Will read the link, thanks. I know modular inverse pow(i,m-2) already, wondering how to make p and q relatively prime.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      You don't have to, you can think of multiplying by the modular inversion as of normal division.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks. Where can I find out why this is true?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          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)

          → Reply
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!!

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      You're welcome!

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        :( 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?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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$$$.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much guys!! This helps me so much and I understand it now.

→ Reply