1
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

You can easily prove both claims by induction.

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$.]

Can you continue with the generic case?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – ueir Feb 3 '20 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.