A simple algorithm for GCD of polynomials
ISSN: 2689-7636
##### Annals of Mathematics and Physics
Research Article       Open Access      Peer-Reviewed

# A simple algorithm for GCD of polynomials

### Pasquale Nardone1* and Giorgio Sonnino2

1Physics Department, Free University of Brussels, 50 av F. D. Roosevelt, Brussels, 1050, Belgium
2Physics Department, International Solvay Institutes for Physics and Chemistry, Belgium
*Corresponding authors: Pasquale Nardone, Physics Department, Free University of Brussels, 50 av F. D. Roosevelt, Brussels, 1050, Belgium, Tel: +32475840393; E-mail: Pasquale.nardone@ulb.be
Received: 05 November, 2022 | Accepted: 15 December, 2022 | Published: 16 December, 2022
Keywords: Bezout's identity; Polynomial remainder sequence; Resultant; Discriminant

Cite this as

Nardone P, Sonnino G (2022) A simple algorithm for GCD of polynomials. Ann Math Phys 5(2): 193-195. DOI: 10.17352/amp.000065

© 2022 Nardone P, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

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(n2) for polynomials of degree n. Bezout identity could be another approach. It is a polynomial of degree n and Qn(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(n2) manipulations. If we know that we propose here another approach that uses only a linear combination of pn(x) and Qn(x) division by x to decrease the degree of both polynomials by 1.

### Method

Let's take two polynomials :

${P}_{n}\left(x\right)=\sum _{k=0}^{n}{p}_{k}^{\left(n\right)}{x}^{k}\text{ };\text{ }{Q}_{n}\left(x\right)=\sum _{k=0}^{n}{q}_{k}^{\left(n\right)}{x}^{k}$

with ${p}_{0}^{\left(n\right)}\ne 0$ and ${p}_{n}^{\left(n\right)}\ne 0$ . The corresponding list of coefficients is:

$\text{ }\text{\hspace{0.17em}}p{\text{ }}_{n}=\left\{{p}_{0}^{\left(n\right)},{p}_{1}^{\left(n\right)},\cdots ,{p}_{n-1}^{\left(n\right)},{p}_{n}^{\left(n\right)}\right\}\text{ };\text{ }\text{ }\text{\hspace{0.17em}}q{\text{ }}_{n}=\left\{{q}_{0}^{\left(n\right)},{q}_{1}^{\left(n\right)},\cdots ,{q}_{n-1}^{\left(n\right)},{q}_{n}^{\left(n\right)}\right\}$

Let's define ${\Delta }_{n}={q}_{n}^{\left(n\right)}{p}_{0}^{\left(n\right)}-{p}_{n}^{\left(n\right)}{q}_{0}^{\left(n\right)}$ . 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:

If ${\Delta }_{n}=0$ then we replace ${Q}_{n}\left(x\right)$ it by ${\stackrel{˜}{Q}}_{n}\left(x\right)$ :

This corresponds to the manipulation on the list of coefficients:

Note also that ${p}_{n-1}^{\left(n-1\right)}=-{q}_{0}^{\left(n-1\right)}=-{\Delta }_{n}$ this will remains true at all iterations ending with ${p}_{0}^{\left(0\right)}=-{q}_{0}^{\left(0\right)}=-{\Delta }_{1}$ .

Note that the new ${\stackrel{˜}{q}}_{1}^{\left(n\right)}=0$ .

In terms of list manipulation we have:

$\text{if}\text{\hspace{0.17em}}{\Delta }_{n}\ne 0\text{ }\begin{array}{c}\text{ }\text{\hspace{0.17em}}p{\text{ }}_{n-1}=Drop\left[First\left[\text{ }\text{\hspace{0.17em}}q{\text{ }}_{n}\right]\text{\hspace{0.17em}}\text{ }\text{\hspace{0.17em}}p{\text{ }}_{n}-First\left[\text{ }\text{\hspace{0.17em}}p{\text{ }}_{n}\right]\text{\hspace{0.17em}}\text{ }\text{\hspace{0.17em}}q{\text{ }}_{n},1\right]\\ \text{ }\text{\hspace{0.17em}}q{\text{ }}_{n-1}=Drop\left[Last\left[\text{ }\text{\hspace{0.17em}}q{\text{ }}_{n}\right]\text{\hspace{0.17em}}\text{ }\text{\hspace{0.17em}}p{\text{ }}_{n}-Last\left[\text{ }\text{\hspace{0.17em}}p{\text{ }}_{n}\right]\text{\hspace{0.17em}}\text{ }\text{\hspace{0.17em}}q{\text{ }}_{n},-1\right]\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}=0$ then we know that ${p}_{0}^{\left(n\right)}{q}_{n}^{\left(n\right)}-{q}_{0}^{\left(n\right)}{p}_{n}^{\left(n\right)}=0$ so the list ${p}_{0}^{\left(n\right)}\text{ }\text{\hspace{0.17em}}q{\text{ }}_{n}-{q}_{0}^{\left(n\right)}\text{ }\text{\hspace{0.17em}}p{\text{ }}_{n}$ ends with 0 so the list manipulation is :

