How to Find the GCD and LCM of Two Numbers

Two numbers raise two natural questions. What is the biggest number that divides both of them, and what is the smallest number that both of them divide? The first answer is the GCD and the second is the LCM. The prime fingerprints from 3.3 give you both.

Problem

A maker has ribbons of 56 cm and 70 cm. She wants to cut both into equal whole-centimeter pieces with no scrap. List the divisors of each and find the longest piece length that works for both.

Show a hint

A piece length works for a ribbon only if it divides that ribbon's length with nothing left over. So write the divisors of 56 and the divisors of 70, then look for the numbers that show up on both lists.
The divisors of 56 are $1, 2, 4, 7, 8, 14, 28, 56$ and the divisors of 70 are $1, 2, 5, 7, 10, 14, 35, 70$ . Which numbers sit on both lists, and which of those is biggest?

Show the full solution

A piece length works on a ribbon only if it divides that length evenly, so write out both divisor lists.

56 : 1, 2, 4, 7, 8, 14, 28, 56

70 : 1, 2, 5, 10, 7, 14, 35, 70

The numbers on both lists are

1, 2, 7,

and

14

, and the largest is

14

centimeters. That gives

56 = 14 \times 4

and

70 = 14 \times 5

, four pieces from one ribbon and five from the other with no scrap.

Problem

Use the fingerprints

168 = 2^{3} \times 3 \times 7

and

180 = 2^{2} \times 3^{2} \times 5

to find

\gcd (168, 180)

. Take each shared prime to its lower power.

Show a hint

Go prime by prime. For the prime $2$ , the number $168$ carries three of them and $180$ carries two. A divisor of both can lean on at most the smaller count, two. Do the same for $3$ , and then ask whether $5$ or $7$ can appear at all.
A prime that lives in only one fingerprint cannot divide the other number, so it cannot appear in the gcd. Take each shared prime to the smaller of its two powers, then multiply those together.

Show the full solution

Go prime by prime and keep the smaller power. For

2

, that is

2^{2}

. For

3

, it is

3^{1}

. The

5

sits only in

180

and the

7

only in

168

, so neither can divide both numbers.

\gcd (168, 180) = 2^{2} \times 3 = 12

A common divisor can only use primes both numbers carry, and never more copies than the smaller supply has.

Problem

A volunteer has 90 soap bars and 126 seed packets. Every kit holds the same counts with no leftovers. With

\gcd (90, 126)

, find the greatest number of identical kits she can build.

Show a hint

The number of kits must divide $90$ evenly, so the soap splits with none left over, and it must also divide $126$ evenly for the seeds. So the kit count is a common divisor of $90$ and $126$ , and she wants the greatest one.
Take each shared prime to its lower power. Both numbers carry $2$ , both carry $3^{2}$ , but $5$ belongs only to $90$ and $7$ only to $126$ . Multiply the shared part.

Show the full solution

The kit count has to divide both totals evenly, so it is a common divisor of

90

and

126

, and she wants the greatest one.

90 = 2 \times 3^{2} \times 5, 126 = 2 \times 3^{2} \times 7

Both carry one

2

and both carry

3^{2}

, while

5

belongs to

90

alone and

7

126

alone.

\gcd (90, 126) = 2 \times 3^{2} = 18

Each kit holds

90 \div 18 = 5

bars and

126 \div 18 = 7

packets. Splitting two quantities into as many identical full shares as possible is always a gcd question.

Problem

Two gears have 24 and 35 teeth, with

24 = 2^{3} \times 3

and

35 = 5 \times 7

. They share no prime factor. How many teeth must pass the meshing point before the red teeth touch again?

Show a hint

The red teeth realign after a count of teeth that both $24$ and $35$ divide evenly, so you want the smallest number that is a multiple of both. Start listing multiples of $35$ and check which is the first that $24$ also divides.
Because $24$ and $35$ share no prime factor, a number divisible by both must carry all of $24$ 's primes and all of $35$ 's primes with no overlap to save on. The smallest such number is just $24 \times 35$ .

Show the full solution

