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: \quad 1,\ 2,\ 4,\ 7,\ 8,\ 14,\ 28,\ 56$$ $$70: \quad 1,\ 2,\ 5,\ 10,\ 7,\ 14,\ 35,\ 70$$ The numbers on both lists are $1, 2, 7,$ and $14$, and the largest is $\boxed{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 = \boxed{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, \qquad 126 = 2 \times 3^2 \times 7$$ Both carry one $2$ and both carry $3^2$, while $5$ belongs to $90$ alone and $7$ to $126$ alone. $$\gcd(90,126) = 2 \times 3^2 = \boxed{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 = \boxed{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, \ldots$ and multiples of $12$ are $12, 24, 36, 48, \ldots$. 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: \quad 9,\ 18,\ 27,\ 36,\ 45,\ \ldots$$ $$12: \quad 12,\ 24,\ 36,\ 48,\ \ldots$$ The first number on both is second $\boxed{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 $\operatorname{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. $$\operatorname{lcm}(168,180) = 2^3 \times 3^2 \times 5 \times 7 = 8 \times 9 \times 5 \times 7 = \boxed{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 $\operatorname{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, \qquad 18 = 2 \times 3^2, \qquad 30 = 2 \times 3 \times 5$$ That is $2^2$ from $12$, $3^2$ from $18$, and $5$ from $30$. $$\operatorname{lcm}(12,18,30) = 2^2 \times 3^2 \times 5 = 4 \times 9 \times 5 = \boxed{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 $\operatorname{lcm} = 240$, and one number is 48. Use the relationship $\gcd \times \operatorname{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 (\text{other}) = 8 \times 240$. Solve for the other number.

Show the full solution

For any pair, $\gcd \times \operatorname{lcm} = a \times b$, so the two numbers multiply to $8 \times 240 = 1920$. Dividing out the known one, $$\text{other} = \frac{1920}{48} = \boxed{40}$$ Checking, $48 = 2^4 \times 3$ and $40 = 2^3 \times 5$ share $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 $\operatorname{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, \qquad 6 = 2 \times 3, \qquad 9 = 3^2, \qquad \operatorname{lcm}(4,6,9) = 2^2 \times 3^2 = 36$$ Put the stranded marble back and the count is $36 + 1 = \boxed{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 $\operatorname{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 $\operatorname{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, \qquad 8 = 2^3, \qquad 9 = 3^2, \qquad \operatorname{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 = \boxed{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\times7$, $28=2^2\times7$). 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 $\operatorname{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, \qquad 28 = 2^2 \times 7, \qquad \operatorname{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 $\boxed{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\operatorname{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 = \boxed{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 $\operatorname{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. $$\operatorname{lcm}(120,144) = 2^4 \times 3^2 \times 5 = 16 \times 9 \times 5 = \boxed{720}$$ The gcd was $24$, and $24 \times 720 = 17280 = 120 \times 144$, exactly as $\gcd \times \operatorname{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 $\boxed{1}$. Two numbers that share no prime are called coprime, and their gcd is always $1$.

Practice

Two numbers have $\gcd = 9$ and $\operatorname{lcm} = 270$. One number is 45. Find the other.

Show the solution

Since $\gcd \times \operatorname{lcm} = a \times b$, the two numbers multiply to $9 \times 270 = 2430$. Dividing out the known one, $$\text{other} = \frac{2430}{45} = \boxed{54}$$ Checking, $45 = 3^2 \times 5$ and $54 = 2 \times 3^3$ share $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, \qquad 24 = 2^3 \times 3, \qquad \operatorname{lcm}(16,24) = 2^4 \times 3 = \boxed{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$, $$\operatorname{lcm}(5,6,8) = 2^3 \times 3 \times 5 = 120.$$ Adding the badge back gives $120 + 1 = \boxed{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\operatorname{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, \qquad 12 = 2^2 \times 3, \qquad \operatorname{lcm}(9,12) = 2^2 \times 3^2 = 36$$ Since $300 \div 36 \approx 8.3$, the largest multiple staying under $300$ is $36 \times 8 = \boxed{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 $\operatorname{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, \qquad 5 = 5, \qquad 6 = 2 \times 3, \qquad \operatorname{lcm}(4,5,6) = 2^2 \times 3 \times 5 = 60$$ The multiples of $60$ run $60, 120, 180, \ldots$, and the first with three digits is $\boxed{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, \qquad 15 = 3 \times 5, \qquad \operatorname{lcm}(10,15) = 2 \times 3 \times 5 = 30$$ So they flash together every $30$ seconds, and $300 \div 30 = \boxed{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. $$\operatorname{lcm}(2,3,4,5) = 2^2 \times 3 \times 5 = 60$$ Adding that person back gives $60 + 1 = \boxed{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 = \boxed{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, \qquad 6 = 2 \times 3, \qquad 8 = 2^3, \qquad \operatorname{lcm}(4,6,8) = 2^3 \times 3 = 24$$ So the number is $24 - 1 = \boxed{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.