19. GCD and LCM · Mastering AMC 8

19.10%

GCD and LCM Fundamentals

In this section you will be able to find the GCD and the LCM of two numbers from their prime factorizations.

You have 12 red beads and 18 blue beads. You want identical bracelets that use every bead. What is the most bracelets you can make? That number is the GCD.

Break each number into prime tokens. The tokens both numbers share sit in the overlap of the Venn diagram.

The GCD uses only the shared tokens. The LCM uses every token, but a shared token only once.

Exploreplay first, formulas later

Try this: Which prime tokens sit in the middle for 12 and 18? Press Overlap = GCD. Do they multiply to 6?
Try this: Press Everything = LCM. Why does each shared token appear only once?
Try this: Turn on Exponent table and type 72 and 60. Is the GCD column the lowest exponents or the highest?
Try this: Type two numbers with no shared primes, like 8 and 15. What is the GCD now? And the LCM?

Name it

Definition 19.1.1 · Greatest Common Divisor

The Greatest Common Divisor (GCD) of two or more integers (which are not all zero) 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 19.1.2 · Least Common Multiple

The Least Common Multiple (LCM) of two or more integers (which are not all zero) is the smallest positive integer that is divisible by both the numbers.

Concept 19.1.3

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$ $= \operatorname{lcm}(m, n)$ can be found by taking the highest prime exponents from the prime factorizations of $m$ and $n$ .

Watch itpredict, then reveal

Example 19.1

AMC 8

What is the ratio of the least common multiple of 180 and 594 to the greatest common factor of 180 and 594?

1
Break 180 into primes. How many factors of 2 does it have?

Predict first:
Your prediction

open on YouTube

Contest cornerreal contest problems

Problem 19.5.2

AMC 8

The least common multiple of $a$ and $b$ is 12, and the least common multiple of $b$ and $c$ is 15. What is the least possible value of the least common multiple of $a$ and $c$ ?

Problem 19.5.3

AIME

For how many values of $k$ is $12^{12}$ the least common multiple of the positive integers $6^6$ , $8^8$ , and $k$ ?

Checkpoint for section 19.1

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

19.20%

GCD and LCM Product

In this section you will be able to use GCD × LCM = m × n to find one of the four numbers from the other three.

Two mystery numbers multiply to 1260. Their LCM is 210. You can find their GCD without ever learning the numbers!

Multiply the two numbers and every prime token gets counted. The shared tokens get counted twice: once from each number.

The GCD holds the shared tokens once, and the LCM holds every token once. Together they hold the same tokens as $m \times n$ .

Exploreplay first, formulas later

Try this: Look at the dashed tokens in the middle. How many times do they show up in 12 × 18?
Try this: GCD × LCM uses the middle tokens once in each. Does the readout give the same total as 12 × 18?
Try this: Type 60 and 84. Predict GCD × LCM before you look at the readout.

Name it

Theorem 19.2.1

The product of GCD and LCM of two numbers is equal to the product of the two numbers:

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

Watch itpredict, then reveal

Example 19.2

Suppose we have 2 numbers $m$ and $n$ such that $mn = 1260$ and $\operatorname{LCM}(m, n) = 210$ . Find $\operatorname{GCD}(m, n)$ .

1
You know the product and the LCM. Which identity links them to the GCD?

Predict first:

Try it

Problem 19.5.5(additional)

Omega Learn

If the GCD of 2 numbers is 12 and the LCM of the same 2 numbers is 240, find the product of the numbers.

Checkpoint for section 19.2

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

19.30%

More GCD/LCM Properties

In this section you will be able to scale out a common factor, and use the fact that every common multiple is a multiple of the LCM.

A red light blinks every 4 seconds and a blue light every 6 seconds. They just blinked together. When do they blink together again? And after that?

The common marks are 12, 24, 36 and so on. Look: they are exactly the multiples of the LCM.

Multiplying both numbers by the same $c$ just multiplies the GCD and the LCM by $c$ too.

The last two examples turn GCD and LCM facts into facts about prime exponents. Go one prime at a time!

Exploreplay first, formulas later