The red teeth meet again at the first tooth count both gears divide evenly. Since

24 = 2^{3} \times 3

and

35 = 5 \times 7

share no prime, a number divisible by both has to carry all four primes, and the smallest one that does is their product.

24 \times 35 = 840

That is

35

full turns of the

24

-tooth gear and

24

of the

35

-tooth one. Coprime numbers have nothing to share, so their lcm is just the two multiplied together.

That problem was the second question, the smallest count that both numbers divide evenly. When two numbers share no factors, that count is just their product. When they do share factors, it comes out smaller.

Problem

Two beacons flash every 9 seconds and every 12 seconds. List the flash times and find the first second after the start when both flash together.

Show a hint

The first beacon flashes at the multiples of $9$ , the second at the multiples of $12$ . You want the first number that shows up on both lists of multiples.
Multiples of $9$ are $9, 18, 27, 36, 45, \dots$ and multiples of $12$ are $12, 24, 36, 48, \dots$ . What is the smallest number appearing on both?

Show the full solution

The first beacon flashes at the multiples of

9

and the second at the multiples of

12

, so walk both lists.

9 : 9, 18, 27, 36, 45, \dots

12 : 12, 24, 36, 48, \dots

The first number on both is second

36

, where one beacon has flashed four times and the other three. That beats

9 \times 12 = 108

because

9

and

12

share a factor of

3

that does not need counting twice.

Problem

Use

168 = 2^{3} \times 3 \times 7

and

180 = 2^{2} \times 3^{2} \times 5

to find

lcm (168, 180)

. Take each prime to its higher power, including primes in only one fingerprint.

Show a hint

Go prime by prime again, but this time take the larger demand. For $2$ , the number $168$ wants $2^{3}$ while $180$ only wants $2^{2}$ , so the lcm must supply $2^{3}$ to satisfy $168$ . Do the same for every prime that appears in either number.
Every prime in either fingerprint must appear in the lcm, each to the highest power demanded by either number. Collect $2^{3}$ , $3^{2}$ , $5$ , and $7$ , then multiply.

Show the full solution

A number that both

168

and

180

divide has to meet the larger demand for every prime. For

2

that is

2^{3}

, from

168

. For

3

it is

3^{2}

, from

180

. The

5

and the

7

each show up in only one number but still have to appear.

lcm (168, 180) = 2^{3} \times 3^{2} \times 5 \times 7 = 8 \times 9 \times 5 \times 7 = 2520

Check that

2520 = 168 \times 15 = 180 \times 14

. The lcm takes each prime to the higher power, the mirror of the gcd taking the lower.

Problem

Three subway lines depart every 12, 18, and 30 minutes. Build

lcm (12, 18, 30)

from the fingerprints and report how many minutes until all three lines next leave together.

Show a hint

Each line departs at the multiples of its own period, so all three leave together at a common multiple of $12$ , $18$ , and $30$ . You want the smallest such number, the least common multiple of all three.
Write $12 = 2^{2} \times 3$ , $18 = 2 \times 3^{2}$ , and $30 = 2 \times 3 \times 5$ . For each prime that appears, take the highest power any of the three numbers demands, then multiply.

Show the full solution

All three lines leave together at the common multiples of

12

18

, and

30

, so take each prime to the highest power any of the three demands.

12 = 2^{2} \times 3, 18 = 2 \times 3^{2}, 30 = 2 \times 3 \times 5

That is

2^{2}

from

12

3^{2}

from

18

, and

5

from

30

lcm (12, 18, 30) = 2^{2} \times 3^{2} \times 5 = 4 \times 9 \times 5 = 180

And indeed

180 = 12 \times 15 = 18 \times 10 = 30 \times 6

. The rule stretches to any number of values, always the highest power demanded by any of them.

Here are the prime fingerprints of

168

and

180

drawn as two overlapping circles. The factors they share,

2, 2,

and

3

, sit in the green overlap, while

168

keeps an extra

2

and a

7

on its own side and

180

keeps an extra

3

and a

5

on its. The greatest common divisor is the product of just the shared overlap,

2 \times 2 \times 3 = 12

