Factors and multiples: Euclid's algorithm

Advanced Math 7 · Unit 1 · euclid-gcd · Teacher edition

euclid-gcd

Name ______________________________Date ______________

1.
Write $360$ in index notation as $2^a \cdot 3^b \cdot 5^c$ . What is $a + b + c$ ?
Answer: ______________
2.
Use Euclid's algorithm to find $\gcd(252, 198)$ , then use $\operatorname{lcm}(a,b) = \dfrac{ab}{\gcd(a,b)}$ . Enter $\operatorname{lcm}(252, 198)$ .
Answer: ______________
3.
A rectangular patio measures $360$ cm by $252$ cm. It is to be covered exactly with identical square tiles, as large as possible, with no cutting. How many tiles are needed?
Answer: ______________
4.
Running Euclid's algorithm on $1071$ and $462$ gives these lines:

$1071 = 2 \times 462 + 147,\qquad 462 = 3 \times 147 + 21,\qquad 147 = 7 \times 21 + 0.$

What is $\gcd(1071, 462)$ ?
1. (A)
  $3$
2. (B)
  $7$
3. (C)
  $21$
4. (D)
  $147$
5.
Two positive integers have a product of $1080$ and a greatest common factor of $6$ . What is their least common multiple?
1. (A)
  $6$
2. (B)
  $36$
3. (C)
  $180$
4. (D)
  $216$
5. (E)
  $1080$

Answer key — Factors and multiples: Euclid's algorithm

1.
6euclid-gcd-01
$360 = 2^3 \cdot 3^2 \cdot 5$ , so $a = 3$ , $b = 2$ , $c = 1$ and $a + b + c = \mathbf{6}$ .
2.
2772euclid-gcd-02
Euclid: $252 = 1(198) + 54$ ; $198 = 3(54) + 36$ ; $54 = 1(36) + 18$ ; $36 = 2(18) + 0$ . So $\gcd = 18$ . Then $\operatorname{lcm} = \dfrac{252 \times 198}{18} = 14 \times 198 = \mathbf{2772}$ . Check: $252 = 2^2 \cdot 3^2 \cdot 7$ and $198 = 2 \cdot 3^2 \cdot 11$ , so $\operatorname{lcm} = 2^2 \cdot 3^2 \cdot 7 \cdot 11 = 2772$ . ✓
3.
70euclid-gcd-03
$\gcd(360, 252) = 36$ by Euclid (remainders $108$ , $36$ , then $0$ ). Along the $360$ cm side there are $360 \div 36 = 10$ tiles; along the $252$ cm side, $252 \div 36 = 7$ . Total $10 \times 7 = \mathbf{70}$ tiles.
4.
(C)
$21$
euclid-gcd-04
The remainders are $147 \to 21 \to 0$ . The last non-zero remainder is $\mathbf{21}$ . Check: $1071 = 21 \times 51$ and $462 = 21 \times 22$ , and $\gcd(51, 22) = 1$ . ( $147$ is stopping one line too early — and $147$ does not even divide $462$ . $7$ is the last quotient; $3$ divides both but is not the greatest.)
5.
(C)
$180$
euclid-gcd-05
$\operatorname{lcm} = \dfrac{ab}{\gcd} = \dfrac{1080}{6} = \mathbf{180}$ . One such pair is $30$ and $36$ : $\gcd = 6$ , $\operatorname{lcm} = 180$ , product $1080$ . ✓ ( $1080$ confuses the product with the lcm; $36 = 6^2$ has no identity behind it.)