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;
for (int i=2; i<n; ++i)
r[i] = (m - (m/i) * r[m%i] % m) % m;
Here is the link:
I am unable to understand the proof of the algorithm.
It would be very helpful if anyone explains the same in a simple way.