Suppose we have two integers a and b. We say that the number d is the greatest common divisor of a and b if and only if, d \mid a and d \mid b and if c \mid a and c \mid b, then c \leq d. Condition 1 says that d is a common divisor of a and b, and condition 2 says that it is the greatest such divisor.
Note that if a and b are not both zero, then the set of common divisors of a and b is a set of integers that is bounded above by the largest of a, b, -a, and -b. Hence, from the well ordering principle for the integers, the set has a largest element, so the greatest common divisor of a and b exists and is unique. Note that gcd(0,0) is not defined, and when gcd(a,b) is defined, then it is positive. In fact, gcd(a, b) \geq 1 because 1 \mid a and 1 \mid b for all a and b.
Properties of GCD
- gcd(a, 0) = |a|
- gcd(a, b) = gcd(b, a)
- gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)
- gcd(a + mb, b) = gcd(a, b)
- gcd(ca, cb) = c * gcd(a, b)
- gcd(a, b) = gcd(a – b, b)
- gcd(a, b) = gcd(b, a \mod b)
- If m \mid a and m \mid b then gcd(a/m, b/m) = gcd(a, b)/m
- If gcd(a, b) = d, then gcd(a/d, b/d) = 1
- Every common divisor of a and b is also a divisor of gcd(a, b)
- If gcd(a, b) = d, then there exists integers x, y such that ax + by = d
Mathematical Proofs
If a and b are not both 0, and let d = gcd(a, b). Then d is the smallest positive integer that can be expressed as a linear combination of a and b, d = sa+tb.
The set of all linear combinations of a and b contains a smallest integer m such that, m = sa+tb. On the right hand side of the equation we see that d \mid sa abd d \mid tb. Hence, in the left hand side, d \mid m. The smallest integer that d can divide is d. So, m = d. So, d is the smallest positive integer that can be expressed as a linear combination of a and b. It is known as Bézout’s identity.
If c is any common divisor of a and b, then c divides gcd(a, b).
Let d = gcd(a, b). Now we can express d as a linear combination, d = sa + tb. Since, the right hand side is divisible by c (c \mid a and c \mid b), in the left hand side c must divide d.
gcd(ca, cb) is the same as c\times gcd(a, b)
Let d = gcd(a, b). So we can say, d \mid a and d \mid b, which implies d \mid ca and d \mid cb. Hence dc \mid ca and dc \mid cb. As d is the greatest common divisor of a, b, we can say that dc is the greatest common divisor of ca, cb. So, gcd(ca, cb) = dc = c \times gcd(a, b)
If m \mid a and m \mid b then gcd(a/m, b/m) = gcd(a, b)/m
Let d = gcd(a, b), since m \mid a and m \mid b, so m is common divisor of a and b and m \leq d. We have to prove that gcd(a / m, b / m) = d / m. From d = sa + tb, it follows that m \mid d. We know that gcd(ca, cb) is the same as c\times gcd(a, b). Hence, gcd(a/m, b/m) = \frac{1}{m} \times gcd(a, b)
If d = gcd(a, b) then gcd(a / d, b / d) = 1
Let us assume that, gcd(a / d, b / d) = 1. We know that gcd(ca, cb) is the same as c\times gcd(a, b). Hence, gcd(a, b) = d * gcd( a / d, b / d ). In order to satisfy the equation gcd(a / d, b / d) must be equal to 1.
gcd(a, b) is equal gcd(b, a \mod b)
Let d = gcd(a, b). We know that since d \mid a and d \mid b, it follows from b = qa + r that d \mid r. Thus d is a common divisor of a and r. Now we need to make sure that d is the greatest of all common divisors of a and r. Let c be a common divisor of a and r. From b = qa + r, if c \mid a and c \mid r, then also c \mid b. Now c \leq d, because d is the largest of all common divisors. So we can conclude that gcd(a, b) = gcd(b, a \mod b) = gcd(b, r) where r = a \mod b.
Prime Factorization to Compute GCD
If we have two integers a, b and we can find gcd(a, b) from the prime factorization of a, b. Suppose a = 2^{a_1} \times 3^{a_2} \times 5^{a_3}… and b = 2^{b_1} \times 3^{b_2} \times 5^{b_3}…, then we can write a \times b = 2^{a_1 + b_1} \times3^{a_2+b_2} \times5^{a_3 + b_3}…. Now, if we take the min(a_i, b_i) for each p_i we get the common portion for that p_i. In this way, we can keep multiplying the common portions to get gcd(a, b). Thus mathematically if ab = p_1^{a_1 + b_1} \times p_2^{a_2 + b_2} \times p_3^{a_3 + b_3} \times \dots \times p_n^{a_n + b_n} then, gcd(a, b) = \prod p_i^{min(a_i , b_i)}
Euclidean Algorithm to Compute GCD
One of the ways to compute the GCD of two integers is to list down the divisors of a and b and pick the largest one. But this naive method takes a lot of time. Another way is the Euclidean Algorithm. This is much more efficient and the time complexity of this algorithm is roughly O(log_2n). This algorithm is based on the fact that when a = bq + r, then we can say that gcd(a, b) = gcd(b, r). We know from the division algorithm, a = bq + r, where r is the remainder when a is divided by b. So, r = a \mod b.
The division algorithm is nothing but a proof that the long divisions that we used to do in schools was right. Let’s take a look at the proof, Let d = gcd(a, b). From the division algorithm we know that a = bq + r. We know, d \mid a and d \mid b, which implies that d \mid r. Again let c is any common divisor of b and r, then we know c \mid b and c \mid r which implies c \mid a. Both parts of the definition of GCD are satisfied and hence Thus gcd(a, b) = gcd(b, r) where r = a \mod b. Let’s now implement the algorithm. As we have seen, gcd(a, b) = gcd(b, a \mod b) which is a recurrence relation and this relation can be used to calculate GCD of two integers recursively. When we reach b = 0, we can say that gcd(a, 0) = a.
int gcd( int a, int b ) {
if ( b == 0 ) return a;
return gcd( b, a % b );
}
We can also implement the euclidean algorithm without recursive calls, which may reduce the recursion overhead. Thus making it a bit faster than the recursive one.
int gcd( int a, int b ) {
while( b != 0 ) {
int new_a = b;
b = a % b;
a = new_a;
}
return a;
}
Related problems
UVa 11417 – GCD
SPOJ GCD – Greatest Common Divisor
CF 664A – Complicated GCD
References
Wikipedia – Greatest Common Divisor
Khan Academy – Euclidean Algorithm
No Comments
Leave a comment Cancel