Polynomial ring/Field/Lemma of Bezout/Determining greatest common divisor/Remark

For given polynomials ${}P_{1},\ldots ,P_{n}\in K[X]$, we can determine explicitly their greatest common divisor ${}G$ and a representation

${}G=Q_{1}P_{1}+\cdots +Q_{n}P_{n}\,$

as stated in fact. For this, we restrict ourselves to the case ${}n=2$. Let the degree of ${}P_{1}$ be as large as the degree of ${}P_{2}$. The division with remainder yields

${}P_{1}=P_{2}H_{2}+R_{2}\,$

with a remaining polynomial, whose degree is smaller than the degree of ${}P_{2}$, or which is ${}0$. The main point is that the ideals

${}(P_{1},P_{2})=(P_{2},R_{2})\,$

are identical and, thus, the greatest common divisor of ${}P_{1}$ and ${}P_{2}$ and of ${}P_{2}$ and ${}R_{2}$ coincide. Now we perform again the division with remainder, dividing ${}P_{2}$ by ${}R_{2}$ with remainder ${}R_{3}$, and again the ideal ${}(R_{2},R_{3})$ coincides with the starting ideal. In this way, we obtain a sequence of remaining polynomials

$R_{0}=P_{1},R_{1}=P_{2},R_{2},\ldots ,R_{k}\neq 0,0,$

with the property that two adjacent polynomials generate the same ideal. Hence, ${}R_{k}$ (the last remaining polynomial different from ${}0$) is the greatest common divisor of ${}R_{0}$ and ${}R_{1}$. We can find a representation of ${}R_{k}$ as a linear combination of the ${}R_{0},R_{1}$, by working back this algorithm using the equations which describe the divisions with remainder.