Skip to main content
edited tags
Link
Dan Brumleve
  • 17.7k
  • 6
  • 52
  • 104
Source Link
khernik
  • 1.4k
  • 3
  • 15
  • 24

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 = 52[multiplicative inverse of the first equation] + 34[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?