Short modular inverse

Revision en1, by _h_, 2016-02-08 22:34:54

Modular inverse is needed to solve some Codeforces problems. Here is a particularly neat way to compute inverses in logarithmic time (in C++), which I find easier to remember than the extended Euclidean algorithm:

long long inv(long long a, long long b){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}

Here a, b are positive co-prime integers, and inv(a,b) is the inverse of a modulo b, lying between 1 and b.

The idea behind the code is that to compute inv(a,b), we find x such that and , and then return x/a. To find x, we can write x = yb + 1 and solve for y by recursively computing inv(b,a). (Or actually inv(b%a, a).)

This is somewhat slower than the extended Euclidean algorithm, and you might get overflow if a*b doesn't fit inside a long long, but that shouldn't be a problem in competitions.

Tags number theory, modular inverse

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English _h_ 2016-02-12 01:18:50 590 (published)
en1 English _h_ 2016-02-08 22:34:54 964 Initial revision (saved to drafts)