...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

The modular multiplicative inverse of a number *a* is
that number *x* which satisfies *ax*
= 1 mod *p*. A fast algorithm for computing modular multiplicative
inverses based on the extended Euclidean algorithm exists and is provided
by Boost.

#include <boost/integer/mod_inverse.hpp> namespace boost { namespace integer { template<class Z> Z mod_inverse(Z a, Z m); }}

int x = mod_inverse(2, 5); // prints x = 3: std::cout << "x = " << x << "\n"; int y = mod_inverse(2, 4); if (y == 0) { std::cout << "There is no inverse of 2 mod 4\n"; }

Multiplicative modular inverses exist if and only if *a*
and *m* are coprime. If *a* and *m*
share a common factor, then ```
mod_inverse(a,
m)
```

returns zero.

Wagstaff, Samuel S., *The Joy of Factoring*, Vol. 68.
American Mathematical Soc., 2013.