Euclidean Algorithm

Show your work for each problem.

1.
In the Euclidean algorithm you write $a = q \times b + r$ with $0 \le r < b$ . Which pair do you divide next?
1. a) $(a, b - r)$
2. b) $(b, r)$
3. c) $(q, r)$
4. d) $(a, r)$
Answer: $(b, r)$
The next pair is $(b, r)$ , because $\text{GCF}(a, b) = \text{GCF}(b, r)$ . The number $a$ is no longer needed.
2.
What is the remainder when $245$ is divided by $63$ ?
Answer: 56
$245 = 3 \times 63 + 56$ , since $63 \times 3 = 189$ and $245 - 189 = 56$ . The remainder $56$ is smaller than $63$ , as it must be.
3.
The Euclidean algorithm for $60$ and $42$ gives $60 = 1 \times 42 + 18$ , $42 = 2 \times 18 + 6$ , $18 = 3 \times 6 + 0$ . What is $\text{GCF}(60, 42)$ ?
1. a) $6$
2. b) $0$
3. c) $18$
4. d) $2$
Answer: $6$
The remainder becomes $0$ in the row $18 = 3 \times 6 + 0$ , so the GCF is the divisor of that row: $6$ . Not $0$ (the stop signal) and not $3$ (a quotient).
4.
Find $\text{GCF}(56, 21)$ with the Euclidean algorithm.
Answer: 7
1. What is the remainder when $56$ is divided by $21$ ? 14
2. What is the remainder when $21$ is divided by $14$ ? 7
3. What is the remainder when $14$ is divided by $7$ ? 0
4. So what is $\text{GCF}(56, 21)$ ? 7
5.
With the subtraction version on $30$ and $12$ you get $30 - 12 = 18$ , $18 - 12 = 6$ , $12 - 6 = 6$ , $6 - 6 = 0$ . What is $\text{GCF}(30, 12)$ ?
Answer: 6
The pair ends as $(6, 6)$ , so $\text{GCF}(30, 12) = 6$ . The two subtractions of $12$ are the division $30 = 2 \times 12 + 6$ .
6.
Which pair of numbers is coprime (GCF $= 1$ )?
1. a) $(12, 18)$
2. b) $(15, 28)$
3. c) $(22, 33)$
4. d) $(14, 21)$
Answer: $(15, 28)$
$28 = 1 \times 15 + 13$ , $15 = 1 \times 13 + 2$ , $13 = 6 \times 2 + 1$ , $2 = 2 \times 1 + 0$ : $\text{GCF}(15, 28) = 1$ . The others share $7$ , $6$ and $11$ .
7.
Find $\text{GCF}(252, 105)$ with the Euclidean algorithm.
Answer: 21
1. What is the remainder when $252$ is divided by $105$ ? 42
2. What is the remainder when $105$ is divided by $42$ ? 21
3. What is the remainder when $42$ is divided by $21$ ? 0
4. So what is $\text{GCF}(252, 105)$ ? 21
8.
Use the Euclidean algorithm to find $\text{GCF}(391, 299)$ .
Answer: 23
$391 = 1 \times 299 + 92$ , $299 = 3 \times 92 + 23$ , $92 = 4 \times 23 + 0$ . So $\text{GCF}(391, 299) = 23$ ( $391 = 17 \times 23$ , $299 = 13 \times 23$ ).
9.
Simplify $\frac{221}{247}$ to lowest terms using the Euclidean algorithm.
Answer: 17/19
1. What is the remainder when $247$ is divided by $221$ ? 26
2. What is the remainder when $221$ is divided by $26$ ? 13
3. $26 = 2 \times 13 + 0$ . So what is $\text{GCF}(221, 247)$ ? 13
4. Divide the numerator: what is $221 \div 13$ ? 17
5. Divide the denominator: what is $247 \div 13$ ? 19
10.
Find $\text{LCM}(45, 75)$ using the Euclidean algorithm and $\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}$ .
Answer: 225
1. What is the remainder when $75$ is divided by $45$ ? 30
2. What is the remainder when $45$ is divided by $30$ ? 15
3. $30 = 2 \times 15 + 0$ . So what is $\text{GCF}(45, 75)$ ? 15
4. What is $\text{LCM}(45, 75) = \frac{45 \times 75}{15}$ ? 225
11.
A number $d$ divides both $a$ and $b$ , and $a = q \times b + r$ . Which number must $d$ also divide?
1. a) $q$
2. b) $r$
3. c) $a + q$
4. d) $q + r$
Answer: $r$
$r = a - q \times b$ . If $d$ divides $a$ and $b$ , it divides $a$ minus a multiple of $b$ , so it divides $r$ . That is why $\text{GCF}(a, b) = \text{GCF}(b, r)$ .
12.
A rectangle is $77$ by $28$ . What is the side of the largest square that tiles it exactly, with no gaps and no cutting?
Answer: 7
$77 = 2 \times 28 + 21$ , $28 = 1 \times 21 + 7$ , $21 = 3 \times 7 + 0$ , so $\text{GCF}(77, 28) = 7$ : squares of side $7$ , $11 \times 4 = 44$ of them.
13.
A wooden board is $96$ cm by $60$ cm. It is cut into equal squares, as large as possible, with nothing left over. How many squares do you get?
Answer: 40
1. What is the remainder when $96$ is divided by $60$ ? 36
2. What is the remainder when $60$ is divided by $36$ ? 24
3. What is the remainder when $36$ is divided by $24$ ? 12
4. $24 = 2 \times 12 + 0$ . What is the side of the largest square, in cm? 12
5. How many such squares do you get from the board? 40
14.
The Fibonacci numbers $144$ and $89$ : run the Euclidean algorithm and find their GCF.
Answer: 1
1. What is the remainder when $144$ is divided by $89$ ? 55
2. What is the remainder when $89$ is divided by $55$ ? 34
3. What is the remainder when $55$ is divided by $34$ ? 21
4. The remainders continue $13, 8, 5, 3, 2, 1, 0$ . What is $\text{GCF}(144, 89)$ ? 1
15.
For any two positive whole numbers $a$ and $b$ , what is $\text{GCF}(a, b) \times \text{LCM}(a, b)$ equal to?
1. a) $a \times b$
2. b) $\frac{a}{b}$
3. c) $a + b$
4. d) $a - b$
Answer: $a \times b$
$\text{GCF}(a, b) \times \text{LCM}(a, b) = a \times b$ . For $4$ and $6$ : $2 \times 12 = 24 = 4 \times 6$ . That is why $\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}$ .
16.
Find $\text{LCM}(126, 588)$ . Use the Euclidean algorithm for the GCF first.
Answer: 1764
$588 = 4 \times 126 + 84$ , $126 = 1 \times 84 + 42$ , $84 = 2 \times 42 + 0$ , so the GCF is $42$ and the LCM is $\frac{126 \times 588}{42} = 126 \times 14 = 1764$ .
17.
Find $\text{GCF}(1309, 1001)$ with the Euclidean algorithm.
Answer: 77
1. What is the remainder when $1309$ is divided by $1001$ ? 308
2. Now divide $1001$ by $308$ . What is the quotient $q$ ? 3
3. And the remainder in $1001 = 3 \times 308 + r$ ? 77
4. What is the remainder when $308$ is divided by $77$ ? 0
5. So what is $\text{GCF}(1309, 1001)$ ? 77
18.
Find the GCF of $840$ , $1176$ and $1260$ : first $\text{GCF}(840, 1176)$ , then the GCF of that result and $1260$ .
Answer: 84
1. What is the remainder when $1176$ is divided by $840$ ? 336
2. What is the remainder when $840$ is divided by $336$ ? 168
3. $336 = 2 \times 168 + 0$ . So what is $\text{GCF}(840, 1176)$ ? 168
4. What is the remainder when $1260$ is divided by $168$ ? 84
5. $168 = 2 \times 84 + 0$ . So what is $\text{GCF}(168, 1260)$ ? 84