A simple program performing the Euclidean algorithm

Euclidean.cc

#include <assert.h>
#include <iostream>
#include <type_traits>

template <typename I>
struct EuclideanResult
{
    static_assert(std::is_integral_v<I>, "I must be integral");
    I gcd, x, y, lhs, rhs;
};

template <typename L, typename R>
auto Euclidean(L const lhs, R const rhs)
{
    static_assert(std::is_integral_v<L>, "L must be integral");
    static_assert(std::is_integral_v<R>, "R must be integral");

    using CommonType = std::common_type_t<L, R>;
    CommonType a = lhs, b = rhs;
    CommonType ax = 1, ay = 0;
    CommonType bx = 0, by = 1;

    while (b)
    {
        auto const q  = a / b;
        auto const r  = a % b;
        auto const rx = ax - q * bx;
        auto const ry = ay - q * by;

        std::cout << a << " = (" << q << ")" << b;

        if (r)
            std::cout << " + " << r << std::endl;
        else
            std::cout << std::endl;

        a = b;
        b = r;

        ax = bx;
        ay = by;

        bx = rx;
        by = ry;
    }

    return EuclideanResult<CommonType> {
        .gcd = a,
        .x   = ax,
        .y   = ay,
        .lhs = lhs,
        .rhs = rhs,
    };
}

template <typename I>
void Verify(EuclideanResult<I> const& res)
{
    assert(res.lhs % res.gcd == 0);
    assert(res.rhs % res.gcd == 0);
    assert(res.gcd == res.lhs * res.x + res.rhs * res.y);
}

template <typename T, typename I>
std::basic_ostream<T>& operator<<(std::basic_ostream<T>&    os,
                                  EuclideanResult<I> const& res)
{
    os << res.gcd << " = (" << res.x << ")" << res.lhs;
    if (res.y < 0)
        os << " - (" << -res.y;
    else
        os << " + (" << res.y;
    return os << ")" << res.rhs;
}

int main()
{
    int a, b;
    while (true)
    {
        using namespace std;
        cin >> a >> b;
        auto res = Euclidean(a, b);
        Verify(res);
        cout << res << endl;
    }
}