GCF and LCM

Learning goals

Find a GCF and an LCM by listing factors or multiples
Compute a GCF and an LCM from prime factorizations, taking the lowest or highest prime power
Explain why lowest serves the GCF and highest serves the LCM
Apply the product rule for two numbers, and say why three break it
Read greatest number of equal groups as GCF and coinciding cycles as LCM

Common factors and the GCF

A common factor of two positive whole numbers is a number that is a factor of both. Take $12$ and $18$ . Their factors are

12: \; 1, 2, 3, 4, 6, 12 \qquad\qquad 18: \; 1, 2, 3, 6, 9, 18.

The numbers that appear in both lists are $1, 2, 3,$ and $6$ : these are the common factors of $12$ and $18$ . Every pair of positive whole numbers shares at least the factor $1$ , so the list of common factors is never empty. The largest entry in it is the one we care about most.

The greatest common factor (GCF) of two positive whole numbers is the largest number that is a factor of both. For $12$ and $18$ the common factors are $1, 2, 3, 6$ , and the greatest of these is $6$ , so

\operatorname{GCF}(12, 18) = 6.

This is the largest number you could divide both $12$ and $18$ by and still land on whole numbers: $12 \div 6 = 2$ and $18 \div 6 = 3$ . That is exactly what makes the GCF useful. When you reach fractions in the next chapter, you will divide the top and bottom of a fraction by their GCF. That is what reduces the fraction as far as it will go in a single step.

Common multiples and the LCM

Now flip the question around. A common multiple of two positive whole numbers is a number that is a multiple of both. List a few multiples of $4$ and of $6$ :

4: \; 4, 8, 12, 16, 20, 24, 28, \ldots \qquad 6: \; 6, 12, 18, 24, 30, \ldots

The numbers in both lists, $12, 24, 36, \ldots$ , are the common multiples of $4$ and $6$ . Unlike common factors, there are infinitely many of them, because you can always go further out and find more. But there is a smallest one, and that is the one worth naming.

The least common multiple (LCM) of two positive whole numbers is the smallest positive common multiple of the two. The common multiples of $4$ and $6$ start $12, 24, 36, \ldots$ , so

\operatorname{LCM}(4, 6) = 12.

This is the soonest the two counting patterns line up: count by fours and by sixes, and $12$ is the first place they meet. That is why the LCM is the natural common denominator when you add fractions later: it is the smallest number into which both denominators fit.

The GCF is a factor of the numbers, so it is never bigger than either one. The LCM is a multiple of the numbers, so it is never smaller than either one. For $4$ and $6$ , the GCF is $2$ , at most as big as the smaller number. The LCM is $12$ , at least as big as the larger. If a value you have called the GCF comes out larger than the numbers themselves, you have the two swapped. The same is true if an LCM comes out smaller than those numbers.

The listing method

The lists above are the listing method (writing the factors or the multiples out and reading the answer off the lists), and they always work:

For the GCF, write out the factors of each number, find the ones common to both, and take the largest.
For the LCM, write out multiples of each number until a value shows up in both lists, and take the first such value.

Listing is reliable and easy to picture, which makes it the right way to meet these ideas. Its drawback shows up with bigger numbers. The factor lists get long, and you might count out a great many multiples before the lists finally meet. For $8$ and $36$ you would list multiples up to $72$ before they coincide. So we want a method that does not depend on the numbers being small, and prime factorization provides exactly that.

Before leaving the listing method, it is worth running it once from start to finish. Write out the factors of each number, then read off the ones that appear in both lists:

8: \; 1, 2, 4, 8 \qquad\qquad 12: \; 1, 2, 3, 4, 6, 12.

The numbers in both lists are $1$ , $2$ and $4$ , so those are the common factors of $8$ and $12$ . The largest of them is $4$ , so $\operatorname{GCF}(8, 12) = 4$ . Notice what disqualifies a number like $3$ : it divides $12$ but not $8$ , so it appears in one list and not the other. A factor has to survive both lists to count as a common one.

Check your understanding

Using the listing method, what is $\operatorname{GCF}(16, 24)$ ?

8

4

48

2

Listing works the same way for the LCM. Write out multiples of each number and watch for the first value that shows up in both lists.

Check your understanding

