A simple algorithm for GCD of polynomials

Based on the Bezout approach we propose a simple algorithm to determine the gcd of two polynomials that don't need division, like the Euclidean algorithm, or determinant calculations, like the Sylvester matrix algorithm. The algorithm needs only n steps for polynomials of degree n. Formal manipulations give the discriminant or the resultant for any degree without needing division or determinant calculation.

Introduction

There exist different approaches to determining the greatest common divisor (gcd) for two polynomials, most of them are based on the Euclid algorithm [1] or matrix manipulation [2,3], or subresultant technics [4]. All these methods require long manipulations and calculations around O(n²) for polynomials of degree n. Bezout identity could be another approach. It is a polynomial of degree n and Q_n(x) is a polynomial of degree at least n, the Bezout identity says that where t(x) and s(x) are polynomials of degree less then n. Finding s(x) and t(x) requires also O(n²) manipulations. If we know that we propose here another approach that uses only a linear combination of p_n(x) and Q_n(x) division by x to decrease the degree of both polynomials by 1.

Method

Let's take two polynomials $P_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}{Q}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ :

$P_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{k\mathrm{<mo>=</mo>0}}^n}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{x}^k\mathrm{<mo>;</mo>}{Q}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{k\mathrm{<mo>=</mo>0}}^n}{q}_k^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{x}^k$

with $p_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\ne 0$ and $p_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\ne 0$ . The corresponding list of coefficients is:

$p{}_n\mathrm{<mo>=</mo><mo>\{</mo>}{p}_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{,}{p}_1^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{,}\cdots \mathrm{,}{p}_{n-1}^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{,}{p}_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>\}</mo>}\mathrm{<mo>;</mo>}q{}_n\mathrm{<mo>=</mo><mo>\{</mo>}{q}_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{,}{q}_1^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{,}\cdots \mathrm{,}{q}_{n-1}^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{,}{q}_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>\}</mo>}$

Let's define ${\Delta }_n\mathrm{<mo>=</mo>}{q}_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{p}_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}-p_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{q}_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}$ . If ${\Delta }_n\ne 0$ , we can build two new polynomials of degree n-1 by canceling the lowest degree term and the highest degree term:

$\{\begin{array}{ll}\hfill & P_{n-1}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>1}/x\left(q_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{P}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-p_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{Q}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\right)\hfill \\ \hfill & Q_{n-1}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{q}_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{P}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-p_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{Q}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\hfill \end{array}\text{ (1)}$

If ${\Delta }_n\mathrm{<mo>=</mo>0}$ then we replace $Q_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ it by ${\tilde{Q}}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ :

$\{\begin{array}{ll}\hfill & P_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{P}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\hfill \\ \hfill & {\tilde{Q}}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}x\mathrm{<mo\; stretchy="false">(</mo>}{p}_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{Q}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-q_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{P}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}\hfill \end{array}\text{ (2)}$

This corresponds to the manipulation on the list of coefficients:

$\text{if}{\Delta }_n\ne 0\{\begin{array}{c}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{q}_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{p}_{k+1}^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}-p_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{q}_{k+1}^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\\ \\ q_k^{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{q}_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}-p_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{q}_k^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\end{array}k\in \mathrm{<mo\; stretchy="false">[</mo>0,}n-\mathrm{1<mo\; stretchy="false">]</mo>}\text{ (3)}$

