Euclidean algorithm & Extended Euclidean Algorithm C++ - https://en.wikipedia.org/wiki/Euclidean_algorithm

euclideanalgorithm.cpp

#include <QtCore/QtGlobal>

// Greatest common divisor (gcd) of two integers
// Euclidean Algorithm
qint64 euclideanAlgorithm(qint64 a, qint64 b) {
  qint64 c;
  while (b) {
     c = a % b;
     a = b;
     b = c;
  }
  qint64 gcd = abs(a);
  return gcd;
}

// Greatest common divisor (gcd) of two integers
// Extended Euclidean Algorithm
qint64 euclideanAlgorithmExtended(qint64 m, qint64 n) {
    qint64 t;
    if (m < n) {
        t = m;
        m = n;
        n = t;
    }
    qint64 a = 0, a_ = 1, c = m;
    qint64 b = 1, b_ = 0, d = n;
    qint64 q = c / d;
    qint64 r = c % d;
    while (r != 0) {
        c = d; d = r; t = a_;
        a_ = a; a = t - q * a; t = b_;
        b_ = b; b = t - q * b;
        q = c / d;
        r = c % d;
    }
    qint64 gcd = a * m + b * n;
    return gcd;
}