OmegaLearn.org Chapter 24.

GCD & LCM

Definition 24.0.1 (Greatest Common Divisor). The Greatest Common Divisor (GCD) of
two or more non-0 integers is the largest positive integer that divides each of the integers.
Note: This is also known as GCF (Greatest Common Factor), and the terms GCF and GCD
are often used interchangeably.

Definition 24.0.2 (Least Common Multiple). The Least Common Multiple (LCM) of two
or more non-0 integers is the smallest positive integer that is divisible by both the numbers.

Concept 24.0.3
GCD/LCM Greatest common divisor of m and n = GCD(m, n) can be found by taking
the lowest prime exponents from the prime factorizations of m and n.

Least common multiple of m and n = LCM (m, n) can be found by taking the high-
est prime exponents from the prime factorizations of m and n.

Theorem 24.0.4
The product of GCD and LCM of two numbers is equal to the product of the two
numbers:
GCD(m, n) · LCM (m, n) = m · n

Theorem 24.0.5
If two numbers have a common factor c, then

gcd(ac, bc) = c · gcd(a, b)

Example 24.1 (Omega Learn)

Two numbers a and b satisfy the condition

lcm(gcd(24, a), gcd(a, b)) = lcm(gcd(24, b), gcd(a, b))

If a = 2b, what is the smallest possible value of a + b?

Video Solution

261
OmegaLearn.org Chapter 24. GCD & LCM

Theorem 24.0.6 (Euclidean Algorithm)

The Euclidean algorithm states that

gcd(x, y) = gcd(x − ky, y)

where x > y and k is a positive integer.

Remark 24.0.7
We can apply the Euclidean Algorithm multiple times to easily find the GCD of large
numbers since after applying the Euclidean algorithm, we know have 2 smaller numbers
which we can apply the Euclidean Algorithm again until we get 2 very small numbers.
For example,

gcd(186, 92) = gcd((186 − (2 · 92)), 92)

= gcd(2, 92)
= gcd(2, (92 − (2 · 46)))
= gcd(2, 0)
=2

Example 24.2 (AIME)

The numbers in the sequence 101, 104, 109, 116,. . . are of the form an = 100 + n2 , where
n = 1, 2, 3, . . . For each n, let dn be the greatest common divisor of an and an+1 . Find
the maximum value of dn as n ranges through the positive integers.

Video Solution

Theorem 24.0.8 (Bezout’s Identity)

Integer solutions to the equation
ax + by = c
will only exist if and only if gcd(a, b) divides c

262
OmegaLearn.org Chapter 24. GCD & LCM

24.1 Practice Problems

Problem 24.1.1 (AMC 10)

Let a, b, c, and d be positive integers such that gcd(a, b) = 24, gcd(b, c) = 36, gcd(c, d) =
54, and 70 < gcd(d, a) < 100. Which of the following must be a divisor of a?
(A) 5 (B) 7 (C) 11 (D) 13 (E) 17

Video Solution

Problem 24.1.2 (IMO)

Prove that the fraction 21n+4

14n+3
is irreducible for every natural number n.

Video Solution

Problem 24.1.3 (AIME)

What is that largest positive integer n for which n3 + 100 is divisible by n + 10?

Video Solution

Problem 24.1.4 (AMC 10)

How many ordered pairs (a, b) of positive integers satisfy the equation

a · b + 63 = 20 · lcm(a, b) + 12 · gcd(a, b),

where gcd(a, b) denotes the greatest common divisor of a and b, and lcm(a, b) denotes
their least common multiple?

Video Solution

263
OmegaLearn.org Chapter 24. GCD & LCM

Additional Problems
Problem 24.1.5 (AMC 12)

Let N be the second smallest positive integer that is divisible by every positive in-
teger less than 7. What is the sum of the digits of N ?

Problem 24.1.6 (AMC 10)

There are 10 horses, named Horse 1, Horse 2, . . . , Horse 10. They get their
names from how many minutes it takes them to run one lap around a circular race track:
Horse k runs one lap in exactly k minutes. At time 0 all the horses are together at the
starting point on the track. The horses start running in the same direction, and they
keep running around the circular track at their constant speeds. The least time S > 0,
in minutes, at which all 10 horses will again simultaneously be at the starting point is
S = 2520. Let T > 0 be the least time, in minutes, such that at least 5 of the horses are
again at the starting point. What is the sum of the digits of T ?

Problem 24.1.7 (AMC 12)

Suppose a, b, c are positive integers such that

a + b + c = 23

and
gcd(a, b) + gcd(b, c) + gcd(c, a) = 9.
What is the sum of all possible distinct values of a2 + b2 + c2 ?

Problem 24.1.8 (AMC 12)

Let N be the second smallest positive integer that is divisible by every positive in-
teger less than 7. What is the sum of the digits of N ?

264
OmegaLearn.org Chapter 24. GCD & LCM

Problem 24.1.9 (AMC 12)

Let n be the smallest positive integer such that n is divisible by 20, n2 is a perfect
cube, and n3 is a perfect square. What is the number of digits of n?

Problem 24.1.10 (AMC 12)

Mary chose an even 4-digit number n. She wrote down all the divisors of n in in-
n
creasing order from left to right: 1, 2, . . . , , n. At some moment Mary wrote 323 as a
2
divisor of n. What is the smallest possible value of the next divisor written to the right
of 323?

Problem 24.1.11 (AMC 12)

How many positive integers n are there such that n is a multiple of 5, and the least
common multiple of 5! and n equals 5 times the greatest common divisor of 10! and n?

Problem 24.1.12 (AIME)

For how many ordered pairs of positive integers (x, y), with y < x ≤ 100, are both
x
y
and x+1
y+1
integers?

Problem 24.1.13 (AMC 10)

Let n be the least positive integer greater than 1000 for which

gcd(63, n + 120) = 21 and gcd(n + 63, 120) = 60.

What is the sum of the digits of n?

Problem 24.1.14 (AIME)

Consider the sequence (ak )k≥1 of positive rational numbers defined by a1 = 2020
2021
and for
k ≥ 1, if ak = m
n
for relatively prime positive integers m and n, then

265
OmegaLearn.org Chapter 24. GCD & LCM

m + 18
ak+1 = .
n + 19
Determine the sum of all positive integers j such that the rational number aj can be
written in the form t+1
t
for some positive integer t.

Problem 24.1.15 (AIME)

Find the number of ordered pairs (m, n) such that m and n are positive integers in
the set {1, 2, ..., 30} and the greatest common divisor of 2m + 1 and 2n − 1 is not 1.

Answers
24.1 24

24.2 401

24.1.1 13

24.1.2 −N A−

24.1.3 890

24.1.4 2

24.1.5 3

24.1.6 3

24.1.7 438

24.1.8 13

24.1.9 7

24.1.10 340

266
OmegaLearn.org Chapter 24. GCD & LCM

24.1.11 48

24.1.12 85

24.1.13 18

24.1.14 059

24.1.15 295

267