Using the listing method, what is $\operatorname{LCM}(6, 8)$ ?

24

48

2

14

The prime-factorization method

Every whole number greater than $1$ has a unique prime factorization. That factorization records exactly how many copies of each prime the number is built from. That bookkeeping is precisely what the GCF and LCM need. Start each number in prime-power form. Take $12$ and $18$ :

12 = 2^2 \times 3, \qquad 18 = 2 \times 3^2.

Think of each number as a bag of prime factors. The bag for $12$ holds two $2$ s and one $3$ ; the bag for $18$ holds one $2$ and two $3$ s. With the numbers written this way, both answers come from one simple rule each.

GCF: for each shared prime, take the lowest power it has in the two numbers. The prime $2$ appears as $2^2$ in $12$ but only $2^1$ in $18$ , so take $2^1$ . The prime $3$ appears as $3^1$ in $12$ and $3^2$ in $18$ , so take $3^1$ . Multiply: $\operatorname{GCF}(12, 18) = 2 \times 3 = 6$ . A prime that sits in only one of the numbers is not shared, so it contributes nothing to the GCF.
LCM: for each prime, take the highest power that appears in either number. For $2$ take $2^2$ ; for $3$ take $3^2$ . Multiply: $\operatorname{LCM}(12, 18) = 2^2 \times 3^2 = 4 \times 9 = 36$ .

Both agree with the lists ( $\operatorname{GCF} = 6$ from before, and $36$ is indeed the first common multiple of $12$ and $18$ ). The figure below shows why “lowest” and “highest” are the right choices. The figure sets the shared core that sits inside both numbers against the combined pile that contains each number whole.

The prime factors of 12 and 18. The middle region is the part both numbers share (one 2 and one 3): multiply it for the GCF. Everything in either circle, taken together, is the LCM (two 2s and two 3s).

Why lowest power for the GCF

The rule is not arbitrary. A factor of both numbers can only use prime copies that both numbers actually own, and that limit is what forces “lowest power.”

Look at what each bag can spare. The bag for $12$ holds two $2$ s, but the bag for $18$ holds only one, so a common factor can use at most one $2$ : nothing can divide $18$ by asking for a $2$ it does not have. The $3$ s work the other way, since here it is $12$ that holds only one $3$ . Take each shared prime at the smaller of its two counts and you get $2 \times 3 = 6$ , the GCF.

So the GCF is built only from the primes the two numbers truly have in common. Each of those primes is capped at the count in whichever number has fewer copies of it. Take a prime to a higher power than that, and the result would no longer divide the number with fewer copies.

Why highest power for the LCM

The LCM argument is the mirror image. A multiple of both numbers must contain enough copies of each prime to cover each number on its own. That is what forces “highest power.”

Check $12$ and $18$ against that demand. A common multiple has to hold two $2$ s, because $12$ does and every multiple of $12$ carries its factors along. It has to hold two $3$ s for the same reason, from the $18$ side. Two of each satisfies both demands at once, and $2^2 \times 3^2 = 36$ is what the demands come to.

Side by side, the two rules are easy to remember once you see the reason. The GCF can only keep what both numbers can spare, so it takes the lower power. The LCM must satisfy whichever number needs more of a given prime, so it takes the higher power.

Check your understanding

Why must $\operatorname{LCM}(12, 18)$ contain $2^2$ , not just $2^1$ ?

A Because

12

has two

2

s, and any multiple of

12

must carry both B Because

18

has two

2

s, and any multiple of

18

must carry both C Because

2^2

is an even number D Because the LCM is always a multiple of

4

Check your understanding

Why can $\operatorname{GCF}(12, 18)$ not contain $2^2$ ?

A Because

18

has only one

2

to offer B Because

12

has only one

2

to offer C Because

2^2

is an even number D Because the GCF is always odd

Worked example 1 Find the GCF and LCM of $24$ and $36$ from their prime factorizations

Write each number in prime-power form first:

24 = 2^3 \times 3, \qquad 36 = 2^2 \times 3^2.

Go prime by prime. For the prime $2$ , the two powers are $2^3$ and $2^2$ . For the prime $3$ , they are $3^1$ and $3^2$ .

For the GCF, take the lower power of each:

\operatorname{GCF}(24, 36) = 2^2 \times 3^1 = 4 \times 3 = 12.