Note also that $p_{n-1}^{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-q_0^{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-{\Delta }_n$ this will remains true at all iterations ending with $p_0^{\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-q_0^{\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-{\Delta }_1$ .

$\text{if}{\Delta }_n\mathrm{<mo>=</mo>0}\{\begin{array}{c}{\tilde{q}}_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>0}\\ {\tilde{q}}_k^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{p}_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{q}_{k-1}^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}-q_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{p}_{k-1}^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\end{array}k\in \mathrm{<mo\; stretchy="false">[</mo>1,}n\mathrm{<mo\; stretchy="false">]</mo>}\text{ (4)}$

Note that the new ${\tilde{q}}_1^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>0}$ .

In terms of list manipulation we have:

$\text{if}{\Delta }_n\ne 0\begin{array}{c}p{}_{n-1}\mathrm{<mo>=</mo>}Drop\mathrm{<mo\; stretchy="false">[</mo>}First\mathrm{<mo\; stretchy="false">[</mo>}q{}_n\mathrm{<mo\; stretchy="false">]</mo>}p{}_n-First\mathrm{<mo\; stretchy="false">[</mo>}p{}_n\mathrm{<mo\; stretchy="false">]</mo>}q{}_n\mathrm{,1<mo\; stretchy="false">]</mo>}\\ q{}_{n-1}\mathrm{<mo>=</mo>}Drop\mathrm{<mo\; stretchy="false">[</mo>}Last\mathrm{<mo\; stretchy="false">[</mo>}q{}_n\mathrm{<mo\; stretchy="false">]</mo>}p{}_n-Last\mathrm{<mo\; stretchy="false">[</mo>}p{}_n\mathrm{<mo\; stretchy="false">]</mo>}q{}_n\mathrm{,}-\mathrm{1<mo\; stretchy="false">]</mo>}\end{array}$

where First[list] and Last[list] take the first and the last element of the list respectively, while Drop[list,1] and Drop[list,-1] drop the first and the last element of the list respectively. If ${\Delta }_n\mathrm{<mo>=</mo>0}$ then we know that $p_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{q}_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}-q_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{p}_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>0}$ so the list $p_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}q{}_n-q_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}p{}_n$ ends with 0 so the list manipulation is :

${\tilde{q}}_n\mathrm{<mo>=</mo>}RotateRight\mathrm{<mo\; stretchy="false">[</mo>}First\mathrm{<mo\; stretchy="false">[</mo>}p{}_n\mathrm{<mo\; stretchy="false">]</mo>}q{}_n-First\mathrm{<mo\; stretchy="false">[</mo>}q{}_n\mathrm{<mo\; stretchy="false">]</mo>}p{}_n\mathrm{<mo\; stretchy="false">]</mo>}$

where RotateRight[list] rotate the list to the right (RotateRight[{a,b,c}]={c,a,b}).

So we have the same Bezout argument, they gcd(P_n (x),Q_n (x)). must divide P_n-1 (x) and Q_n-1 (x) or P_n (x) and . Repeating k times the iteration, it must divide P_n-1 (x) and Q_n-1 (x).

If we reach a constant: $P_0\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{p}_0^{\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo>}}$ and $Q_0\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{q}_0^{\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-p_0^{\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo>}}$ then $gcd\mathrm{<mo\; stretchy="false">(</mo>}{P}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>,}{Q}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>1}$ . If we reach, some stage j of iteration, $P_{n-j}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>0}$ or $Q_{n-j}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>0}$ then the previous stage j-1 contains the gcd.

Repeating these steps decrease the degree of polynomials. Reversing the process enables us to find a combination of P_n (x) and Q_n (x) which gives a monomial x^k and the polynomials are co-prime, or we reach a 0-polynomial before reaching the constant and P_n (x), Q_n (x) have a nontrivial gcd.

Results

When dealing with numbers the recurrence could give large numbers so we can normalize the polynomials by some constant