, the most both numbers carry in common. The least common multiple is the product of everything across both circles,

2^{3} \times 3^{2} \times 5 \times 7 = 2520

, since it must cover every prime either number demands. One picture, read two ways, the overlap for the gcd and the union for the lcm.

Problem

A locksmith knows two numbers have

\gcd = 8

and

lcm = 240

, and one number is 48. Use the relationship

\gcd \times lcm = a \times b

to find the other number.

Show a hint

Try multiplying a few pairs of numbers and comparing the product to the gcd times the lcm of the same pair. For example take $12$ and $18$ : their product is $216$ , their gcd is $6$ , and their lcm is $36$ . What do you notice about $6 \times 36$ ?
For any two numbers, the gcd times the lcm equals the two numbers multiplied together. So here $48 \times (other) = 8 \times 240$ . Solve for the other number.

Show the full solution

For any pair,

\gcd \times lcm = a \times b

, so the two numbers multiply to

8 \times 240 = 1920

. Dividing out the known one,

other = \frac{1920}{48} = 40

Checking,

48 = 2^{4} \times 3

and

40 = 2^{3} \times 5

2^{3} = 8

, and their lcm is

2^{4} \times 3 \times 5 = 240

. The rule holds because for each prime the gcd takes the lower power and the lcm takes the higher, so between them they use exactly the two powers the numbers had.

Problem

Dividing marbles into groups of 4, 6, or 9 always leaves exactly 1 over. What is the smallest number of marbles greater than 1 that behaves this way?

Show a hint

If you set the one leftover marble aside, the rest divide perfectly into groups of $4$ , of $6$ , and of $9$ . So the count minus $1$ is a common multiple of $4$ , $6$ , and $9$ .
The smallest number that $4$ , $6$ , and $9$ all divide is $lcm (4, 6, 9)$ . Find it, then add back the single leftover marble.
With $4 = 2^{2}$ , $6 = 2 \times 3$ , and $9 = 3^{2}$ , the lcm is $2^{2} \times 3^{2} = 36$ . The marble count is one more than the smallest common multiple above zero.

Show the full solution

Lift the one leftover marble away and what remains divides evenly into groups of

4

, of

6

, and of

9

, so the count minus

1

is a common multiple of all three.

4 = 2^{2}, 6 = 2 \times 3, 9 = 3^{2}, lcm (4, 6, 9) = 2^{2} \times 3^{2} = 36

Put the stranded marble back and the count is

36 + 1 = 37

. A number leaving the same remainder under several divisors sits that fixed step above a common multiple, so the smallest one is the lcm plus the remainder.

Problem

A bakery wants the smallest four-digit batch number divisible by 6, 8, and 9 at once. Find

lcm (6, 8, 9)

, then find its smallest four-digit multiple.

Show a hint

A number divisible by $6$ , $8$ , and $9$ is exactly a common multiple of the three, so the ones that qualify are the multiples of $lcm (6, 8, 9)$ . Find that lcm first.
With $6 = 2 \times 3$ , $8 = 2^{3}$ , and $9 = 3^{2}$ , the lcm is $2^{3} \times 3^{2} = 72$ . Now find the smallest four-digit multiple of $72$ by dividing $1000$ by $72$ and rounding up.

Show the full solution

Divisible by

6

8

, and

9

at once means being a multiple of their lcm.

6 = 2 \times 3, 8 = 2^{3}, 9 = 3^{2}, lcm (6, 8, 9) = 2^{3} \times 3^{2} = 72

Since

1000 \div 72 \approx 13.9

, thirteen

72

s land at

936

, still three digits, so the next multiple is the first to clear the line.

72 \times 14 = 1008

Hitting several divisors at once collapses the search into one list, the multiples of a single number.

Problem

Two pendulums swing every 21 and 28 seconds (

21 = 3 \times 7

28 = 2^{2} \times 7

). Find their lcm, then count how many times both start a swing together in the first 600 seconds.

Show a hint