For the LCM, take the higher power of each:

\operatorname{LCM}(24, 36) = 2^3 \times 3^2 = 8 \times 9 = 72.

As a check, $12$ divides both $24$ and $36$ (giving $2$ and $3$ ), and both $24$ and $36$ divide $72$ (giving $3$ and $2$ ). So the answers behave exactly as a GCF and an LCM should.

Check your understanding

Given $20 = 2^2 \times 5$ and $30 = 2 \times 3 \times 5$ , what is $\operatorname{LCM}(20, 30)$ ?

60

10

600

120

GCF and LCM together: the product rule

Look back at $12$ and $18$ . The GCF was $6$ and the LCM was $36$ , and

\operatorname{GCF}(12, 18) \times \operatorname{LCM}(12, 18) = 6 \times 36 = 216 = 12 \times 18.

That is not a coincidence of this one pair. For any two positive whole numbers $a$ and $b$ ,

\operatorname{GCF}(a, b) \times \operatorname{LCM}(a, b) = a \times b.

The reason lives in the prime powers again. Look at the prime $2$ in $12$ and $18$ . There are two of them in $12$ and one in $18$ . The GCF takes the one and the LCM takes the two, so between them the two answers take all three. Multiplying $12$ by $18$ takes all three as well.

That happens at every prime, because a prime is offered just two counts, one from each number. The GCF takes the smaller and the LCM takes the larger, so between them they take both. The two counts can also be equal, as the $5$ s are in $40$ and $60$ . Then each answer takes one of the pair, and the tally comes out the same.

The same bookkeeping is easier to see with blocks than with exponents. Split each number into the part it shares with the other and the part it does not. That gives $12 = 2 \times 6$ and $18 = 6 \times 3$ , with the shared block $6$ in the middle. The GCF is that shared block by itself, and the LCM is all three blocks together. So the GCF times the LCM calls on the shared block twice and each outside block once, which is exactly what $12 \times 18$ does.

GCF times LCM equals the numbers multiplied, seen in blocks. The shaded overlap is the GCF and all three blocks together are the LCM, so GCF times LCM uses 2 once, the shared 6 twice, and 3 once. Writing 12 as 2 times 6 and 18 as 6 times 3 uses exactly those same four factors, so both products come to 216.

This gives a handy shortcut. Once you have the GCF, you can get the LCM without listing anything, by dividing the product of the numbers by the GCF:

\operatorname{LCM}(a, b) = (a \times b) \div \operatorname{GCF}(a, b).

For $12$ and $18$ that is $(12 \times 18) \div 6 = 216 \div 6 = 36$ , matching what we found the long way.

Worked example 2 Use the product rule to find $\operatorname{LCM}(8, 36)$

First find the GCF. In prime-power form,

8 = 2^3, \qquad 36 = 2^2 \times 3^2.

The only shared prime is $2$ , and the lower power is $2^2$ , so $\operatorname{GCF}(8, 36) = 4$ . The prime $3$ appears only in $36$ , so it is not part of the common factor.

Now apply the product rule instead of listing multiples:

\operatorname{LCM}(8, 36) = (8 \times 36) \div \operatorname{GCF}(8, 36) = 288 \div 4 = 72.

The same answer falls out of the highest-power rule: $\operatorname{LCM}(8, 36) = 2^3 \times 3^2 = 8 \times 9 = 72$ . Either route works, and the product rule is quickest once the GCF is in hand.

Check your understanding

Given that $\operatorname{GCF}(15, 20) = 5$ , what is $\operatorname{LCM}(15, 20)$ using the product rule?

60

300

5

100

The power rules extend, but the product rule does not

Take $4$ , $6$ and $10$ . Only the prime $2$ sits in all three, and the fewest copies any of them holds is one, so $\operatorname{GCF}(4, 6, 10) = 2$ . For the LCM, take the most copies of each prime that appears anywhere. That is two $2$ s from $4$ , one $3$ from $6$ and one $5$ from $10$ , giving $2^2 \times 3 \times 5 = 60$ . Both answers check out, since $2$ divides all three numbers and all three divide $60$ .

