Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for a snapshot of the develop branch, built from commit 0f79ae966a.

Extended Euclidean Algorithm


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.