The first pendulum starts a swing at the multiples of $21$ , the second at the multiples of $28$ . They begin together exactly at the common multiples of $21$ and $28$ , which are the multiples of $lcm (21, 28)$ . Find that lcm first.
With $21 = 3 \times 7$ and $28 = 2^{2} \times 7$ , the lcm is $2^{2} \times 3 \times 7 = 84$ . Now count how many multiples of $84$ land in the window from just after $0$ up to $600$ .
Count the whole multiples of $84$ that are at most $600$ . Since $84 \times 7 = 588$ and $84 \times 8 = 672$ , see how many steps of $84$ fit before passing $600$ .

Show the full solution

The pendulums start together at the common multiples of

21

and

28

, which are the multiples of their lcm.

21 = 3 \times 7, 28 = 2^{2} \times 7, lcm (21, 28) = 2^{2} \times 3 \times 7 = 84

Stepping by

84

gives

84, 168, 252, 336, 420, 504, 588

, and the next would be

672

, past

600

. That is

7

shared starts. Counting coincidences in a window is just counting multiples of one number, the lcm of the two periods.

Both ideas come from the same two fingerprints. The overlap gives the gcd, everything across both gives the lcm, and $\gcd \times lcm = a \times b$ ties them together. The common multiples of a pair are exactly the multiples of their lcm, which sends you back to the multiple counting of 3.1.

Practice these ideas

Practice

Find

\gcd (120, 144)

using

120 = 2^{3} \times 3 \times 5

and

144 = 2^{4} \times 3^{2}

. Take each shared prime to its lower power.

Show the solution

Keep each shared prime at its lower power. For

2

that is

2^{3}

, and for

3

it is

3^{1}

. The

5

appears only in

120

, so it contributes nothing.

\gcd (120, 144) = 2^{3} \times 3 = 24

Check that

120 = 24 \times 5

and

144 = 24 \times 6

, both whole.

Practice

Using

120 = 2^{3} \times 3 \times 5

and

144 = 2^{4} \times 3^{2}

, find

lcm (120, 144)

by taking each prime to its higher power.

Show the solution

Take each prime to its higher power, including one carried by just a single number. For

2

that is

2^{4}

, for

3

it is

3^{2}

, and the

5

from

120

has to come along.

lcm (120, 144) = 2^{4} \times 3^{2} \times 5 = 16 \times 9 \times 5 = 720

The gcd was

24

, and

24 \times 720 = 17280 = 120 \times 144

, exactly as

\gcd \times lcm = a \times b

promises.

Practice

With

49 = 7^{2}

and

60 = 2^{2} \times 3 \times 5

, do these numbers share any prime factor? Report their greatest common divisor.

Show the solution

49 = 7^{2}

is built only from

7

, and

60 = 2^{2} \times 3 \times 5

carries no

7

at all. With no prime in common, the only number dividing both is

1

. Two numbers that share no prime are called coprime, and their gcd is always

1

Practice

Two numbers have

\gcd = 9

and

lcm = 270

. One number is 45. Find the other.

Show the solution

Since

\gcd \times lcm = a \times b

, the two numbers multiply to

9 \times 270 = 2430

. Dividing out the known one,

other = \frac{2430}{45} = 54

Checking,

45 = 3^{2} \times 5

and

54 = 2 \times 3^{3}

3^{2} = 9

, and their lcm is

2 \times 3^{3} \times 5 = 270

Practice

Two ferries leave together and return every 16 and 24 minutes. How many minutes until both depart together again?

Show the solution

The ferries leave together at the common multiples of

16

and

24

, and the first one is their lcm.

16 = 2^{4}, 24 = 2^{3} \times 3, lcm (16, 24) = 2^{4} \times 3 = 48

Check that

48 = 16 \times 3 = 24 \times 2

, both whole.

Practice

Stacking badges leaves 1 over for groups of 5, 6, or 8. What is the smallest badge count greater than 1 with this property?

Show the solution

Set the leftover badge aside and the rest divides evenly into stacks of

5

6

, and

8

, so the count minus

1

is a common multiple of the three. With

6 = 2 \times 3

and

8 = 2^{3}

