GCF and LCM: Free Response

Work up from $1$ and pair each factor with its partner, so that nothing is missed.

$27: \; 1 \times 27, \; 3 \times 9 \;\Rightarrow\; 1, 3, 9, 27$

$45: \; 1 \times 45, \; 3 \times 15, \; 5 \times 9 \;\Rightarrow\; 1, 3, 5, 9, 15, 45$

Now compare the two lists. The numbers standing in both are $1$, $3$ and $9$, and those are the common factors of $27$ and $45$. Every pair of whole numbers has $1$ in common, so such a list is never empty, and here the largest entry is $9$:

$\operatorname{GCF}(27, 45) = 9.$

Check it against the definition: $27 \div 9 = 3$ and $45 \div 9 = 5$, both whole, so $9$ divides both numbers. Nothing larger can, because the two lists hold nothing larger in common.

Break each number down. $27 = 3 \times 3 \times 3$, and $45 = 3 \times 3 \times 5$, so in prime-power form

$27 = 3^3, \qquad 45 = 3^2 \times 5.$

Go prime by prime. The prime $3$ appears three times in $27$ and twice in $45$, so a number dividing both can carry it at most twice: take $3^2$. The prime $5$ appears in $45$ only, and $27$ has none of it to offer, so it cannot appear in a common factor at all.

$\operatorname{GCF}(27, 45) = 3^2 = 9.$

This is the same $9$ the lists produced, which is what had to happen. The lists and the prime powers are two ways of asking one question, not two questions.

A multiple of both numbers has to carry enough copies of every prime to cover each number on its own. The prime $3$ appears three times in $27$ and twice in $45$, so three copies are needed; the prime $5$ appears in $45$, so it has to be there as well.

$\operatorname{LCM}(27, 45) = 3^3 \times 5 = 27 \times 5 = 135.$

Check it both ways round: $135 \div 27 = 5$ and $135 \div 45 = 3$, so $135$ really is a multiple of each.

By listing, the multiples of $27$ run $27, 54, 81, 108, 135$, so $135$ is the fifth of them, and the multiples of $45$ run $45, 90, 135$, so it is the third of those. Five rows is no hardship. The point is that listing gives no warning of how long it will take: for $27$ and $50$, which share no prime at all, the first coincidence is $1{,}350$, and the same count would run to $50$ rows.

The prime factorizations show it at once:

$27 = 3^3, \qquad 45 = 3^2 \times 5.$

The prime $5$ belongs to $45$ alone.

A common factor has to divide $27$. Every prime inside a factor of $27$ already sits inside $27$, and $27$ is built from copies of $3$ and nothing else, so no factor of $27$ can contain a $5$. That bars $5$ from the greatest common factor entirely: it is not that the rule chooses to drop it, it is that $27$ has none of it to give.

A common multiple has to be a multiple of $45$, and $45$ cannot divide a number with no $5$ in it. So every common multiple carries a $5$, the least one included. Here the demand comes from one number alone, and one number is enough.

Compare the two answers and the difference is visible:

$\operatorname{GCF}(27, 45) = 9 = 3^2, \qquad \operatorname{LCM}(27, 45) = 135 = 3^3 \times 5.$

That is the general pattern for an unshared prime: barred from the greatest common factor, because the other number cannot supply it, and compulsory in the least common multiple, at the full power it has, because the number that owns it demands it.

Set the two tallies side by side, prime by prime. For the prime $2$ the powers are $2^4$ in $a$ and $2^2$ in $b$; for the prime $3$ they are $3^2$ and $3^3$; the prime $5$ appears in $b$ alone, and the prime $7$ in $a$ alone.

The greatest common factor takes the lower power of each prime the two numbers share, and takes nothing from a prime only one of them has:

$\operatorname{GCF}(a, b) = 2^2 \times 3^2.$

The least common multiple takes the higher power of every prime that appears anywhere, unshared primes included:

$\operatorname{LCM}(a, b) = 2^4 \times 3^3 \times 5 \times 7.$

Multiplied out these come to $36$ and $15{,}120$, but the prime powers are the more useful form. In them you can see directly that the first divides both numbers, since every power in it is matched or beaten in each, and that both numbers divide the second.

The student holds one correct rule and has applied it to a question it does not govern.

For the greatest common factor the reasoning holds. A common factor divides $a$, so every prime inside it already sits inside $a$; it divides $b$, so every prime inside it sits inside $b$ as well. The prime $5$ is nowhere in $a$ and the prime $7$ is nowhere in $b$, so neither can appear in any common factor whatsoever:

$\operatorname{GCF}(a, b) = 2^2 \times 3^2.$

For the least common multiple the reasoning reverses. A common multiple must be divisible by $a$, and $a$ carries a $7$, so the multiple carries a $7$ too. It must be divisible by $b$, and $b$ carries a $5$, so the multiple carries a $5$. An unshared prime is not optional in a common multiple; it is demanded by the one number that owns it.

$\operatorname{LCM}(a, b) = 2^4 \times 3^3 \times 5 \times 7.$

