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.

[2] https://www.geeksforgeeks.org/gcd-two-array-numbers/

[3] https://www.geeksforgeeks.org/lcm-of-given-array-elements/

Leave a Reply

Your email address will not be published. Required fields are marked *