Mathematics.

elementary number theory

GCD and LCM

Number Theory20 minDifficulty2 out of 10

You should know: divisibility

Overview

The greatest common divisor (GCD), also called the greatest common factor (GCF), of two or more integers not all zero is the largest positive integer that divides each of them. For two integers x and y, the greatest common divisor is denoted gcd(x, y); for example, gcd(8, 12) = 4. The least common multiple (LCM) is the smallest positive integer that is a multiple of each of the given integers, e.g. lcm(4, 6) = 12. GCD and LCM are dual notions connected by the identity gcd(a,b)·lcm(a,b) = a·b, and both are computed efficiently via the Euclidean algorithm.

Formal Definition

Definition

For nonzero integers a and b:

gcd⁡(a,b)=max⁡{d∈Z+:d∣a and d∣b}\gcd(a,b) = \max\{d \in \mathbb{Z}^+ : d \mid a \text{ and } d \mid b\}
GCD definition
lcm⁡(a,b)=min⁡{m∈Z+:a∣m and b∣m}\operatorname{lcm}(a,b) = \min\{m \in \mathbb{Z}^+ : a \mid m \text{ and } b \mid m\}
LCM definition
gcd⁡(a,b)⋅lcm⁡(a,b)=∣a⋅b∣\gcd(a,b)\cdot\operatorname{lcm}(a,b) = |a \cdot b|
Product identity
gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b) = \gcd(b, a \bmod b)
Euclidean algorithm recursion

Worked Examples

  1. Divisors of 8: {1,2,4,8}. Divisors of 12: {1,2,3,4,6,12}. Largest common divisor is 4.

    gcd⁡(8,12)=4\gcd(8,12) = 4

  2. Use the product identity to get the LCM without listing multiples.

    lcm⁡(8,12)=8×12gcd⁡(8,12)=964=24\operatorname{lcm}(8,12) = \frac{8 \times 12}{\gcd(8,12)} = \frac{96}{4} = 24

Answer: gcd(8,12) = 4, lcm(8,12) = 24.

Practice Problems

Difficulty 3/10

Find gcd(18, 24) and lcm(18, 24).

Difficulty 5/10

Two maintenance tasks are done every 12 and every 18 days respectively, and both happen today. In how many days will they next coincide?

Difficulty 5/10

A floor 240 cm by 180 cm is to be covered exactly by identical square tiles as large as possible with no cutting. What is the tile side length?

Quiz

Two events repeat every 12 and 18 units and start together. They next coincide after:
The relationship linking gcd and lcm of two positive integers a, b is:
The largest identical square tile that exactly covers an m × n floor has side:

Summary

  • gcd(a,b) is the largest integer dividing both a and b; lcm(a,b) is the smallest positive multiple of both.
  • Product identity: gcd(a,b) · lcm(a,b) = |a·b|, letting you compute one from the other.
  • The Euclidean algorithm computes gcd(a,b) efficiently via repeated division: gcd(a,b) = gcd(b, a mod b).

References

  1. WebsiteWikipedia — Greatest common divisor