Number Theory · Chapter 23

GCD & LCM

Build GCDs and LCMs from prime exponents, shrink big pairs with the Euclidean algorithm, and use Bézout's identity to see exactly which totals two step sizes can reach.

What's this chapter about?

23.0a GCD and LCM from Prime Factors
23.0b The Euclidean Algorithm
23.0c Bézout's Identity
23.1 Practice Problems

You'll need

open on YouTube

23.0a0%

GCD and LCM from Prime Factors

In this section you will be able to find a GCD or an LCM from prime factorizations, and use GCD × LCM = m × n.

Ten horses run laps of $1, 2, \ldots, 10$ minutes. When are they all back at the start together? They meet at every common multiple of $1$ through $10$ , and the first time is the LCM, $2520$ .

Every GCD and LCM question becomes easy once you write the numbers as products of primes. Shared primes go in the middle of the diagram. The GCD keeps only what both numbers share; the LCM keeps everything.

Look: for each prime, the GCD takes the lower exponent and the LCM takes the higher one. Lower plus higher is the sum of both exponents, and that is why $\gcd(m, n) \cdot \operatorname{lcm}(m, n) = mn$ .

Exploreplay first, formulas later

Try this: Press Overlap = GCD. Which prime tokens are lit? Multiply them: do you get gcd(24, 36) = 12?
Try this: Now press Everything = LCM and open the exponent table. Why does the LCM take the higher exponent of each prime?
Try this: Press GCD × LCM. The shared tokens count twice. Why does that make GCD × LCM = 24 × 36?

Name it

Definition 23.0.1 · Greatest Common Divisor

The Greatest Common Divisor (GCD) of two or more nonzero integers is the largest positive integer that divides each of them.

It is also called the GCF (Greatest Common Factor). The two names mean the same thing.

Definition 23.0.2 · Least Common Multiple

The Least Common Multiple (LCM) of two or more nonzero integers is the smallest positive integer that is divisible by each of them.

Concept 23.0.3 · GCD and LCM from prime factorizations

$\gcd(m, n)$ takes the lowest exponent of each prime in the prime factorizations of $m$ and $n$ .

$\operatorname{lcm}(m, n)$ takes the highest exponent of each prime.

For example, $24 = 2^{3} \cdot 3$ and $36 = 2^{2} \cdot 3^{2}$ , so $\gcd(24, 36) = 2^{2} \cdot 3 = 12$ and $\operatorname{lcm}(24, 36) = 2^{3} \cdot 3^{2} = 72$ .

Theorem 23.0.4 · GCD × LCM

The product of the GCD and the LCM of two numbers equals the product of the two numbers:

\gcd(m, n) \cdot \operatorname{lcm}(m, n) = m \cdot n.

Theorem 23.0.5 · Pulling out a common factor

If two numbers have a common factor $c$ , then

\gcd(ac, bc) = c \cdot \gcd(a, b).

Watch itpredict, then reveal

Example 23.1

Omega Learn

Two numbers $a$ and $b$ satisfy the condition

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

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

GCD = 2 × 2 = 4

prime	in 24	in 4	lowest	highest
2	3	2	2	3
3	1	0	0	1

1
Since $a = 2b$ , what is $\gcd(a, b) = \gcd(2b, b)$ ?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Try it

Problem 23.1.7(additional)

AMC 12

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

Problem 23.1.8(additional)

AMC 10

There are $10$ horses, named Horse $1$ , Horse $2$ , $\ldots$ , 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$ ?

Contest cornerreal contest problems

Problem 23.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$ ?

Problem 23.1.4

AMC 10

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

a \cdot b + 63 = 20 \cdot \operatorname{lcm}(a, b) + 12 \cdot \gcd(a, b),

where $\gcd(a, b)$ denotes the greatest common divisor of $a$ and $b$ , and $\operatorname{lcm}(a, b)$ denotes their least common multiple?

Problem 23.1.6

AMC 12

Suppose that $a, b, c$ , and $d$ are positive integers satisfying all of the following relations:

\begin{aligned} abcd &= 2^{6} \cdot 3^{9} \cdot 5^{7} \\ \operatorname{lcm}(a, b) &= 2^{3} \cdot 3^{2} \cdot 5^{3} \\ \operatorname{lcm}(a, c) &= 2^{3} \cdot 3^{3} \cdot 5^{3} \\ \operatorname{lcm}(a, d) &= 2^{3} \cdot 3^{3} \cdot 5^{3} \\ \operatorname{lcm}(b, c) &= 2^{1} \cdot 3^{3} \cdot 5^{2} \\ \operatorname{lcm}(b, d) &= 2^{2} \cdot 3^{3} \cdot 5^{2} \\ \operatorname{lcm}(c, d) &= 2^{2} \cdot 3^{3} \cdot 5^{2} \end{aligned}

What is $\gcd(a, b, c, d)$ ?

Problem 23.1.13(additional)

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$ ?

Checkpoint for section 23.0a

Get 2 of 3 right to master this section. One try each, no hints.

23.0b0%

The Euclidean Algorithm

In this section you will be able to find the GCD of big numbers, or of expressions in n, by repeated subtraction.

What is $\gcd(186, 92)$ ? Factoring works, but there is a faster way: take $92$ away from $186$ twice. Anything that divides both numbers also divides what is left.

Cut the biggest possible squares off an $x \times y$ rectangle. The leftover strip has the same common divisors as the rectangle you started with. Keep cutting: the last square’s side is the GCD.