${\stackrel{˜}{q}}_{n}=RotateRight\left[First\left[\text{ }\text{\hspace{0.17em}}p{\text{ }}_{n}\right]\text{ }\text{\hspace{0.17em}}q{\text{ }}_{n}-First\left[\text{ }\text{\hspace{0.17em}}q{\text{ }}_{n}\right]\text{ }\text{\hspace{0.17em}}p{\text{ }}_{n}\right]$

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(Pn (x),Qn (x)). must divide Pn-1 (x) and Qn-1 (x) or Pn (x) and . Repeating k times the iteration, it must divide Pn-1 (x) and Qn-1 (x).

If we reach a constant: ${P}_{0}\left(x\right)={p}_{0}^{\left(0\right)}$ and ${Q}_{0}\left(x\right)={q}_{0}^{\left(0\right)}=-{p}_{0}^{\left(0\right)}$ then $gcd\left({P}_{n}\left(x\right),{Q}_{n}\left(x\right)\right)=1$ . If we reach, some stage j of iteration, ${P}_{n-j}\left(x\right)=0$ or ${Q}_{n-j}\left(x\right)=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 Pn (x) and Qn (x) which gives a monomial xk and the polynomials are co-prime, or we reach a 0-polynomial before reaching the constant and Pn (x), Qn (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

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}={\sum }_{k=0}^{n-1}\parallel {p}_{k}^{\left(n-1\right)}\parallel$ , ${\beta }_{n-1}^{-1}={\sum }_{k=0}^{n-1}\parallel {q}_{k}^{\left(n-1\right)}\parallel$ , or that the maximum of the coefficients is always : ${\alpha }_{n-1}^{-1}=max\left({p}_{k}^{\left(n-1\right)}\right)$ , ${\beta }_{n-1}^{-1}=max\left({q}_{k}^{\left(n-1\right)}\right)$ .

For example

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

${P}_{7}\left(x\right)=-121x{Q}_{8}\left(x\right)\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{Q}_{7}\left(x\right)=148\left({P}_{8}\left(x\right)-{Q}_{8}\left(x\right)\right)$

