# Property of Euclidean algorithm

The Euclid's algorithm for computing the greatest common divisor of two polynomials $$r_i(z)$$ and $$r_0(z)$$ can be done iteratively as follows, where we assume $$\deg r_ 1 > \deg r_0$$. $$r_{-1}(z)=q_1(z)r_0(z)+r_1(z),\deg r_{-1}=\deg q_1+\deg r_0,\deg r_0>\deg r_1,$$ $$r_{0}(z)=q_2(z)r_1(z)+r_2(z),\deg r_{0}=\deg q_2+\deg r_1,\deg r_1 > \deg r_2,$$ $$r_{1}(z)=q_3(z)r_2(z)+r_3(z),\deg r_{1}=\deg q_3+\deg r_2,\deg r_2 > \deg r_3,$$ $$\vdots$$

This iteration can be rewritten in the matrix form as follows: $$\begin{pmatrix} q_i(z) & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{i-1}(z) \\ r_{i}(z) \end{pmatrix} = \begin{pmatrix} r_{i-2}(z) \\ r_{i-1}(z) \end{pmatrix}$$ We define $$U_i(z),V_i(z)$$ as $$\begin{pmatrix} U_i(z) & U_{i-1}(z) \\ V_i(z) & V_{i-1}(z) \end{pmatrix}= \prod_{k=1}^{i} \begin{pmatrix} q_k(z) & 1 \\ 1 & 0 \end{pmatrix}$$

According to equation $$11$$ of this article on page 91, $$\deg U_i = \deg r_{-1} - \deg r_{i-1}$$ will be satisfied. Is this obvious?

Author say this is equivalent to $$\deg r_{i-1}=\deg r_{-1} - \sum_{j=1}^i \deg q_{i}$$.

How to prove this ?

For $$i=1$$, we have $$U_1=q_1$$ and $$\deg q_1=\deg r_{-1}-\deg r_0$$.
[Though, we could as well have started with $$i=0$$, when $$U_0=1$$.]
• I got it. From $\deg r_{-1}=\deg q_1+\deg r_0, \deg r_{0}=\deg q_2+\deg r_1, \deg r_{1}=\deg q_3+\deg r_2, \ldots$, we get $\deg r_{-1}=\deg q_1+\deg r_0=\deg q_1+\deg q_2+\deg r_1=\deg q_1+\deg q_2+\deg q_3+\deg r_2=\ldots$. Thank you. – ueir Feb 3 '20 at 23:26