Advanced Math 7

Try This First

Try this short activity before reading the lesson.

> Cut two paper strips. Make one $21$ cm long and one $15$ cm long. Lay the short strip along the long one and mark what is left over. It is $6$ cm. Now lay that $6$ cm piece along the $15$ cm strip as many times as it fits. What is left over now? Keep going with the new leftover until nothing is left. What is the last piece that fits exactly?

The Big Idea

Factor trees find a greatest common factor by breaking both numbers into primes. Euclid's algorithm finds it without breaking anything up. For big numbers it is much faster. Divide the larger number by the smaller one. Keep the remainder. Then divide the smaller number by that remainder. Keep going until a remainder is $0$. The last remainder that was not zero is the GCF.

Why does it work? Take any number that divides both $252$ and $198$. It also divides their difference, $252 - 198 = 54$. So the pair $(252, 198)$ and the pair $(198, 54)$ have exactly the same common factors. The pair got smaller. The answer did not change.

The LCM comes for free afterwards. $\gcd(a, b) \times \operatorname{lcm}(a, b) = ab$, so $\operatorname{lcm} = \dfrac{ab}{\gcd}$. Stories still have to be read carefully. Biggest piece and most groups want the GCF. First time together again and smallest amount that both want the LCM.

Words to Know

• gcd, GCF: Two names for one thing: the greatest common divisor, or greatest common factor. $\gcd(12, 18) = 6$.
• remainder: What is left after dividing. $252 = 1 \times 198 + 54$, so the remainder is $54$.
• algorithm: A recipe of steps that always finishes. Euclid's is about $2300$ years old. Computers still use it.
• product identity: $\gcd(a,b) \times \operatorname{lcm}(a,b) = a \times b$. Know one and you get the other.

Formulas and Theorems

• Euclid: $\gcd(a,b) = \gcd(b,\ a \bmod b)$
• LCM from GCD: $\operatorname{lcm}(a,b) = \frac{ab}{\gcd(a,b)}$

Worked Examples and Your Turn

Study each example, then try the paired problem.

Example 1: Both ways on one pair

Problem: Find $\gcd(72, 30)$ by primes. Then find it again by Euclid's algorithm. Then find $\operatorname{lcm}(72, 30)$.

Solution:

• Write the primes: $72 = 2^3 \cdot 3^2$ and $30 = 2 \cdot 3 \cdot 5$. Take each shared prime at its lowest power: $2 \cdot 3 = 6$.
• Now Euclid. Divide $72$ by $30$: $72 = 2 \times 30 + 12$. The new pair is $(30, 12)$.
• Divide $30$ by $12$: $30 = 2 \times 12 + 6$. The new pair is $(12, 6)$.
• Divide $12$ by $6$: $12 = 2 \times 6 + 0$. The remainder is zero, so stop. The last remainder that was not zero is $6$.
• Find the LCM: $\operatorname{lcm} = \dfrac{72 \times 30}{6} = \dfrac{2160}{6} = 360$.

Answer: $\gcd = 6$, $\operatorname{lcm} = 360$

> Notice: Two methods, one answer. Euclid never needed the primes of $72$. That matters when the numbers are $1071$ and $462$.

> Verification & Check: $360 \div 72 = 5$ and $360 \div 30 = 12$. Both are whole, so $360$ is a common multiple. And $6 \times 360 = 2160 = 72 \times 30$.

Your Turn 1: Find $\gcd(48, 20)$ by Euclid's algorithm. Then find $\operatorname{lcm}(48, 20)$.

Example 2: Euclid on 252 and 198, then the LCM

Problem: Use Euclid's algorithm to find $\gcd(252, 198)$. Then find $\operatorname{lcm}(252, 198)$ from the product identity.

Solution:

• Divide $252$ by $198$: $252 = 1 \times 198 + 54$. The pair is now $(198, 54)$. Why: anything that divides $252$ and $198$ also divides their difference, $54$.
• Divide $198$ by $54$: $198 = 3 \times 54 + 36$. Now $(54, 36)$.
• Divide $54$ by $36$: $54 = 1 \times 36 + 18$. Now $(36, 18)$.
• Divide $36$ by $18$: $36 = 2 \times 18 + 0$. The remainder is zero, so stop. $\gcd = 18$, the last remainder that was not zero.
• Find the LCM: $\operatorname{lcm}(252, 198) = \dfrac{252 \times 198}{18} = 14 \times 198 = 2772$.

Answer: $\gcd = 18$, $\operatorname{lcm} = 2772$

> Notice: The remainders shrink every line: $54, 36, 18, 0$. A remainder is always smaller than the number you divided by. So the chain must reach $0$. That is why the algorithm always stops.

> Verification & Check: $252 \div 18 = 14$ and $198 \div 18 = 11$. $14$ and $11$ share no factor, so nothing bigger than $18$ works. And $2772 = 252 \times 11 = 198 \times 14$.

