Let \(x_{1}, x_{2}, \ldots\) be countably many indeterminates over \(\mathbb{Z},
R=\mathbb{Z}\left[x_{1}, x_{2}, \ldots\right]\),
$$
Q_{i}=\left(\begin{array}{cc}
0 & 1 \\
1 & x_{i}
\end{array}\right) \in R^{2 \times 2}
$$
for \(i \geq 1\), and \(R_{i}=Q_{i} \cdots Q_{1}\). We define the \(i\) th
continuant polynomial \(c_{i} \in R\) recursively by \(c_{0}=0\), \(c_{1}=1\), and
\(c_{i+1}=c_{i-1}+x_{i} c_{i}\) for \(i \geq 1\). Then \(c_{i} \in
\mathbb{Z}\left[x_{1}, \ldots, x_{i-1}\right]\) for \(i \geq 1\).
(i) List the first 10 continuant polynomials.
(ii) Let \(T\) be the "shift homomorphism" \(T x_{i}=x_{i+1}\) for \(i \geq 1\).
Show that \(c_{i+2}\left(0, x_{1}, x_{2}, \ldots, x_{i}\right)=T c_{i}\) for \(i
\geq 0\).
(iii) Show that \(R_{i}=\left(\begin{array}{cc}T c_{i-1} & c_{i} \\ T_{c_{i}}
& c_{i+1}\end{array}\right)\) for \(i \geq 1\).
(iv) Show that \(\operatorname{det} R_{i}=(-1)^{i}\), and conclude that
\(\operatorname{gcd}\left(c_{i}, c_{i+1}\right)=1\) for \(i \geq 0\).
(v) Let \(D\) be a Euclidean domain and \(r_{i}, q_{i}, s_{i}, t_{i} \in D\) for
\(0 \leq i \leq \ell\) the results of the traditional Extended Euclidean
Algorithm for \(r_{0}, r_{1}\). Show that
$$
\begin{aligned}
s_{i} &=c_{i-1}\left(-q_{2}, \ldots,-q_{i-1}\right)=(-1)^{i}
c_{i-1}\left(q_{2}, \ldots, q_{i-1}\right) \\
t_{i} &=c_{i}\left(-q_{1}, \ldots,-q_{i-1}\right)=(-1)^{i-1} c_{i}\left(q_{1},
\ldots, q_{i-1}\right)
\end{aligned}
$$
for \(1 \leq i \leq \ell\)
(vi) Write a MAPLE program that implements the traditional Extended Euclidean
Algorithm and additionally computes all continuants \(c_{i}\left(q_{\ell-i+2},
\ldots, q_{\ell}\right)\) for \(r_{0}=x^{20}\) and \(r_{1}=x^{19}+2 x^{18}+x\) in
\(\mathbb{Q}[x]\), where \(q_{1}, \ldots, q_{\ell}\) are the quotients in the
traditional Extended Euclidean Algorithm.
