Given a number x, find its multiplicative inverse y for a given modulo N

i.e. (x*y) == 1(MOD N)

Where the multiplicative inverse is useful?

Lets assume we need to compute ((a1 * a2 *....)/(b1 * b2 * .....)) mod N

1 simple way is to compute the above expression as

i.e. (x*y) == 1(MOD N)

Where the multiplicative inverse is useful?

Lets assume we need to compute ((a1 * a2 *....)/(b1 * b2 * .....)) mod N

1 simple way is to compute the above expression as