Nothing there was special to three numbers. A common factor has to divide all of them, so at each prime it is capped by whichever number holds the fewest copies. A common multiple has to cover all of them, so at each prime it needs enough for whichever number holds the most. Just more numbers to compare at each prime.

Worked example 3 Find the GCF and LCM of $18$ , $42$ and $63$

Write all three in prime-power form:

18 = 2 \times 3^2, \qquad 42 = 2 \times 3 \times 7, \qquad 63 = 3^2 \times 7.

Now go prime by prime across all three at once. The prime $2$ sits in $18$ and $42$ but not in $63$ , since $63$ is odd. The prime $3$ sits in all three, as $3^2$ , $3^1$ and $3^2$ . The prime $7$ sits in $42$ and $63$ but not in $18$ .

For the GCF, keep only the primes every number has, each at its lowest power. That leaves the prime $3$ on its own, and the lowest of its three powers is $3^1$ :

\operatorname{GCF}(18, 42, 63) = 3.

The primes $2$ and $7$ drop out for the same reason an unshared prime drops out with two numbers. The number $63$ has no copy of $2$ to give, and $18$ has no copy of $7$ .

For the LCM, take the highest power of every prime that appears anywhere, which is $2^1$ , $3^2$ and $7^1$ :

\operatorname{LCM}(18, 42, 63) = 2 \times 3^2 \times 7 = 2 \times 9 \times 7 = 126.

Check both ends. The GCF divides all three: $18 \div 3 = 6$ , $42 \div 3 = 14$ , and $63 \div 3 = 21$ . And all three divide the LCM: $126 \div 18 = 7$ , $126 \div 42 = 3$ , and $126 \div 63 = 2$ . Every division comes out whole, which is exactly what a GCF and an LCM are for.

The product rule does not extend, and $2$ , $3$ and $4$ show why. Their GCF is $1$ and their LCM is $12$ , so the two answers multiply to $12$ , while $2 \times 3 \times 4 = 24$ .

Watch the prime $2$ in those three numbers. The number $2$ holds one copy, $3$ holds none, and $4$ holds two. The GCF takes the fewest, none, and the LCM takes the most, two. The middle count, the single copy inside the number $2$ , is taken by neither, and that missing copy is the whole gap: $24 = 12 \times 2$ . With two numbers there is no middle count to miss.

Check your understanding

For $2$ , $3$ and $4$ , why does $\operatorname{GCF}(2,3,4) \times \operatorname{LCM}(2,3,4)$ come out smaller than $2 \times 3 \times 4$ ?

A The prime

2

has three counts among the numbers,

0

1

, and

2

, and the GCF and LCM together take only the lowest and the highest, leaving the middle count of

1

(from the number

2

) uncounted B The GCF and LCM were computed incorrectly C The product rule works fine here, and

12 \ne 24

is just a coincidence of small numbers D Three numbers always make the GCF equal to

1

, which breaks the rule

The lowest-power and highest-power rules work for any number of numbers, but this product rule works only for two. With three or more, read the GCF and the LCM straight off the prime powers instead: this shortcut, $(a \times b) \div \operatorname{GCF}(a, b)$ , does not carry over to three numbers in the same simple way.

Check your understanding

Given $26 = 2 \times 13$ , $39 = 3 \times 13$ and $52 = 2^2 \times 13$ , what is $\operatorname{GCF}(26, 39, 52)$ ?

26

156

13

1

GCF in a word problem: the greatest number of equal groups

Word problems hide the GCF and LCM behind everyday situations. The signal for a GCF problem is that you are splitting things into the greatest possible number of equal groups. The same signal appears when you are finding the biggest size that fits evenly into several totals at once.

Worked example 4 Packing into the greatest number of equal boxes

A baker has $48$ muffins and $60$ cookies. She wants to pack them into identical gift boxes so that every box has the same number of muffins and the same number of cookies. No muffins or cookies may be left over, and she wants to make as many boxes as possible. How many boxes can she make?

Each box gets an equal share of the muffins and an equal share of the cookies. So the number of boxes must divide both $48$ and $60$ . The largest such number is the greatest common factor. In prime-power form,

48 = 2^4 \times 3, \qquad 60 = 2^2 \times 3 \times 5.

Take the lower power of each shared prime: $2^2$ for the prime $2$ , and $3^1$ for the prime $3$ . The prime $5$ is only in $60$ , so it drops out.

