# How to find modular multiplicative inverse

For example:

$$63x \equiv 1 (mod 17)$$

I wanna find the multiplicative inverse here so that I can use this in the Chinese reminder theorem. Example:

$$x \equiv 2 (mod 3)$$ $$x \equiv 4 (mod 5)$$

$N=3*5=15$
$N_{1}=5$
$N_{2}=3$

x = 5*2*[multiplicative inverse of the first equation] + 3*4*[multiplicative inverse of the second equation]

Multiplicative inversions should be evaluated like this - $N_{1}x \equiv 1 (mod n_{1})$

So, back to the topic, the solution of the first equation in this post is $17k-7$...But what will the multiplicative inverse be? -7? 10? 27?

As you said, any number of the form $x=17k-7$ (where $k$) is an integer will be a valid solution to $$63x \equiv 1 \pmod {17}$$ But the real punchline is that when we talk about the numbers modulo $17$, the numbers $x=17k-7$ are all the same number.

To be more precise, the numbers $x=17k-7$ are all part of the equivalence class of $10$, where two numbers are equivalent when they have the same remainder under division by $17$. As it ends up, when you add and multiply numbers in modular arithmetic, the result is the same regardless of which representative you choose.

So, for this example, $10\equiv -7$ are the same valid solution to the equation. In fact, we can check to find that this is the case:

$$63\times10 \equiv 630 \equiv 1 + (37\times 17) \equiv 1 + 0 \equiv 1 \pmod{17}\\ 63\times(-7) \equiv -441 \equiv 1 + (26\times 17)\equiv 1 + 0 \equiv 1 \pmod{17}$$ In fact, we didn't even need to use the number $63$. Instead, we could have used the equivalent value $12\equiv63 \pmod{17}$. You'll find, as before, that $$12\times10\equiv 12\times(-7)\equiv 1 \pmod{17}$$ I hope that I've cleared things up.

• If so, then what should I substitute as the inverse variable in the Chinese reminder theorem final formula, as in my example? Anything from $17k - 7$? – khernik Aug 15 '13 at 23:10
• Yep, anything from there will work, and will give you the same answer modulo $n_1n_2$. I personally would use $10$ to make the multiplication easier. – Omnomnomnom Aug 15 '13 at 23:14

For example:

$$63=12\pmod{17 }\;,\;\;12\cdot7=84=-1\pmod{17}\implies -7=10=12^{-1}\pmod{17}$$

and from here

$$63x=1\pmod{17}\implies 12x=1\pmod{17}\implies x=12^{-1}=10\pmod{17}$$