# How to calculate mod inverse

Given a number set of integers $$\mathbb{Z}$$, how do I find the inverse of a given number?

I am trying to test an algorithm to extract the $$k$$ and $$x$$ values from the Elgamal Signature algorithm given that $$k$$ is repeated.

What I have is $$k$$ congruent to $$(m_1 - m_2)\times(s_1 - s_2)^{-1} \mod p - 1$$ given $$k$$ is used twice.

I am not sure how to calculate the mod inverse though? _ Is the above formula the same thing as $$((m_1 - m_2) \mod p -1 \times (s_1 - s_2)^{-1} \mod p -1) \mod p -1$$

I am not sure if it is any different since I am doing a mod inverse.

PS. I am a programmer, not a mathematician so please elaborate.

• Use the Extended Euclidean Algorithm, e.g. see here – Bill Dubuque Nov 19 '18 at 20:36
• I know how to find a mod inverse. But if I have a number A*B^-1 mod p-1 is that equivalent to A mod p-1 * B mod p-1 mod p-1. That is what I found online but I wasn't sure. – User Nov 19 '18 at 20:39
• $ab$ is invertible $\iff a,b$ are invertible $\iff a,b\,$ are coprime to the modulus. When so we have $(ab)^{-1}\equiv b^{-1}a^{-1}\,$ by $\ b^{-1}a^{-1} (ab) \equiv b^{-1}(a^{-1}a)b\equiv b^{-1}b \equiv 1\$ (inverses are always unique) – Bill Dubuque Nov 19 '18 at 20:58
• So what if I have a number * an inverse mod p -1. How would I break that down? – User Nov 19 '18 at 21:01
• Calculate the inverse then modular_multiply the two as you would any pair of (modular) integers - using the mod prodcut rule – Bill Dubuque Nov 19 '18 at 21:05

More generally, as Bill Dubuque points out in the comments, you can usually just take mods at each step, instead of doing the whole computation and then modding at the end. However, exponentiation is a notable exception; you can reduce the base but generally not the exponent $$a^k \bmod n \quad=\quad (a\bmod n)^k \bmod n \qquad\neq\qquad (a\bmod n)^{(k \bmod n)}.$$