...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
The extended Euclidean algorithm solves the integer relation mx + ny = gcd(m, n) for x and y.
#include <boost/integer/extended_euclidean.hpp> namespace boost { namespace integer { template<class Z> struct euclidean_result_t { Z gcd; Z x; Z y; }; template<class Z> euclidean_result_t<Z> extended_euclidean(Z m, Z n); }}
int m = 12; int n = 15; auto res = extended_euclidean(m, n); int gcd = res.gcd; int x = res.x; int y = res.y; // mx + ny = gcd(m,n) should now hold
Wagstaff, Samuel S., The Joy of Factoring, Vol. 68. American Mathematical Soc., 2013.