1[section:extended_euclidean Extended Euclidean Algorithm] 2 3[section Introduction] 4 5The extended Euclidean algorithm solves the integer relation /mx + ny/ = gcd(/m/, /n/) for /x/ and /y/. 6 7[endsect] 8 9[section Synopsis] 10 11 #include <boost/integer/extended_euclidean.hpp> 12 13 namespace boost { namespace integer { 14 15 template<class Z> 16 struct euclidean_result_t { 17 Z gcd; 18 Z x; 19 Z y; 20 }; 21 22 23 template<class Z> 24 euclidean_result_t<Z> extended_euclidean(Z m, Z n); 25 26 }} 27 28[endsect] 29 30[section Usage] 31 32 int m = 12; 33 int n = 15; 34 auto res = extended_euclidean(m, n); 35 36 int gcd = res.gcd; 37 int x = res.x; 38 int y = res.y; 39 // mx + ny = gcd(m,n) should now hold 40 41[endsect] 42 43[section References] 44Wagstaff, Samuel S., ['The Joy of Factoring], Vol. 68. American Mathematical Soc., 2013. 45 46[endsect] 47[endsect] 48[/ 49Copyright 2018 Nick Thompson. 50Distributed under the Boost Software License, Version 1.0. 51(See accompanying file LICENSE_1_0.txt or copy at 52http://www.boost.org/LICENSE_1_0.txt). 53] 54