1. Use the Euclidean algorithm from Theorem 4 in $\S 3$ to find the greatest common divisor (gcd) of the following sets of numbers, and express the gcd as an integer linear combination of these numbers:
(i) 1819, 3587;
(ii) 2947, 3997;
(iii) $-1109, 4999$.
1. (i) $3587=1819+1768,1819=1768+51,1768=34 \cdot 51+34,51=$ $1 \cdot 34+17,34=2 \cdot 17$, so $(3587,1819)=17$.
$$\begin{aligned}
17 & =51-34=51-(1768-34 \cdot 51) \\
& =35 \cdot 51-1768=35(1819-1768)-1768 \\
& =35 \cdot 1819-36 \cdot 1768=35 \cdot 1819-36(3587-1819) \\
& =-36 \cdot 3587+71 \cdot 1819
\end{aligned}$$
(ii) $(2947,3997)=7=-87 \cdot 3997+118 \cdot 2947$;
(iii) $(-1109,4999)=1=522 \cdot 4999+2353 \cdot(-1109)$.