The same trick works on expressions. To find $\gcd(100 + n^{2},\ 100 + (n + 1)^{2})$ , subtract one from the other and the $n^{2}$ disappears.

Exploreplay first, formulas later

Try this: Press Cut squares once. Two 92 × 92 squares come off. Why is gcd(186, 92) the same as gcd(2, 92)?
Try this: Press Finish. What is the side of the last square, and why does it divide both 186 and 92?
Try this: Turn on One square at a time and set the sides to 21 and 13. How many cuts does it take to reach 1?

Name it

Theorem 23.0.6 · Euclidean Algorithm

\gcd(x, y) = \gcd(x - ky,\ y)

where $x > y$ and $k$ is a positive integer.

Watch itpredict, then reveal

Example 23.2

AIME

The numbers in the sequence $101, 104, 109, 116, \ldots$ are of the form $a_n = 100 + n^{2}$ , where $n = 1, 2, 3, \ldots$ For each $n$ , let $d_n$ be the greatest common divisor of $a_n$ and $a_{n+1}$ . Find the maximum value of $d_n$ as $n$ ranges through the positive integers.

1
What is $a_{n+1} - a_n$ ?

Predict first:
Your prediction

open on YouTube

Contest cornerreal contest problems

Problem 23.1.3

AIME

This problem also appears in the book as 22.1.5.

What is the largest positive integer $n$ for which $n^{3} + 100$ is divisible by $n + 10$ ?

Problem 23.1.15(additional)

AMC 10

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

\gcd(63, n + 120) = 21 \quad\text{and}\quad \gcd(n + 63, 120) = 60.

What is the sum of the digits of $n$ ?

Checkpoint for section 23.0b

Get 2 of 3 right to master this section. One try each, no hints.

23.0c0%

Bézout's Identity

In this section you will be able to decide which totals ax + by can reach, using Bézout's identity.

A token sits at $0$ and can jump $6$ or $10$ to the left or right. Can it ever land on $3$ ? Every jump keeps it on an even number, so no.

Every total $6x + 10y$ is a multiple of $\gcd(6, 10) = 2$ . The surprise is the other direction: every multiple of $2$ can be reached. Running the Euclidean algorithm backwards finds the jumps.

So $ax + by = c$ has integer solutions exactly when $\gcd(a, b)$ divides $c$ . Look: this also proves that two expressions are coprime. If some combination of them equals $1$ , their GCD must be $1$ .

Exploreplay first, formulas later

Try this: With steps 6 and 10, try to land on 3. Now try 4. Which one is possible, and why?
Try this: Turn on Light up reachable cells. Every lit cell is a multiple of one number. Which one?
Try this: Set the target to 2 and press Find x, y. Compare with gcd(6, 10) from the Euclid tiles: the smallest positive landing cell is the last square.

Name it

Theorem 23.0.8 · Bézout's Identity

The equation

ax + by = c

has integer solutions $x, y$ if and only if $\gcd(a, b)$ divides $c$ .

Contest cornerreal contest problems

Problem 23.1.2

IMO

This problem also appears in the book as 22.1.4.

Prove that the fraction $\dfrac{21n+4}{14n+3}$ is irreducible for every natural number $n$ .

This one asks for a proof. Write yours on paper, use the hints if you need them, then compare it with the written proof.

Checkpoint for section 23.0c

Get 2 of 3 right to master this section. One try each, no hints.

23.1

Practice Problems

In this section you will be able to mix prime exponents, Euclid and Bézout on harder contest problems.

Time to mix it all up. These problems need prime exponents, Euclid’s subtraction and a little parity, often at once. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 23.1.5

AMC 10/12

Suppose $a$ , $b$ , and $c$ are positive integers such that

\frac{a}{14} + \frac{b}{15} = \frac{c}{210}.

Which of the following statements are necessarily true?

I. If $\gcd(a, 14) = 1$ or $\gcd(b, 15) = 1$ or both, then $\gcd(c, 210) = 1$ .

II. If $\gcd(c, 210) = 1$ , then $\gcd(a, 14) = 1$ or $\gcd(b, 15) = 1$ or both.

III. $\gcd(c, 210) = 1$ if and only if $\gcd(a, 14) = \gcd(b, 15) = 1$ .

Problem 23.1.9(additional)

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 $a^{2} + b^{2} + c^{2}$ ?

Problem 23.1.10(additional)

AMC 12

This problem also appears in the book as 23.1.7.

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

Problem 23.1.11(additional)

AMC 12

Let $n$ be the smallest positive integer such that $n$ is divisible by $20$ , $n^{2}$ is a perfect cube, and $n^{3}$ is a perfect square. What is the number of digits of $n$ ?

Problem 23.1.12(additional)

AMC 12

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

Problem 23.1.14(additional)

AIME

For how many ordered pairs of positive integers $(x, y)$ , with $y < x \le 100$ , are both $\dfrac{x}{y}$ and $\dfrac{x+1}{y+1}$ integers?

Problem 23.1.16(additional)

AIMEChallenge

Consider the sequence $(a_k)_{k \ge 1}$ of positive rational numbers defined by $a_1 = \dfrac{2020}{2021}$ and for $k \ge 1$ , if $a_k = \dfrac{m}{n}$ for relatively prime positive integers $m$ and $n$ , then

a_{k+1} = \frac{m + 18}{n + 19}.

Determine the sum of all positive integers $j$ such that the rational number $a_j$ can be written in the form $\dfrac{t}{t+1}$ for some positive integer $t$ .

Problem 23.1.17(additional)

AIMEChallenge

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