GCD and All it’s Quirks

So from past 3–4 days I am solving Leetcode problems, and they all have GCD(Greatest Common Divisor) use in some form or other. So I decided to learn more about GCD and write a small article about it.

The greatest common divisor (GCD) of two or more integers, not all zero, is the largest positive integer that divides each of them without a remainder.

1. Euclidean Algorithm — For getting GCD of any two numbers a very famous algorithm is Euclidean, where we keep replacing the pair (a, b) with (b, a mod b) until the second number becomes 0, and at that point we get our answer.

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

This algorithm takes O(log(min(a,b))) time.

2. Subtraction Form — There is also this subrtraction property that can be useful when calculating GCD of numbers in a range.

gcd(a, b) = gcd(a − b, b);

gcd(a₁, a₂, …, aₙ) = gcd(a₁, a₂−a₁, a₃−a₂, …);

3. Relation with LCM — For any two numbers the product of their GCD and LCM equals the product of the numbers. This relation is useful to compute LCM of two numbers as it can be a large value.

4. GCD of Negative Numbers — For Negative numbers, we take the absolute values of numbers and then calculate their GCD. And if one of the numbers is 0, then the GCD becomes the absolute value of other number.

GCD(-a,-b) = GCD(a,b)
GCD(-a,0) = GCD(a,0) = a
GCD(0,0) = 0

5. GCD of more than two numbers — GCD is associative, so to find the GCD of a whole array we don’t need anything special. We just take two numbers at a time: gcd(a, b, c) = gcd(gcd(a, b), c). So we start with the first number and keep taking GCD with the next one. A nice bonus is that this is fast — the running GCD shrinks very quickly and can only get smaller, so it stays cheap even for a large array.

6. Bezout’s Identity-— It means the smallest positive number you can make from ax + by (for integers x, y) is exactly gcd(a, b) — and you can only ever make multiples of the GCD, nothing else. This is very useful when answering puzzles like -

• Can I measure exactly X litres using jugs of size a and b?
• Can I reach target at distance X using only steps of size a and b?

The answers to these questions depend on the GCD of a and b. if X is a multiple of gcd(a,b), then our answer is yes.

Get Div CS Nook’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

7. Now some honorary mentions where GCD does its magic —

• gcd(aᵐ − 1, aⁿ − 1) = a^gcd(m,n) − 1
• gcd(n, n+1) = 1
• gcd(ka, kb) = k · gcd(a, b)

So yes, this is all that I found interesting about GCD, there are many more complex concepts where GCD is useful, and it makes our life easier.

Leetcode problems in case you want to try some hands on work with GCDs

• 1979. Find Greatest Common Divisor of Array
• 1071. Greatest Common Divisor of Strings
• 914. X of a Kind in a Deck of Cards
• 2807. Insert Greatest Common Divisors in Linked List
• 2543. Check if Point Is Reachable
• 3312. Sorted GCD Pair Queries

References:

• https://www.geeksforgeeks.org/dsa/euclidean-algorithms-basic-and-extended/
• https://math.stackexchange.com/questions/495119/what-is-gcd0-0

I am reviving my technical writing skills by writing about Computer Science concepts, so if you liked this article, follow along. :)