Test the student's version and it collapses at once. Dropping both unshared primes leaves $2^4 \times 3^3 = 432$, and neither $a = 1{,}008$ nor $b = 540$ divides $432$, since both are larger than it. A number that is a multiple of neither number can hardly be their least common multiple.

Take the prime $2$ first. Suppose $d$ is a common factor of $a$ and $b$, and suppose $d$ contained three copies of $2$. Since $d$ divides $b$, those three copies would have to sit inside $b$ already. But

$b = 2^2 \times 3^3 \times 5$

holds exactly two copies of $2$ and no third can be extracted from it, so the supposition fails. A common factor carries at most two copies of $2$. The number $a$ has four of them to spare, and that turns out not to matter: the poorer of the two numbers sets the cap.

Now the prime $3$. Suppose $m$ is a common multiple of $a$ and $b$. Being a multiple of $b$ means

$m = b \times k = 2^2 \times 3^3 \times 5 \times k$

for some whole number $k$, so every copy of $3$ inside $b$ is already inside $m$, which is at least three of them. Here $a$ holds only two copies of $3$, and again that does not matter: the richer of the two numbers sets the demand.

Run those two arguments at every prime at once and the rules fall out. A common factor is capped, prime by prime, by whichever number holds fewer copies, so the greatest one takes the lower power throughout. A common multiple is forced, prime by prime, to match whichever number holds more, so the least one takes the higher power throughout. Lowest and highest are not a convention to be memorised. They are the two directions the definitions push in.

A card of side $s$ fits along the $40$ centimetre edge only if $s$ divides $40$, and along the $100$ centimetre edge only if $s$ divides $100$. Both conditions apply at once, so $s$ must be a common factor of the two measurements, and the largest card is the greatest common factor. In prime-power form,

$40 = 2^3 \times 5, \qquad 100 = 2^2 \times 5^2.$

Take the lower power of each shared prime, which is $2^2$ for the prime $2$ and one copy of $5$ for the prime $5$:

$\operatorname{GCF}(40, 100) = 2^2 \times 5 = 20.$

So the cards are $20$ centimetres square. The short edge takes $40 \div 20 = 2$ of them and the long edge $100 \div 20 = 5$, so the board takes

$2 \times 5 = 10 \text{ cards.}$

Both divisions came out whole, which is the check that the cards really do fit.

Both cases are settled by asking whether the side divides both measurements, not just one.

For $5$: $40 \div 5 = 8$ and $100 \div 5 = 20$, both whole. So $5$ is a common factor of the two measurements and the board takes

$8 \times 20 = 160 \text{ cards.}$

That is a legitimate covering. It is simply not the largest one, because $5$ is a common factor but not the greatest.

For $25$: $100 \div 25 = 4$ is whole, but $40 \div 25$ is not. Laid along the $40$ centimetre edge, one card covers $25$ centimetres and leaves $15$ bare, while two would reach

$25 + 25 = 50 > 40,$

hanging $10$ centimetres past the edge. No whole number of $25$ centimetre cards lands on $40$.

Dividing one measurement is not enough, and that is the whole content of the word common. Notice also that $5$ divides the $20$ centimetre answer from part A while $25$ does not, which is no accident: every common factor of two numbers is a factor of their greatest common factor, since it is held to the same lowest power at every prime.

From the same prime powers, taking the higher power of each prime:

$\operatorname{LCM}(40, 100) = 2^3 \times 5^2 = 8 \times 25 = 200.$

Now look at what the situation demands. A card has to fit a whole number of times into each edge, so its side must be a factor of each measurement. The two candidate answers sit on opposite sides of the numbers they came from:

$\operatorname{GCF}(40, 100) = 20 \le 40 \quad \text{and} \quad \operatorname{LCM}(40, 100) = 200 \ge 100.$

The greatest common factor is a factor of both numbers, so it is never larger than either of them, and a card of that size fits on the board. The least common multiple is a multiple of both, so it is never smaller than either of them: a $200$ centimetre card is five times the length of the short edge and could not be laid down at all.

That size comparison is a fast check on any answer of this shape. An answer to "how large can the identical pieces be" that comes out larger than the thing being covered has to be the wrong one of the two.

Flour arrives on days $21, 42, 63, \ldots$, the multiples of $21$, and sugar on days $35, 70, 105, \ldots$, the multiples of $35$. A day carrying both is a common multiple of the two cycles, and the next such day is the least common multiple. In prime-power form,

$21 = 3 \times 7, \qquad 35 = 5 \times 7.$

Take the highest power of every prime that appears, which here is one copy each of $3$, $5$ and $7$:

$\operatorname{LCM}(21, 35) = 3 \times 5 \times 7 = 105.$

So the two deliveries next coincide $105$ days from today. The check:

$105 \div 21 = 5, \qquad 105 \div 35 = 3,$

so that day is the fifth flour delivery and the third sugar delivery. Both counts are whole, which is exactly what makes it a day the two cycles share, and no earlier day works because $105$ is the smallest number both cycles divide.

Two separate questions are tangled together here, and they have different answers.

Is day $735$ a day both deliveries arrive? Yes:

