###### tags: `MATA02-2022`
# Ungraded problems 3

You are to work on these questions only for the benefit of learning the material. These problems are meant for practice, not an assignment to be handed in.

## 1.
Use the Euclidean Algorithm to find the greatest common divisor (gcd) of the following pairs of numbers. You must show your work.

1. (51, 96)
2. (49, 76)
3. (4025, 840)


## 2.
In the textbook *The Magic of Numbers*, Example 9.3.1, the Euclidean algorithm is used to find the greatest common divisor of 271 and 670. This calculation is then used to express the greatest common divisor, 1, in terms of 271 and 670:
$$ 1=-87 \cdot 271 + 36 \cdot 670$$

We did similar examples in class as well. Carry out the analogous calculation for each of the three pairs of numbers above to express the great common divisor in each case in terms of the original pair of numbers.

1. (51, 96)
2. (49, 76)
3. (4025, 840)


## Selected (partial) solutions
<details>
<summary>Solutions to (without work)</summary>
The process is identical to the example given above. Note that if you encounter similar problems on a quiz or homework, you MUST show your work. Here, however, I've just included the final answers for you to double check your work.

Problem 1:
1. 3
2. 1
3. 35 because $\gcd(4025,840)=\gcd(840,665)=\gcd(665,175)=\gcd(175,140)=\gcd(140,35)=35$

Problem 2:

3. $35 = 4025 \cdot (-5) + 840 \cdot 24$

</details>