Try this: Press Show common marks. Where do the lines for 4 and 6 first meet? Where do they meet next?
Try this: Are all the common marks multiples of the first one? That is Theorem 19.3.3.
Try this: Change the lines to 8 and 12, twice 4 and 6. How did the first common mark change?

Name it

Theorem 19.3.1

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

Theorem 19.3.2

\operatorname{lcm}(ac, bc) = c \cdot \operatorname{lcm}(a, b)

Theorem 19.3.3

If a number is divisible by two numbers $a$ and $b$ , it will also be divisible by $\operatorname{lcm}(a, b)$ .

Watch itpredict, then reveal

Example 19.3

Omega Learn

Let $a$ be the smallest positive perfect cube that's divisible by 15, 22, and 176. If $a = b^3$ , find $b$ .

1
A number divisible by 15, 22 and 176 must be divisible by one single number. Which one?

Predict first:
Your prediction

open on YouTube

Example 19.5

Omega Learn

3 numbers $a$ , $b$ , and $c$ satisfy the conditions that $\gcd(a, b) = 4$ , $\gcd(b, c) = 18$ , and $\operatorname{lcm}(a, c) = 144$ . Find the value of $a + c$ .

1
What must be true about $a$ and $b$ if $\gcd(a, b) = 4$ ?

Example 19.6

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

1
Write $5!$ and $10!$ as prime factorizations. What is the exponent of 2 in $10!$ ?

Predict first:
Your prediction

open on YouTube

Try it

Problem 19.5.6(additional)

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

Contest cornerreal contest problems

Problem 19.5.1

AMC 10

Each piece of candy in a store costs a whole number of cents. Casper has exactly enough money to buy either 12 pieces of red candy, 14 pieces of green candy, 15 pieces of blue candy, or $n$ pieces of purple candy. A piece of purple candy costs 20 cents. What is the smallest possible value of $n$ ?

Problem 19.5.4

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

(Choices from the original contest: 5, 7, 11, 13, 17.)

Problem 19.5.8(additional)

Omega Learn

Three numbers $a$ , $b$ , and $c$ satisfy the conditions that $\gcd(a, b) = 20$ , $\gcd(b, c) = 18$ , and $\operatorname{lcm}(a, c) = 5040$ . Find the sum of all possible values of $a + c$ .

Checkpoint for section 19.3

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

19.40%

Euclidean Algorithm

In this section you will be able to find the GCD of big numbers fast by subtracting the smaller number from the bigger one.

Factoring 186 and 92 is slow. Here is a faster trick: keep cutting the biggest squares you can out of a 186 × 92 rectangle.

Any number that divides both $x$ and $y$ also divides $x - y$ . So taking $y$ away from $x$ never changes the GCD.

Keep subtracting until one number hits 0. The other number is the GCD.

Exploreplay first, formulas later

Try this: Press Cut squares. How many 12 × 12 squares fit in the 30 × 12 rectangle? What is left over?
Try this: Keep cutting. What is the side of the very last square? Is it gcd(30, 12)?
Try this: Turn on One square at a time. Each cut is one subtraction: gcd(x, y) = gcd(x − y, y).
Try this: Try 21 and 13. Why does the last square have side 1?

Name it

Theorem 19.4.1 · Euclidean Algorithm

The Euclidean algorithm states that

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

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

Watch itpredict, then reveal

Example 19.4

Find the GCD of 186 and 92.

1
Take as many 92s away from 186 as you can. What is left?

Predict first:
Your prediction

Contest cornerreal contest problems

Problem 19.5.9(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 19.4

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

19.5

Practice Problems

In this section you will be able to put GCD and LCM exponent counting to work on a tough contest problem.

Time for an AIME problem! Split it into the powers of 2 and the powers of 5, count each, and multiply. 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 19.5.7(additional)

AIME

Let $[r, s]$ denote the least common multiple of positive integers $r$ and $s$ . Find the number of ordered triples $(a, b, c)$ of positive integers for which $[a, b] = 1000$ , $[b, c] = 2000$ , and $[c, a] = 2000$ .