$735 \div 21 = 35, \qquad 735 \div 35 = 21,$

both whole. Multiplying two numbers always produces a number that each of them divides, so the clerk's day is certainly a common multiple.

Is it the next such day? No. The question asked for the first coincidence, and

$735 \div 105 = 7,$

so the clerk has landed on the seventh one and walked past six earlier days when both deliveries arrive.

What went wrong is that the product counts the shared prime twice:

$21 \times 35 = (3 \times 7) \times (5 \times 7) = 3 \times 5 \times 7 \times 7,$

which carries one more $7$ than any common multiple needs. The product rule says the same thing in a single step. For two positive whole numbers, the greatest common factor times the least common multiple is the product of the numbers, so

$\operatorname{LCM}(21, 35) = (21 \times 35) \div \operatorname{GCF}(21, 35) = 735 \div 7 = 105.$

The clerk's method is right only when the two numbers share no prime at all, because only then is the divisor $1$ and the division changes nothing.

Work the new coincidence out the same way. In prime-power form,

$21 = 3 \times 7, \qquad 30 = 2 \times 3 \times 5,$

and taking the highest power of every prime that appears,

$\operatorname{LCM}(21, 30) = 2 \times 3 \times 5 \times 7 = 210.$

So the deliveries would next coincide after $210$ days, where the present cycles coincide after $105$. A shorter sugar cycle has doubled the wait, and the manager's expectation is wrong.

The product rule shows where the effect comes from. For two positive whole numbers,

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

For the present pair, $21 \times 35 = 735$ and $\operatorname{GCF}(21, 35) = 7$, giving $735 \div 7 = 105$. For the proposed pair, $21 \times 30 = 630$ and $\operatorname{GCF}(21, 30) = 3$, giving $630 \div 3 = 210$. The product did fall, just as the manager expected. What decided the outcome was the divisor. Flour and sugar at $21$ and $35$ days are both built on the prime $7$, so both cycles land on multiples of $7$ and the two patterns reuse a great deal. Move sugar to $30$ days and the only prime still shared is $3$, so far less is reused and the coincidences spread out.

How often two cycles meet is decided by what the two lengths hold in common, and not by their sizes alone.

In prime-power form,

$36 = 2^2 \times 3^2, \qquad 90 = 2 \times 3^2 \times 5.$

Lower power of each shared prime for the greatest common factor, higher power of every prime present for the least common multiple:

$\operatorname{GCF}(36, 90) = 2 \times 3^2 = 18, \qquad \operatorname{LCM}(36, 90) = 2^2 \times 3^2 \times 5 = 180.$

Now the two products:

$18 \times 180 = 3{,}240, \qquad 36 \times 90 = 3{,}240.$

They agree, and the prime powers show why they had to. For the prime $2$ the two numbers hold two copies and one copy; the greatest common factor takes the one and the least common multiple takes the two, so between them they hold three, exactly as $36$ and $90$ do between them. The same swap happens at the prime $3$, where the counts are two and two, and at the prime $5$, where they are none and one. Nothing is created and nothing is lost, only redistributed.

Everything follows from the product rule, which for two positive whole numbers $a$ and $b$ says

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

Forwards. Suppose $\operatorname{GCF}(a, b) = 1$. Putting that into the rule,

$1 \times \operatorname{LCM}(a, b) = a \times b, \qquad \text{so} \qquad \operatorname{LCM}(a, b) = a \times b.$

Backwards. Suppose instead that $\operatorname{LCM}(a, b) = a \times b$. Putting that into the rule,

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

Both numbers are positive, so $a \times b$ is not $0$, and dividing each side by it leaves

$\operatorname{GCF}(a, b) = 1.$

Both directions hold, so the two conditions are one condition wearing two faces: the least common multiple is the product precisely for pairs whose only common factor is $1$, which is to say pairs with no prime in common.

One word on scope. The product rule is a statement about two positive whole numbers, and nothing above establishes anything about three numbers at once, so the criterion should be quoted for pairs only.

A claim of the form "this happens exactly when that happens" makes two promises, and each has to be tested on its own.

One direction: can a pair that is not two primes still have the product as its least common multiple? Take $4$ and $9$:

$4 = 2^2, \qquad 9 = 3^2, \qquad \operatorname{LCM}(4, 9) = 2^2 \times 3^2 = 36 = 4 \times 9.$

Neither number is prime, so this half of the claim is false. What this pair does have is $\operatorname{GCF}(4, 9) = 1$, and by the criterion of part B that is all that was needed.

The other direction: do two primes always have the product as their least common multiple? Not always. Take $5$ and $5$:

$\operatorname{LCM}(5, 5) = 5, \qquad 5 \times 5 = 25.$

Both numbers are prime and the least common multiple is not the product, because $\operatorname{GCF}(5, 5) = 5$ rather than $1$: the two numbers share their prime with each other. Two different primes do work, since they share nothing, but the claim as written does not say different, and a claim is tested as written.

So the verdict is that the claim fails both ways. It has noticed a real pattern and named the wrong cause. What makes the least common multiple equal the product is having no prime in common, and being prime is neither necessary for that nor sufficient.