$\left\{\begin{array}{ll}\hfill & {P}_{7}\left(x\right)=-\frac{{x}^{7}}{21}-\frac{{x}^{6}}{7}+\frac{{x}^{3}}{3}+{x}^{2}+\frac{2x}{7}+\frac{6}{7}\hfill \\ \hfill & {Q}_{7}\left(x\right)=-\frac{{x}^{7}}{16}-\frac{{x}^{6}}{12}+\frac{{x}^{5}}{12}-\frac{11{x}^{4}}{24}+\frac{41{x}^{3}}{48}+\frac{5{x}^{2}}{8}+\frac{17x}{24}+1\hfill \end{array}$

then gcd divide

$\left\{\begin{array}{ll}\hfill & {P}_{6}\left(x\right)=\frac{{x}^{6}}{78}-\frac{2{x}^{5}}{13}-\frac{2{x}^{4}}{13}+\frac{11{x}^{3}}{13}-\frac{67{x}^{2}}{78}+x-\frac{9}{13}\hfill \\ \hfill & {Q}_{6}\left(x\right)=\frac{{x}^{6}}{4}+\frac{{x}^{5}}{5}-\frac{11{x}^{4}}{10}+{x}^{3}-\frac{33{x}^{2}}{20}+\frac{4x}{5}-\frac{3}{10}\hfill \end{array}$

then gcd divide

$\left\{\begin{array}{ll}\hfill & {P}_{5}\left(x\right)=\frac{22{x}^{5}}{57}+\frac{8{x}^{4}}{19}-\frac{31{x}^{3}}{19}+{x}^{2}-\frac{115x}{57}+\frac{11}{19}\hfill \\ \hfill & {Q}_{5}\left(x\right)=-\frac{32{x}^{5}}{187}-\frac{19{x}^{4}}{187}+\frac{155{x}^{3}}{187}-\frac{151{x}^{2}}{187}+x-\frac{12}{17}\hfill \end{array}$

etc.. finally gcd divide

$\left\{\begin{array}{ll}\hfill & {P}_{3}\left(x\right)={x}^{3}+3{x}^{2}+x+3\hfill \\ \hfill & {Q}_{3}\left(x\right)=\frac{{x}^{3}}{3}+{x}^{2}+\frac{x}{3}+1\hfill \end{array}$

the next step will give ${Q}_{2}\left(x\right)=0$ ( $3{Q}_{3}\left(x\right)-{P}_{3}\left(x\right)=0$ ), with the last step:

$\left\{\begin{array}{ll}\hfill & {P}_{2}\left(x\right)={P}_{8}\left(x\right)\left(\frac{88}{63{x}^{4}}+\frac{50}{63{x}^{3}}+\frac{229}{378{x}^{2}}+\frac{143}{378x}\right)+\hfill \\ \hfill & -{Q}_{8}\left(x\right)\left(-\frac{704}{189{x}^{5}}-\frac{400}{189{x}^{4}}+\frac{164}{189{x}^{3}}-\frac{100}{189{x}^{2}}+\frac{143}{378x}\right)={x}^{3}+3{x}^{2}+x+3\hfill \\ \hfill & {Q}_{2}\left(x\right)={P}_{8}\left(x\right)\left(-\frac{6}{{x}^{3}}+x-\frac{1}{x}\right)-{Q}_{8}\left(x\right)\left(\frac{16}{{x}^{4}}-\frac{8}{{x}^{2}}+x+\frac{4}{x}-3\right)=0\hfill \end{array}$

so we have $gcd\left({P}_{8}\left(x\right),{Q}_{8}\left(x\right)\right)={x}^{3}+3{x}^{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 xm-1 by translation) we have:

${P}_{3}\left(x\right)={x}^{3}+p\text{\hspace{0.17em}}x+q\text{ }{Q}_{3}\left(x\right)={P}_{3}\left(x{\right)}^{\prime }=3{x}^{2}+p$

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

$\begin{array}{ll}\hfill & p\left(9qx+2{p}^{2}\right){P}_{3}\left(x\right)-\left(3pq{x}^{2}+\left(2{p}^{3}+9{q}^{2}\right)x+2{p}^{2}q\right){Q}_{3}\left(x\right)=-\left(4{p}^{3}+27{q}^{2}\right){x}^{3}\hfill \\ \hfill & 3p\left(2px-3q\right){P}_{3}\left(x\right)-\left(px-3q\right)\left(2px+3q\right){Q}_{3}\left(x\right)=\left(4{p}^{3}+27{q}^{2}\right){x}^{2}\hfill \end{array}$

For the general polynomial of degree :

${P}_{4}\left(x\right)={x}^{4}+p\text{\hspace{0.17em}}{x}^{2}+q\text{\hspace{0.17em}}x+r\text{ }{Q}_{4}\left(x\right)=4{x}^{3}+2p\text{\hspace{0.17em}}x+q$

in 5 iterations we have the discriminant is [5]

$disc=256{r}^{3}-128{p}^{2}{r}^{2}+144p{q}^{2}r-27{q}^{4}+16{p}^{4}r-4{p}^{3}{q}^{2}$

A more formal case [5] is:

${P}_{m}\left(x\right)={x}^{m}+a\text{\hspace{0.17em}}x+b;\text{ }{Q}_{m}\left(x\right)={P}_{m}\left(x{\right)}^{\prime }=m\text{\hspace{0.17em}}{x}^{m-1}+a$

so we have successively:

so

then

this structure will repeat, indeed, if

then ${p}_{0}^{\left(m-j\right)}=0$ , ${p}_{m-j}^{\left(m-j\right)}={B}_{j}$ , ${q}_{0}^{\left(m-j\right)}=-{B}_{j}$ , ${q}_{m-j}^{\left(m-j\right)}={C}_{j}$ , then ${\Delta }_{m-j}={B}_{j}^{2}$ and the next coefficients are:

so we have the recurrence ${A}_{j+1}=-{B}_{j}{A}_{j}$ , ${B}_{j+1}=-{B}_{j}^{2}$ and ${C}_{j+1}={C}_{j}{A}_{j}$ from $j=2$ (with ${A}_{2}=mab$ , ${B}_{2}=\left(m-1\right){a}^{2}$ , ${C}_{2}={m}^{2}b$ ) up to $j=m-2$ . At $j=m-1$ we arrive then to:

with ${p}_{0}^{\left(1\right)}={A}_{m-1}$ , ${p}_{1}^{\left(1\right)}={B}_{m-1}$ , ${q}_{1}^{\left(1\right)}={C}_{m-1}$ and ${q}_{0}^{\left(1\right)}=-{B}_{m-1}$ so ${\Delta }_{1}={C}_{m-1}{A}_{m-1}+{B}_{m-1}^{2}$ and the last iteration gives the constant:

the recurrence on ${B}_{j}$ , ${A}_{j}$ and ${C}_{j}$ gives ( $j\ge 2$ )

${B}_{j}=-{\left(\left(m-1\right){a}^{2}\right)}^{{2}^{j-2}}\text{\hspace{0.17em}};\text{\hspace{0.17em}}{A}_{j}=m\text{\hspace{0.17em}}a\text{\hspace{0.17em}}b{\left(\left(m-1\right){a}^{2}\right)}^{-1+{2}^{j-2}}$

${C}_{j}=\left(m-1\right){m}^{j}{a}^{j}{b}^{j-1}{\left(\left(m-1\right){a}^{2}\right)}^{{2}^{j-2}-j}$

so the final constant term is

${\left(m-1\right)}^{-m+{2}^{m-2}+1}{a}^{{2}^{m-1}-m}\left({m}^{m}{b}^{m-1}+{\left(m-1\right)}^{m-1}{p}^{m}\right)$

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

### 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.

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