\operatorname{GCF}(48, 60) = 2^2 \times 3 = 12.

So she can make $12$ boxes. Each box holds $48 \div 12 = 4$ muffins and $60 \div 12 = 5$ cookies. Asking for the greatest number of equal groups is the tell that you want the GCF.

Check your understanding

A gym coach has $18$ jump ropes and $24$ cones and wants to set up the greatest possible number of identical stations, using every rope and every cone with none left over. How many stations can she set up?

6

72

2

18

LCM in a word problem: when patterns coincide

The signal for an LCM problem is that two repeating cycles start together and you want to know when they will next line up. The same signal appears when you want the smallest amount that several given sizes can all build up to exactly.

Worked example 5 When do the two bells ring together again?

At a train station, one bell rings every $8$ minutes and another rings every $12$ minutes. They ring together at $9{:}00$ . How many minutes until they next ring at the same time?

The first bell rings at minutes $8, 16, 24, \ldots$ (the multiples of $8$ ), and the second at minutes $12, 24, 36, \ldots$ (the multiples of $12$ ). They coincide at any common multiple, and they next coincide at the smallest one, the least common multiple. In prime-power form,

8 = 2^3, \qquad 12 = 2^2 \times 3.

Take the highest power of each prime: $2^3$ for the prime $2$ , and $3^1$ for the prime $3$ .

\operatorname{LCM}(8, 12) = 2^3 \times 3 = 8 \times 3 = 24.

So the bells next ring together after $24$ minutes, at $9{:}24$ . Checking: $24 \div 8 = 3$ rings of the first bell and $24 \div 12 = 2$ rings of the second, both whole, so $24$ really is a moment they share. Asking when repeating events next coincide is the tell that you want the LCM.

Check your understanding

Two runners start together on a track. One finishes a lap every $6$ minutes, the other every $9$ minutes. After how many minutes do they next cross the start line at the same time?

18

3

54

15

A word problem never announces which of the two you need; you have to read for the signal.

Check your understanding

A youth group has $28$ volunteers and $42$ supply kits. It wants to form identical teams, giving every team the same number of volunteers and the same number of kits with none left over, using as many teams as it possibly can. Which computation finds the number of teams?

\operatorname{GCF}(28, 42)

\operatorname{LCM}(28, 42)

28 \times 42

28 + 42

Common mistakes

Swapping GCF and LCM. The GCF is a factor, so it is at most as big as either number. The LCM is a multiple, so it is at least as big as either number. If your GCF is the larger answer, you have the two reversed.
Mixing up the powers. GCF takes the lowest power of each shared prime; LCM takes the highest. A quick check: the GCF should divide both numbers, and both numbers should divide the LCM.
Dropping a prime from the LCM. A prime that appears in only one number still belongs in the LCM, at its full power there, because that number alone demands it. For $8 = 2^3$ and $9 = 3^2$ , the LCM is $2^3 \times 3^2 = 72$ , not $1$ ; do not discard $2^3$ or $3^2$ just because they are not shared.
Using the plain product as the LCM. Multiplying the two numbers gives a common multiple, but not the least one unless the numbers share no prime. For $4$ and $6$ , the product is $24$ but the LCM is $12$ ; divide the product by the GCF to correct it.
Carrying the product rule to three numbers. The rule $\operatorname{GCF}(a, b) \times \operatorname{LCM}(a, b) = a \times b$ is about a pair, and the $2, 3, 4$ example above shows it failing for three. With three or more numbers, read both answers straight off the prime powers instead.
Stopping the multiple lists too soon. With the listing method, keep extending both lists until a value truly appears in both. The first shared value is the LCM, not merely the first largish number you recognize.

Key takeaways