$\begin{array}{ll}\hfill & P_{n-1}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\alpha }_{n-1}x\left(q_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{P}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-p_0^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{Q}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\right)\hfill \\ \hfill & Q_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\beta }_{n-1}\left(q_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{P}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-p_n^{\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{Q}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\right)\hfill \end{array}\text{ (5)}$

Choosing for example α and β such that the sum of the absolute value of the coefficients of Pn-1 (x) and Qn-1 (x) are : ${\alpha }_{n-1}^{-1}\mathrm{<mo>=</mo>}{\displaystyle {\sum }_{k\mathrm{<mo>=</mo>0}}^{n-1}}\parallel p_k^{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}}\parallel$ , ${\beta }_{n-1}^{-1}\mathrm{<mo>=</mo>}{\displaystyle {\sum }_{k\mathrm{<mo>=</mo>0}}^{n-1}}\parallel q_k^{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}}\parallel$ , or that the maximum of the coefficients is always : ${\alpha }_{n-1}^{-1}\mathrm{<mo>=</mo>}max\mathrm{<mo\; stretchy="false">(</mo>}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo\; stretchy="false">)</mo>}$ , ${\beta }_{n-1}^{-1}\mathrm{<mo>=</mo>}max\mathrm{<mo\; stretchy="false">(</mo>}{q}_k^{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo\; stretchy="false">)</mo>}$ .

For example

$\begin{array}{ll}\hfill & \{\begin{array}{ll}\hfill & P_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{x}^8-4x^6+4x^5-29x^4+20x^3+24x^2+16x+48\hfill \\ \hfill & Q_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{x}^8+3x^7-7x^4-21x^3-6x^2-18x\hfill \end{array}\hfill \\ \hfill & \{\begin{array}{ll}\hfill & p{}_8\mathrm{<mo>=</mo><mo>\{</mo>48,16,24,20,}-\mathrm{29,4,}-\mathrm{4,0,1<mo>\}</mo>}\hfill \\ \hfill & q{}_8\mathrm{<mo>=</mo><mo>\{</mo>0,}-\mathrm{18,}-\mathrm{6,}-\mathrm{21,}-\mathrm{7,0,0,3,1<mo>\}</mo>}\hfill \end{array}\hfill \end{array}\text{ (6)}$

and let's use the ``max" normalization. The first iteration says that gcd must divide P7 (x) and Q7 (x):

$P_7\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-121x{Q}_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\text{and}{Q}_7\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>148<mo\; stretchy="false">(</mo>}{P}_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-Q_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$

$\{\begin{array}{ll}\hfill & P_7\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-\frac{x^7}{21}-\frac{x^6}{7}+\frac{x^3}{3}+x^2+\frac{2x}{7}+\frac{6}{7}\hfill \\ \hfill & Q_7\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-\frac{x^7}{16}-\frac{x^6}{12}+\frac{x^5}{12}-\frac{11x^4}{24}+\frac{41x^3}{48}+\frac{5x^2}{8}+\frac{17x}{24}+1\hfill \end{array}$

then gcd divide

$\{\begin{array}{ll}\hfill & P_6\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{x^6}{78}-\frac{2x^5}{13}-\frac{2x^4}{13}+\frac{11x^3}{13}-\frac{67x^2}{78}+x-\frac{9}{13}\hfill \\ \hfill & Q_6\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{x^6}{4}+\frac{x^5}{5}-\frac{11x^4}{10}+x^3-\frac{33x^2}{20}+\frac{4x}{5}-\frac{3}{10}\hfill \end{array}$

then gcd divide

$\{\begin{array}{ll}\hfill & P_5\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{22x^5}{57}+\frac{8x^4}{19}-\frac{31x^3}{19}+x^2-\frac{115x}{57}+\frac{11}{19}\hfill \\ \hfill & Q_5\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-\frac{32x^5}{187}-\frac{19x^4}{187}+\frac{155x^3}{187}-\frac{151x^2}{187}+x-\frac{12}{17}\hfill \end{array}$

etc.. finally gcd divide

$\{\begin{array}{ll}\hfill & P_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{x}^3+3x^2+x+3\hfill \\ \hfill & Q_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{x^3}{3}+x^2+\frac{x}{3}+1\hfill \end{array}$

the next step will give $Q_2\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>0}$ ( $3Q_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-P_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>0}$ ), with the last step:

$\{\begin{array}{ll}\hfill & P_2\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{P}_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\left(\frac{88}{63x^4}+\frac{50}{63x^3}+\frac{229}{378x^2}+\frac{143}{378x}\right)+\hfill \\ \hfill & -Q_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\left(-\frac{704}{189x^5}-\frac{400}{189x^4}+\frac{164}{189x^3}-\frac{100}{189x^2}+\frac{143}{378x}\right)\mathrm{<mo>=</mo>}{x}^3+3x^2+x+3\hfill \\ \hfill & Q_2\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{P}_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\left(-\frac{6}{x^3}+x-\frac{1}{x}\right)-Q_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\left(\frac{16}{x^4}-\frac{8}{x^2}+x+\frac{4}{x}-3\right)\mathrm{<mo>=</mo>0}\hfill \end{array}$

so we have $gcd\mathrm{<mo\; stretchy="false">(</mo>}{P}_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>,}{Q}_8\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>}{x}^3+3x^2+x+3$

Doing the algorithm on formal polynomials gives automatically the resultant or the discriminant of Pn (x) and Qn (x).

For example for the gcd of Pn (x) and for formal polynomials (we always cancel the term x^m-1 by translation) we have:

$P_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{x}^3+px+q{Q}_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{P}_3\mathrm{<mo\; stretchy="false">(</mo>}x{)}^{\prime }\mathrm{<mo>=</mo>3}{x}^2+p$

gives after 3 iterations the well-known discriminant , and the Bezout expression is:

$\begin{array}{ll}\hfill & p\mathrm{<mo\; stretchy="false">(</mo>9}qx+2p^2\mathrm{<mo\; stretchy="false">)</mo>}{P}_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-\mathrm{<mo\; stretchy="false">(</mo>3}pq{x}^2+\mathrm{<mo\; stretchy="false">(</mo>2}{p}^3+9q^2\mathrm{<mo\; stretchy="false">)</mo>}x+2p^{2}q\mathrm{<mo\; stretchy="false">)</mo>}{Q}_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-\mathrm{<mo\; stretchy="false">(</mo>4}{p}^3+27q^2\mathrm{<mo\; stretchy="false">)</mo>}{x}^3\hfill \\ \hfill & 3p\mathrm{<mo\; stretchy="false">(</mo>2}px-3q\mathrm{<mo\; stretchy="false">)</mo>}{P}_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-\mathrm{<mo\; stretchy="false">(</mo>}px-3q\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>2}px+3q\mathrm{<mo\; stretchy="false">)</mo>}{Q}_3\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>4}{p}^3+27q^2\mathrm{<mo\; stretchy="false">)</mo>}{x}^2\hfill \end{array}$

For the general polynomial of degree :

$P_4\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{x}^4+p{x}^2+qx+r{Q}_4\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>4}{x}^3+2px+q$

