Advanced Math 7

Chapter at a Glance

• Chapter: 1
• Strand: Pure — Numbers
• Difficulty: Level 3 of 5
• Builds on: Whole numbers: primes, GCF, and LCM, Division (2-digit divisors)

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)}$

Outcomes and Milestones

• Students can: prime factorization and exponent notation; GCF and LCM; cycle and partition stories; Euclid’s algorithm.
• Watch for: stopping Euclid one remainder too early; GCF and LCM swapped in a story.
• Ready when: $\gcd(252, 198)$ by Euclid, then LCM via $\mathrm{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:

• Prompt: Find $\gcd(48, 20)$ by Euclid's algorithm. Then find $\operatorname{lcm}(48, 20)$.
• Answer: $48 = 2 \times 20 + 8$; $20 = 2 \times 8 + 4$; $8 = 2 \times 4 + 0$. So $\gcd = 4$ and $\operatorname{lcm} = 960 \div 4 = 240$.

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:

• Prompt: Use Euclid's algorithm to find $\gcd(273, 182)$. Then find $\operatorname{lcm}(273, 182)$.
• Answer: $273 = 1 \times 182 + 91$; $182 = 2 \times 91 + 0$. So $\gcd = 91$ and $\operatorname{lcm} = \dfrac{273 \times 182}{91} = 3 \times 182 = 546$.

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:

• Prompt: $91 = 2 \times 35 + 21$. Explain why $\gcd(91, 35)$ is the same as $\gcd(35, 21)$. Then find it.
• Answer: $21 = 91 - 2 \times 35$, so any factor of both $91$ and $35$ divides $21$. And $91 = 2 \times 35 + 21$, so any factor of both $35$ and $21$ divides $91$. Same common factors. $\gcd = 7$.

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:

• Prompt: 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.
• Answer: $221 = 2 \times 91 + 39$; $91 = 2 \times 39 + 13$; $39 = 3 \times 13 + 0$, so $13$. Ropes: GCF, $10$ m. Bells: LCM, $60$ 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 chapter continues in the book.