Boost C++ Libraries

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

Extended Euclidean Algorithm

Introduction
Synopsis
Usage
References

Introduction

The extended Euclidean algorithm solves the integer relation mx + ny = gcd(m, n) for x and y.

Synopsis

#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);

}}

Usage

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

References

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