in 5 iterations we have the discriminant is [5]

$disc\mathrm{<mo>=</mo>256}{r}^3-128p^2{r}^2+144p{q}^{2}r-27q^4+16p^{4}r-4p^3{q}^2$

A more formal case [5] is:

$P_m\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{x}^m+ax+b\mathrm{<mo>;</mo>}{Q}_m\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{P}_m\mathrm{<mo\; stretchy="false">(</mo>}x{)}^{\prime }\mathrm{<mo>=</mo>}m{x}^{m-1}+a$

so we have successively:

$k\in \mathrm{<mo\; stretchy="false">[</mo>0,}m\mathrm{<mo\; stretchy="false">]</mo>}\mathrm{<mo>:</mo>}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>}m\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}b{\delta }_0^k+a{\delta }_1^k+{\delta }_m^k\text{and}{q}_k^{\mathrm{<mo\; stretchy="false">(</mo>}m\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}a{\delta }_0^k+m{\delta }_{m-1}^k\text{ (7)}$

so

$\begin{array}{ll}\hfill & p_0^{\mathrm{<mo\; stretchy="false">(</mo>}m\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}b\mathrm{<mo>;</mo>}{p}_m^{\mathrm{<mo\; stretchy="false">(</mo>}m\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>1}\mathrm{<mo>;</mo>}{q}_0^{\mathrm{<mo\; stretchy="false">(</mo>}m\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}a\mathrm{<mo>;</mo>}{q}_m^{\mathrm{<mo\; stretchy="false">(</mo>}m\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>0}\mathrm{<mo>;</mo>}{\Delta }_m\mathrm{<mo>=</mo>}-a\hfill \\ \hfill & k\in \mathrm{<mo\; stretchy="false">[</mo>0,}m-\mathrm{1<mo\; stretchy="false">]</mo>}\{\begin{array}{c}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{a}^2{\delta }_0^k-mb{\delta }_{m-2}^k+a{\delta }_{m-1}^k\\ q_k^{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-a{\delta }_0^k-m{\delta }_{m-1}^k\end{array}\hfill \end{array}\text{ (8)}$

then

$\begin{array}{ll}\hfill & p_0^{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{a}^2\mathrm{<mo>;</mo>}{p}_{m-1}^{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}a\mathrm{<mo>;</mo>}{q}_0^{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-a\mathrm{<mo>;</mo>}{q}_{m-1}^{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-m\mathrm{<mo>;</mo>}{\Delta }_{m-1}\mathrm{<mo>=</mo>}-\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}{a}^2\hfill \\ \hfill & k\in \mathrm{<mo\; stretchy="false">[</mo>0,}m-\mathrm{2<mo\; stretchy="false">]</mo>}\{\begin{array}{c}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{2<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}mab{\delta }_{m-3}^k+\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}{a}^2{\delta }_{m-2}^k\\ q_k^{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{2<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}{a}^2{\delta }_0^k+m^{2}b{\delta }_{m-2}^k\end{array}\hfill \end{array}\text{ (9)}$

this structure will repeat, indeed, if

$k\in \mathrm{<mo\; stretchy="false">[</mo>0,}m-j\mathrm{<mo\; stretchy="false">]</mo>}\{\begin{array}{c}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>}m-j\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{A}_j{\delta }_{m-j-1}^k+B_j{\delta }_{m-j}^k\\ q_k^{\mathrm{<mo\; stretchy="false">(</mo>}m-j\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-B_j{\delta }_0^k+C_j{\delta }_{m-j}^k\end{array}\text{ (10)}$

then $p_0^{\mathrm{<mo\; stretchy="false">(</mo>}m-j\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>0}$ , $p_{m-j}^{\mathrm{<mo\; stretchy="false">(</mo>}m-j\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{B}_j$ , $q_0^{\mathrm{<mo\; stretchy="false">(</mo>}m-j\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-B_j$ , $q_{m-j}^{\mathrm{<mo\; stretchy="false">(</mo>}m-j\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{C}_j$ , then ${\Delta }_{m-j}\mathrm{<mo>=</mo>}{B}_j^2$ and the next coefficients are:

$k\in \mathrm{<mo\; stretchy="false">[</mo>0,}m-j-\mathrm{1<mo\; stretchy="false">]</mo>}\{\begin{array}{c}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>}m-j-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-B_j{A}_j{\delta }_{m-j-2}^k-B_j^2{\delta }_{m-j-1}^k\\ q_k^{\mathrm{<mo\; stretchy="false">(</mo>}m-j-\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{B}_j^2{\delta }_0^k+C_j{A}_j{\delta }_{m-j-1}^k\end{array}\text{ (11)}$

so we have the recurrence $A_{j+1}\mathrm{<mo>=</mo>}-B_j{A}_j$ , $B_{j+1}\mathrm{<mo>=</mo>}-B_j^2$ and $C_{j+1}\mathrm{<mo>=</mo>}{C}_j{A}_j$ from $j\mathrm{<mo>=</mo>2}$ (with $A_2\mathrm{<mo>=</mo>}mab$ , $B_2\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}{a}^2$ , $C_2\mathrm{<mo>=</mo>}{m}^{2}b$ ) up to $j\mathrm{<mo>=</mo>}m-2$ . At $j\mathrm{<mo>=</mo>}m-1$ we arrive then to:

$k\in \mathrm{<mo\; stretchy="false">[</mo>0,1<mo\; stretchy="false">]</mo>}\{\begin{array}{c}{p}_k^{\mathrm{<mo\; stretchy="false">(</mo>1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{A}_{m-1}{\delta }_0^k+B_{m-1}{\delta }_1^k\\ q_k^{\mathrm{<mo\; stretchy="false">(</mo>1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-B_{m-1}{\delta }_0^k+C_{m-1}{\delta }_1^k\end{array}\text{ (12)}$

with $p_0^{\mathrm{<mo\; stretchy="false">(</mo>1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{A}_{m-1}$ , $p_1^{\mathrm{<mo\; stretchy="false">(</mo>1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{B}_{m-1}$ , $q_1^{\mathrm{<mo\; stretchy="false">(</mo>1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{C}_{m-1}$ and $q_0^{\mathrm{<mo\; stretchy="false">(</mo>1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-B_{m-1}$ so ${\Delta }_1\mathrm{<mo>=</mo>}{C}_{m-1}{A}_{m-1}+B_{m-1}^2$ and the last iteration gives the constant:

$\{\begin{array}{c}{p}_0^{\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-B_{m-1}^2-A_{m-1}{C}_{m-1}\\ q_0^{\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}{C}_{m-1}{A}_{m-1}+B_{m-1}^2\end{array}\text{ (13)}$

the recurrence on $B_j$ , $A_j$ and $C_j$ gives ( $j\ge 2$ )

$B_j\mathrm{<mo>=</mo>}-{\left(\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}{a}^2\right)}^{2^{j-2}}\mathrm{<mo>;</mo>}{A}_j\mathrm{<mo>=</mo>}mab{\left(\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}{a}^2\right)}^{-1+2^{j-2}}$

$C_j\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}{m}^j{a}^j{b}^{j-1}{\left(\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}{a}^2\right)}^{2^{j-2}-j}$

so the final constant term is

${\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}}^{-m+2^{m-2}+1}{a}^{2^{m-1}-m}\left(m^m{b}^{m-1}+{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}}^{m-1}{p}^m\right)$

we can factorize the constant and the discriminant is then [5]

$m^m{b}^{m-1}+{\mathrm{<mo\; stretchy="false">(</mo>}m-\mathrm{1<mo\; stretchy="false">)</mo>}}^{m-1}{a}^m\text{ (14)}$

Discussion

The algorithm developed here could be used for formal or numerical calculation of the gcd of two polynomials, or the discriminant and the resultant. It doesn't use matrix manipulation nor determinant calculations and for polynomials of order n, it takes n steps to achieve the goal. It provide also the two polynomials needed for Bezout identity.

Supplementary information

Data sharing is not applicable to this article as no datasets were generated or analyzed during the current study.

Appendix

1. Knuth DE. The Art of Computer Programming. Addison-Wesley, Reading, Mass. 1969; 2.
2. Bini DA, Boito P. Structured matrix-based methods for polynomial -gcd: analysis and comparisons. In Proceedings of the 2007 international symposium on Symbolic and algebraic computation (ISSAC '07). Association for Computing Machinery, New York, NY. USA. 9-16. 2007. DOI:https://doi.org/10.1145/1277548.1277551
3. Fazzi A, Guglielmi N, Markovsky I. Generalized algorithms for the approximate matrix polynomial GCD of reducing data uncertainties with application to MIMO system and control. Journal of Computational and Applied Mathematics. 2021; 393: 113499. https://doi.org/10.1016/j.cam.2021.113499
4. Brown WS, Traub JF. On Euclid's Algorithm and the Theory of Subresultants. J ACM. 1971; 18: 505-514. DOI:https://doi.org/10.1145/321662.321665
5. http://www2.math.uu.se/ svante/papers/sjN5.pdf