The GCF of two or more positive whole numbers is the largest number that divides all of them. The LCM of those numbers is the smallest positive number that is a common multiple of all of them.
Listing method: for the GCF, list the factors of each number and take the largest shared one. For the LCM, list the multiples of each number until the lists first coincide.
Prime-factorization method: write each number in prime-power form, then for the GCF take the lowest power of each prime shared by all of them. For the LCM, take the highest power of every prime that appears.
Take the lowest power of each shared prime for the GCF, because a common factor can use only the copies both numbers have. Take the highest power of every prime for the LCM, because a common multiple needs enough copies for each number.
For two numbers the answers are linked by $\operatorname{GCF}(a, b) \times \operatorname{LCM}(a, b) = a \times b$ , so $\operatorname{LCM}(a, b) = (a \times b) \div \operatorname{GCF}(a, b)$ . The reason is that a pair of counts holds only a lower one and a higher one, with nothing in between.
Three or more numbers: the lowest-power and highest-power rules work unchanged, but the product rule does not travel with them, as the $2, 3, 4$ example showed. Read the GCF and the LCM straight off the prime powers instead.
In words: the greatest number of equal groups signals a GCF; when repeating cycles next coincide signals an LCM.

Practice

Multiple Choice Questions (MCQ)

Progressively harder sets of questions. Each opens on its own page.

Level 1 Foundational 12 questions Start → Level 2 Intermediate 12 questions Start → Level 3 Challenge 12 questions Start →

Core practice

Practice problems at the level of the course, to be worked out on paper. Hints one at a time, then the answer or the full worked solution, with your progress kept in this browser.

More practice (optional)

Extra sets, as hard as the Challenge set. Each one opens on its own page.

More resources (optional)

Other explanations of this lesson, if you want a second take.

Greatest common factor (Khan Academy)
Least common multiple (Khan Academy)
Greatest common factor (Math is Fun)
Prealgebra: prime factorization and the LCM (free textbook) (OpenStax)

Go deeper (optional)

You can skip this and keep going. Read it if you want to know more.

Why the GCF takes the lowest power of each shared prime

The lesson shows the cap biting on $12$ and $18$ : a common factor may carry one $2$ , because $18$ has only one to give. This runs the same argument on a fresh pair, then on any two numbers at once.

Why the GCF takes the lowest power of each shared prime#

Try it on $40 = 2^3 \times 5$ and $60 = 2^2 \times 3 \times 5$ . Suppose $d$ divides both of them, and ask how many $2$ s $d$ is allowed. Every $2$ inside $d$ has to sit inside $40$ as well, which caps the count at three. Every one has to sit inside $60$ too, which caps it at two. Two is the lower cap, so $d$ holds at most two $2$ s. Asking the same of $5$ gives one from each side, and asking it of $3$ gives none, since $40$ has no $3$ to offer. Taking every cap at once builds $2^2 \times 5 = 20$ , which is $\operatorname{GCF}(40, 60)$ .

Now the general form of that. Suppose a number $d$ divides both $a$ and $b$ . Look at any prime $p$ in the factorization of $d$ , and say that $d$ contains $p$ exactly $k$ times. Since $d$ divides $a$ , those $k$ copies must already sit inside $a$ , so $a$ holds at least $k$ of them. The same reasoning gives $b$ at least $k$ . So $k$ is at most the smaller of those two counts.

For every prime, then, a common factor can carry no more copies than the number that has fewer of them. The greatest common factor is the one that carries as many as it possibly can. For each shared prime that is the lower of the two powers. A prime sitting in only one of the numbers drops out entirely, because the other has none of it to offer.

Multiply the lowest power of each prime together. The result divides both $a$ and $b$ , because it never asks for more copies than either number has. It is also as large as any common factor can be, since it takes the most copies allowed. That is the GCF.

Why the LCM takes the highest power of each prime that appears in either number

The lesson shows the demand landing on $12$ and $18$ : a common multiple has to hold two $2$ s, because every multiple of $12$ carries them along. This runs the same argument on a fresh pair, then on any two numbers at once.

Why the LCM takes the highest power of each prime that appears in either number#

Take the same $40 = 2^3 \times 5$ and $60 = 2^2 \times 3 \times 5$ , and let $m$ be a multiple of both. Because $40$ divides $m$ , that $m$ carries at least three $2$ s. Because $60$ divides $m$ , it carries at least two, a demand the three has already met. So three is what the pair asks for, the larger of the two counts. One $3$ is demanded by $60$ and one $5$ by either number, so the smallest $m$ meeting every demand is $2^3 \times 3 \times 5 = 120$ , which is $\operatorname{LCM}(40, 60)$ .

