Euclidean Algorithm

Name:

Class:

Date:

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)$
2.
What is the remainder when $245$ is divided by $63$ ?
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$
4.
Find $\text{GCF}(56, 21)$ with the Euclidean algorithm.
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)$ ?
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)$
7.
Find $\text{GCF}(252, 105)$ with the Euclidean algorithm.
8.
Use the Euclidean algorithm to find $\text{GCF}(391, 299)$ .
9.
Simplify $\frac{221}{247}$ to lowest terms using the Euclidean algorithm.
10.
Find $\text{LCM}(45, 75)$ using the Euclidean algorithm and $\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}$ .
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$
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?
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?
14.
The Fibonacci numbers $144$ and $89$ : run the Euclidean algorithm and find their GCF.
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$
16.
Find $\text{LCM}(126, 588)$ . Use the Euclidean algorithm for the GCF first.
17.
Find $\text{GCF}(1309, 1001)$ with the Euclidean algorithm.
18.
Find the GCF of $840$ , $1176$ and $1260$ : first $\text{GCF}(840, 1176)$ , then the GCF of that result and $1260$ .