[Introduction to Number Theory Series Part 4] How Do GCD and LCM Reveal Shared Structure?

When two integers are viewed together, two summary values appear over and over again: the gcd and the lcm. The gcd tells us about shared divisor structure, while the lcm tells us about the smallest common multiple structure that contains both numbers.

What this post covers

• The meaning of the gcd and lcm
• How to read them through divisor lists and multiple lists
• Why prime factorization makes both clearer
• How this leads into the Euclidean algorithm

Key terms

• greatest common divisor: the largest positive common divisor of two integers
• least common multiple: the smallest positive integer that is a multiple of both integers
• divisibility: the relation that decides whether one integer divides another
• prime factorization: expressing an integer as a product of primes

What is the gcd?

The gcd of two integers is the largest positive integer that divides both.

For 12 and 18:

• divisors of 12: 1, 2, 3, 4, 6, 12
• divisors of 18: 1, 2, 3, 6, 9, 18

The common divisors are 1, 2, 3, 6, so

$$\gcd(12,18)=6.$$

What is the lcm?

The lcm of two integers is the smallest positive common multiple.

For 12 and 18:

• multiples of 12: 12, 24, 36, 48, ...
• multiples of 18: 18, 36, 54, ...

The first common positive multiple is 36, so

$$\operatorname{lcm}(12,18)=36.$$

Why prime factorization helps

Write

$$12=2^2\times 3, \qquad 18=2\times 3^2.$$

For the gcd, we take the smaller exponent of each shared prime, because the result must divide both numbers. If we took a larger exponent, the result would no longer divide one of them:

$$\gcd(12,18)=2^1\times 3^1=6.$$

For the lcm, we take the larger exponent of each relevant prime, because the result must be a multiple of both. If we took a smaller exponent, the result would fail to include enough of one factorization:

$$\operatorname{lcm}(12,18)=2^2\times 3^2=36.$$

A useful identity

For positive integers a and b, we have

$$\gcd(a,b)\operatorname{lcm}(a,b)=ab.$$

For 12 and 18:

$$6 \times 36 = 216 = 12 \times 18.$$

Why does the gcd matter more later?

The gcd is not only a descriptive value. It connects directly to:

• coprimality
• Bézout's identity
• integer-solution conditions for equations
• modular inverses
• fast algorithms such as the Euclidean algorithm

Common mistakes

1. Mixing up the gcd and lcm rules

• gcd: smaller exponents
• lcm: larger exponents

2. Forgetting that the lcm is the smallest positive common multiple

That positivity condition matters in the standard definition.

3. Treating the gcd as just a classroom calculation

The gcd later becomes a structural tool for equations, congruences, and algorithms.

Wrap-up

The gcd summarizes common divisor structure. The lcm summarizes the smallest common multiple structure. Together they show two complementary ways integers can overlap.

Next we study the Euclidean algorithm, the fast method that computes the gcd by repeatedly shrinking the problem.