Now the general form. Suppose a number $m$ is a multiple of both $a$ and $b$ , so both of them divide $m$ . Look at any prime $p$ . Because $a$ divides $m$ , that $m$ holds at least as many copies of $p$ as $a$ does. Because $b$ divides $m$ , it holds at least as many as $b$ does. To meet both demands at once, $m$ needs at least the larger of the two counts.

For every prime, then, a common multiple must carry no fewer copies than the number that has more of them. The least common multiple carries exactly that many and not one extra, which for each prime is the higher of the two powers. A prime sitting in only one number still appears, at the full power it has there, because that number alone demands it.

Multiply the highest power of each prime together. The result is a number that both $a$ and $b$ divide, because each prime is present in enough quantity for either one. It is also as small as any common multiple can be, because no prime is taken to more than the largest power required. That is the LCM.

Why the counts always add up, for any two positive numbers

The lesson shows the product rule working on $12$ and $18$ , and says why. At each prime the GCF takes the smaller count and the LCM takes the larger, so together they take both. This does that count for every prime at once.

Why the GCF and the LCM of two numbers multiply back to the product#

Take $40 = 2^3 \times 5$ and $60 = 2^2 \times 3 \times 5$ first. Their GCF is $2^2 \times 5$ and their LCM is $2^3 \times 3 \times 5$ . Count the $2$ s. The GCF took two and the LCM took three, so five between them, and $40 \times 60$ holds five as well. The $3$ s give $0 + 1$ against $0 + 1$ , and the $5$ s give $1 + 1$ against $1 + 1$ . Every prime matches, and $20 \times 120 = 2400 = 40 \times 60$ .

Now with letters. If either number is $1$ there is nothing to prove: the GCF is $1$ , the LCM is the other number, and both sides read the same. So take $a$ and $b$ above $1$ .

Multiplying two numbers stands their prime lists side by side, and a number has only one prime list, so that combined list is the product’s. Counting a prime inside a product means adding the two counts.

Fix a prime $p$ . Let $x$ be how many copies of it sit in $a$ , and $y$ how many sit in $b$ . Either count may be $0$ . The two rules already proved say the GCF takes the lower of $x$ and $y$ , and the LCM takes the higher. So $\operatorname{GCF}(a, b) \times \operatorname{LCM}(a, b)$ holds

(\text{lower of } x \text{ and } y) + (\text{higher of } x \text{ and } y)

copies of $p$ . Here is the whole rule in one step. Take the smaller of $x$ and $y$ as the “lower” value, and either one if they are equal. Then “lower” and “higher” are $x$ and $y$ again, just named in size order. Sorting two numbers does not change their total, so

(\text{lower of } x \text{ and } y) + (\text{higher of } x \text{ and } y) = x + y,

and $x + y$ is how many copies of $p$ sit inside $a \times b$ .

So at every prime the two sides hold the same number of copies. A number has only one prime list, so two numbers built from identical lists cannot be different. Therefore

\operatorname{GCF}(a, b) \times \operatorname{LCM}(a, b) = a \times b.

Notice the step that needed a pair. Two counts are a smaller one and a larger one, and the two answers take one each. Three counts have a middle one that neither answer takes, which is why this rule is about two numbers only.

A bit of history (optional)

You found the GCF by breaking both numbers into primes. That works while the numbers stay small. Hand someone a number built by secretly multiplying two large primes, each hundreds of digits long, and the method stalls: factoring a number like that back into its two primes can take far too long to be practical, even for a computer.

An older way never factors anything. A Greek writer named Euclid set it down around 300 BCE, in the geometry book called the Elements, and the recipe carries his name today. Take the two numbers and subtract the smaller from the larger, over and over, until the two are equal. That final value is the GCF.

Run it on $48$ and $60$ . Subtracting drives the pair down to $12$ and $12$ , so the GCF is $12$ . One line explains why. A number that divides both of them also divides their difference. So the difference is safe to use, and it is smaller.

Subtracting one at a time is slow on huge numbers. Modern versions divide instead, replacing the larger number by the remainder, which lands in one step where subtracting took thousands. That change, plus never factoring at all, keeps it quick on numbers hundreds of digits long. A close relative of this algorithm is part of how today’s internet codes, the ones built from two secret large primes, get set up in the first place. Two thousand years on, it still returns the $12$ your prime powers did.