finding Inverse Modulo of a range of numbers under modulo m

pranay2063 · February 20, 2015, 7:01pm

While searching about inverse modulo, i got to know about a concise algorithm to find inverse modulo of
numbers in range[1…n) under modulo m.

Time complexity of this approach is O(n).

Implementation of the algorithm:

r[1] = 1;
for (int i=2; i<n; ++i)
r[i] = (m - (m/i) * r[m%i] m) m;

I am unable to understand the proof of the algorithm.
It would be very helpful if anyone explains the same in a simple way.

vaibhavchhabra · February 20, 2015, 9:57pm

i DOnt Know!

rahul_nexus · February 20, 2015, 10:33pm

When you muliply r[i] on the left hand and right hand side.

r[i] * i = 1 mod m

(m mod i ) * r[i]= - (m/i)

Now multiply r[m%i].

Thus r[m%i]*(m%i)=1

r[i] * 1= -(m/i)*r[m%i] mod m

r[i]=(m-(m/i)*r[m%i])%m

alt text

Hope this helps.
Sorry I dont know how to use latex.

pranay2063 · February 20, 2015, 11:07pm

This was indeed helpful.
I did not realise r[i]*i=1 mod m and so the confusion arose.