### 1. Description

Because $$gcd(a,b)=gcd(|a|,|b|)$$, we just consider the nonnegative integers in this article.
And $$d|a$$ means $$d$$ divides $$a$$, that is to say, $$a=kd$$ for some integer $$k$$.

### 2. GCD recursion theorem

$$gcd(a,b)=gcd(b,a mod b)$$

Proof:
Let $$d=gcd(a,b)$$, then $$d|a$$ and $$d|b$$.
$$a\ mod\ b=a-qb$$, where $$q=\left \lfloor a/b \right \rfloor$$, so $$d|(a\ mod\ b)$$.
And $$d|b$$, so $$d|gcd(b,a\ mod\ b)$$, this is to say, $$gcd(a,b)|gcd(b,a\ mod\ b)$$.
Similarly, $$gcd(b,a\ mod\ b)|gcd(a,b)$$.
So $$gcd(a,b)=gcd(b,a\ mod\ b)$$.

### 3. Euclid’s algorithm

int Euclid(int a, int b)
{
if (b == 0)
return a;
else
return Euclid(b, a%b);
}


And we can easily implement it in an iterative way.

int Euclid_iter(int a, int b)
{
int tmp;
while (b != 0)
{
tmp = b;
b = a % b;
a = tmp;
}
return a;
}


The Euclid’s algorithm can return some additional useful information.
$$d=gcd(a,b)=ax+by$$

void ExtendedEuclid(int a, int b,int &d,int &x,int &y,vector<vector<int> >&res)
{
if (b == 0)
{
d = a;
x = 1;
y = 0;
vector<int> tmp;
tmp.push_back(d);
tmp.push_back(x);
tmp.push_back(y);
res.push_back(tmp);
}
else
{
int d_, x_, y_;
ExtendedEuclid(b, a%b,d_,x_,y_,res);
d=d_;
x=y_;
y=x_ - a / b * y_;
vector<int> tmp;
tmp.push_back(d);
tmp.push_back(x);
tmp.push_back(y);
res.push_back(tmp);
}
}


The time complexity is $$O(lgb)$$.

### 4. Greatest common divisor and least common multiple for n integers

The GCD of n integers is easy to understand.

$$gcd(a_1,…,a_n)=gcd(a_i,gcd(a_1,…,a_(i-1),a(i+1),…,a_n))$$

int Euclid_mul(vector<int> A)
{
int res = A[0];
for (int i = 1; i < A.size(); i++)
{
res = Euclid(A[i], res);
}
return res;
}


Considering about LCM, we know $$lcm(a,b)={a*b}/{gcd(a,b)}$$, but this only works for two numbers.

So,

$$lcm(a_1,…,a_n)=lcm(a_i,lcm(a_1,…,a_{i-1},a_{i+1},…,a_n)$$

int lcm(vector<int> A)
{
int res = A[0];
for (int i = 1; i < A.size(); i++)
{
res = (A[i] * res) / Euclid(A[i], res);
}
return res;
}


The time complexity is $$O(n+lg(max\left \{a_0,a_1,…,a_n \right \}))$$.

### 5. Test

#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n",Euclid(a, b));
printf("%d\n", Euclid_iter(a, b));
vector<vector<int> > res;
int d, x, y;
ExtendedEuclid(a, b,d,x,y,res);
for (int i = res.size()-1; i>=0; i--)
{
for (int j = 0; j < res[0].size(); j++)
{
printf("%d ", res[i][j]);
}
printf("\n");
}
int n;
scanf("%d", &n);
vector<int> A(n);
for (int i = 0; i < n; i++) scanf("%d", &A[i]);
printf("%d\n",Euclid_mul(A));
printf("%d\n", lcm(A));
system("pause");
return 0;
}


Result:


99 78
3
3
3 -11 14
3 3 -11
3 -2 3
3 1 -2
3 0 1
3 1 0
2 4 6 8
2
12


### Reference

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.