GCD and LCM: Essential Tools for Competitive Programming

by

GCD and LCM is a foundational concept in number theory and widely used in areas such as simplifying fractions, cryptography, and solving Diophantine equations.

GCD (Greatest Common Divisor)

  • GCD of two numbers is the largest number that divides both without leaving a remainder.
  • Also known as, HCF(highest common factor)

GCD of 12 and 18

  • Factors of 12: 1, 2, 3, 4, 6, 12
  • Factors of 18: 1, 2, 3, 6, 9, 18
  • Common factors: 1, 2, 3, 6

So, the GCD is 6

Euclidean Algorithm for GCD

This is an efficient method to find GCD:

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



gcd(a, b) = gcd(b, a % b)
Repeat until b becomes 0.
When b is 0, a is the GCD.
Python

gcd(1220, 516) => gcd(516,188) => gcd(188,140) 

gcd(188,140) => gcd(140,48) => gcd(48,44)

gcd(48,44) => gcd(44,4) => gcd(4,0) => 4
Python

Code

def gcd(a, b):
    # Euclidean Algorithm
    while b != 0:
        a, b = b, a % b  # Replace a with b, and b with a mod b
    return a
Python

Euclidean Algorithm, Why it works:

It keeps reducing the problem into smaller pairs while preserving the GCD.

In the Euclidean algorithm:

gcd(a,b) = gcd(b,a%b)
Python

As we know, standard Modulo concept

a % b = a - q·b for some integer q.
Python

So, you’re effectively replacing (a, b) with (b, a – q·b) — and since any common divisor of a and b also divides a – q·b, the GCD is preserved.

That’s why you can keep reducing the numbers like this without changing the result.

LCM (Least Common Multiple)

The LCM of two integers is the smallest number that is a multiple of both numbers.

Find LCM of 12 and 18.

  • Multiples of 12: 12, 24, 36, 48, 60…
  • Multiples of 18: 18, 36, 54, 72…
  • Common multiples: 36, 72, …

So, the LCM is 36

Relation between GCD and LCM:

For any two positive integers a and b:

LCM(a,b) × GCD(a,b) = a×b
Python

Code

def lcm(a, b):
    # LCM formula: (a * b) // GCD(a, b)
    return abs(a * b) // gcd(a, b)
Python

Using math module (Python 3.5+)

import math

a = 12
b = 18

gcd = math.gcd(a, b)
lcm = abs(a * b) // gcd

print("GCD:", gcd)
print("LCM:", lcm)
Python

Why Euclidean algorithm is efficient?

Because a % b is always smaller than b, the numbers shrink quickly. In fact, it finishes in logarithmic time.

O(log min(a,b)) => O(log n)
Python

GCD Properties

  • Commutative: gcd(a,b)=gcd(b,a)
  • Associative: gcd(a,gcd(b,c))=gcd(gcd(a,b),c)
  • If a divides b, then: gcd(a,b)=a
  • GCD with 0: gcd(a,0)= |a|
  • GCD for consecutive Numbers: gcd(n,n+1)=1
  • Two numbers are coprime if gcd(a, b) == 1
  • consecutive integers are always coprime
  • If gcd(a, b) = d, then: a%b=a%(b%d)

LCM Properties

  • Associative: lcm(a,lcm(b,c))=lcm(lcm(a,b),c)

Practice

Beginner Level

ProblemConcepts
1071. Greatest Common Divisor of StringsGCD logic with strings
231. Power of TwoBinary tricks, GCD base
136. Single NumberXOR logic (good warm-up)

Intermediate Level

ProblemConcepts
149. Max Points on a LineGCD for slope normalization
365. Water and Jug ProblemLinear Diophantine Eq. (GCD-based)
2447. Number of Subarrays With GCD Equal to KSliding window + GCD

Advanced Level

ProblemConcepts
1250. Check If It Is a Good ArrayBézout’s Identity, GCD of array
1998. GCD Sort of an ArrayUnion-Find + GCD
1185. Day of the WeekLCM indirectly used (date calc)

Bonus Math-Based

ProblemConcepts
1014. Best Sightseeing PairIndirect use of number theory
172. Factorial Trailing ZeroesMultiples, primes — LCM logic insight
1492. The kth Factor of nDivisors, used in LCM/GCD contexts

Conclusion

Understanding the GCD and the Euclidean Algorithm provides a solid base for tackling a wide range of computational and mathematical problems. Its efficiency—thanks to logarithmic complexity—makes it ideal for use even with very large numbers. Mastering this concept unlocks deeper topics such as LCM computation, coprimality checks, modular arithmetic, and plays a critical role in many competitive programming challenges.

Leave a Comment