lcm (5, 6, 8) = 2^{3} \times 3 \times 5 = 120.

Adding the badge back gives

120 + 1 = 121

. Check that

121 = 5 \times 24 + 1 = 6 \times 20 + 1 = 8 \times 15 + 1

Practice

Two readings of two fingerprints. The gcd takes each shared prime to its lower power, and the lcm takes every prime to its higher power. They satisfy

\gcd \times lcm = a \times b

. Common multiples are multiples of the lcm.

Practice

Two rhythms of 9 and 12 beats loop together. Find the largest common multiple of 9 and 12 below 300.

Show the solution

A loop that is a whole number of both rhythms is a common multiple of

9

and

12

, so it is a multiple of their lcm.

9 = 3^{2}, 12 = 2^{2} \times 3, lcm (9, 12) = 2^{2} \times 3^{2} = 36

Since

300 \div 36 \approx 8.3

, the largest multiple staying under

300

36 \times 8 = 288

, and the next one,

324

, sails past. The common multiples of two numbers are exactly the multiples of their lcm, so a hunt like this only ever scans one list.

Practice

A poster shop prints only in runs divisible by 4, 5, and 6 at once. Find

lcm (4, 5, 6)

and its smallest three-digit multiple.

Show the solution

A run divisible by all three is a common multiple of

4

5

, and

6

, so it is a multiple of their lcm.

4 = 2^{2}, 5 = 5, 6 = 2 \times 3, lcm (4, 5, 6) = 2^{2} \times 3 \times 5 = 60

The multiples of

60

run

60, 120, 180, \dots

, and the first with three digits is

120

. Check that

120 = 4 \times 30 = 5 \times 24 = 6 \times 20

Practice

Two lights flash every 10 and 15 seconds. In 300 seconds after the start, how many times do both flash together?

Show the solution

The lights coincide at the common multiples of

10

and

15

, which are the multiples of their lcm.

10 = 2 \times 5, 15 = 3 \times 5, lcm (10, 15) = 2 \times 3 \times 5 = 30

So they flash together every

30

seconds, and

300 \div 30 = 10

of those land in the window, at

30, 60, 90

, on up to

300

Practice

A crowd leaves 1 person over for teams of 2, 3, 4, or 5. What is the smallest crowd greater than 1 with this property?

Show the solution

Set the leftover person aside and the rest splits evenly into teams of

2

3

4

, and

5

, so the crowd minus

1

is a common multiple of all four.

lcm (2, 3, 4, 5) = 2^{2} \times 3 \times 5 = 60

Adding that person back gives

60 + 1 = 61

. Check that

61

leaves exactly

1

over for each of the four team sizes.

Practice

A wall is 132 cm by 198 cm. Using

132 = 2^{2} \times 3 \times 11

and

198 = 2 \times 3^{2} \times 11

, find the side length of the largest square tile that fits exactly.

Show the solution

A tile of side

s

fits exactly only when

s

divides both

132

and

198

, so the largest tile is the gcd. Each shared prime goes to its lower power, giving one

2

, one

3

, and one

11

\gcd (132, 198) = 2 \times 3 \times 11 = 66

The tile is

66

cm on a side, fitting

2

across and

3

up. The largest square that tiles a whole-number rectangle is always the gcd of the two sides.

Practice

A number leaves remainder 3 when divided by 4, remainder 5 when divided by 6, and remainder 7 when divided by 8. Notice each remainder is one less than its divisor. What is the smallest such number?

Show the solution

Each remainder is one less than its divisor, so adding

1

would make the number divide evenly by

4

6

, and

8

at once. That puts it one below a common multiple.

4 = 2^{2}, 6 = 2 \times 3, 8 = 2^{3}, lcm (4, 6, 8) = 2^{3} \times 3 = 24

So the number is

24 - 1 = 23

. Check that

23 = 4 \times 5 + 3 = 6 \times 3 + 5 = 8 \times 2 + 7

Practice

GCD and LCM are the engines of fractions. Reducing divides by the gcd, and adding different-denominator fractions uses the lcm as common denominator. Master these now and fraction work becomes routine.