Your Turn 2: Use Euclid's algorithm to find $\gcd(273, 182)$. Then find $\operatorname{lcm}(273, 182)$.

Example 3: Why the pair can shrink

Problem: Explain why $\gcd(252, 198)$ is the same as $\gcd(198, 54)$. Here $54$ is the remainder of $252 \div 198$.

Solution:

• Write the division as a sentence: $252 = 198 + 54$. So $54 = 252 - 198$.
• Take any number that divides both $252$ and $198$. It divides $252 - 198 = 54$ too. Why: the difference of two multiples of $d$ is a multiple of $d$. So it is a common factor of $198$ and $54$.
• Now take any number that divides both $198$ and $54$. It divides $198 + 54 = 252$. So it is a common factor of $252$ and $198$.
• Put the two facts together. The two pairs have exactly the same common factors. So they have the same greatest one.

Answer: The pairs share every common factor, so their GCFs are equal

> Notice: Nothing here depended on the numbers. The same two sentences work for any $a = qb + r$. The common factors of $(a, b)$ are the common factors of $(b, r)$. That is the whole algorithm.

Your Turn 3: $91 = 2 \times 35 + 21$. Explain why $\gcd(91, 35)$ is the same as $\gcd(35, 21)$. Then find it.

Example 4: One line too early, and the swap

Problem: Find $\gcd(1001, 385)$. Then decide which to use, GCF or LCM: a $12$ m rope and an $18$ m rope are cut into equal pieces, as long as possible. Two buses leave together and run every $12$ and $18$ minutes.

Solution:

• Run the chain: $1001 = 2 \times 385 + 231$; $385 = 1 \times 231 + 154$; $231 = 1 \times 154 + 77$; $154 = 2 \times 77 + 0$.
• Common mistake: reading off $154$, the remainder one line too early. People stop before the line that gives $0$. Test it: $385 \div 154 = 2.5$, not a whole number. $154$ is not even a factor of $385$.
• Do this instead. Run the chain until a remainder is $0$. Then take the last remainder that was not zero: $\gcd(1001, 385) = 77$. Check: $1001 = 13 \times 77$ and $385 = 5 \times 77$.
• Read the stories. The ropes want the biggest length that goes into both. That is the GCF: $\gcd(12, 18) = 6$ m. The buses want the first minute that both cycles reach. That is the LCM: $\operatorname{lcm}(12, 18) = 36$ minutes. Swap them and you get $36$ m pieces from a $12$ m rope.

Answer: $77$; ropes: GCF, $6$ m; buses: LCM, $36$ min

> Notice: A GCF is never bigger than either number. An LCM is never smaller. If your story answer breaks that rule, you picked the wrong one.

Your Turn 4: Find $\gcd(221, 91)$. Then decide, GCF or LCM: a $20$ m rope and a $30$ m rope cut into equal pieces, as long as possible. Two bells that ring every $20$ and every $30$ minutes.

Example 5: Square tiles on a floor

Problem: A floor is $420$ cm by $308$ cm. It is to be covered exactly by square tiles that are all the same size, as large as possible, with no cutting. How big are the tiles? How many are needed?

Solution:

• Read the words. "As large as possible, no cutting" means the tile side divides both $420$ and $308$. That is the GCF.
• Run Euclid: $420 = 1 \times 308 + 112$; $308 = 2 \times 112 + 84$; $112 = 1 \times 84 + 28$; $84 = 3 \times 28 + 0$. So $\gcd = 28$.
• Count the tiles. Along the length: $420 \div 28 = 15$. Along the width: $308 \div 28 = 11$. Total: $15 \times 11 = 165$.

Answer: $28$ cm tiles; $165$ of them

> Verification & Check: $165 \times 28^2 = 165 \times 784 = 129360$. And $420 \times 308 = 129360$. The tiles exactly fill the floor.

Your Turn 5: A floor is $360$ cm by $270$ cm. It is covered with the largest possible square tiles, all the same, with no cutting. How big are the tiles, and how many are needed?

Example 6: Product and GCF known

Problem: Two whole numbers have a product of $1800$ and a GCF of $15$. What is their LCM? What could the numbers be?

Solution:

• Use the product identity: $\operatorname{lcm} = \dfrac{\text{product}}{\gcd} = \dfrac{1800}{15} = 120$.
• Write the numbers as $15a$ and $15b$, with $\gcd(a, b) = 1$. Why: both numbers are multiples of $15$, and they share nothing else. Then $225ab = 1800$, so $ab = 8$.
• Find pairs with product $8$ and no common factor. $(1, 8)$ works. $(2, 4)$ does not, because both are even. So the numbers are $15$ and $120$.

Answer: $\operatorname{lcm} = 120$; the numbers are $15$ and $120$

> Verification & Check: $\gcd(15, 120) = 15$, $\operatorname{lcm}(15, 120) = 120$, and $15 \times 120 = 1800$.

Your Turn 6: Two whole numbers have a product of $600$ and a GCF of $10$. What is their LCM? What could the numbers be?

The chapter continues in the book.