Simple algorithm for GCD of polynomials
NARDONE PASQUALE,SONNINO GIORGIO
Physics Department
Université Libre de Bruxelles
50 av F. D. Roosevelt, Bruxelles 1050
BELGIUM
Abstract: Based on the Bezout approach we propose a simple algorithm to determine the gcd of two polyno-
mials which doesn’t need division, like the Euclidean algorithm, or determinant calculations, like the Sylvester
matrix algorithm. The algorithm needs only nsteps for polynomials of degree n. Formal manipulations give the
discriminant or the resultant for any degree without needing division nor determinant calculation.
Key-Words: Bezout’s identity, polynomial remainder sequence, resultant, discriminant
1 Introduction
There exist different approach to determine the great-
est common divisor (gcd) for two polynomials, most
of them are based on Euclid algorithm [1] or matrix
manipulation [4] [5] or subresultant
techniques [2]. All
these methods require are
long manipulations and cal-
culations around O(n2)for polynomials of degree n.
Bezout identity could be another approach. If Pn(x)
is a polynomial of degree nand Qn(x)is a polyno-
mial of degree at least n, the Bezout identity says
that gcd(Pn(x), Qn(x)) = s(x)Pn(x) + t(x)Qn(x)
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 Pn(0) = 0 we pro-
pose here another approach which use only a linear
combination of Pn(x)and Qn(x)and division by x
to decrease the degree of both polynomials by 1.
2 Problem Formulation
Let’s take two polynomials Pn(x)and Qn(x):
Pn(x) =
n
k=0
p(n)
kxk;Qn(x) =
n
k=0
q(n)
kxk
with p(n)
0= 0 and p(n)
n= 0. The corresponding list
of coefficients are:
pn={p(n)
0, p(n)
1,· · · , p(n)
n−1, p(n)
n}
qn={q(n)
0, q(n)
1,· · · , q(n)
n−1, q(n)
n}
Let’s define ∆n=q(n)
np(n)
0−p(n)
nq(n)
0. If ∆n= 0,
we can build two new polynomials of degree n−1
by cancelling the lowest degree term and the highest
degree term:
Pn−1(x) = 1
x(q(n)
0Pn(x)−p(n)
0Qn(x))
Qn−1(x) = q(n)
nPn(x)−p(n)
nQn(x)
(1)
If ∆n= 0 then we replace Qn(x)by ˜
Qn(x):
Pn(x) = Pn(x)
˜
Qn(x) = x(p(n)
0Qn(x)−q(n)
0Pn(x))
(2)
This correspond to the manipulation on the list of
coefficients:
p(n−1)
k=q(n)
0p(n)
k+1 −p(n)
0q(n)
k+1
q(n−1)
k=q(n)
np(n)
k−p(n)
nq(n)
k
Note also that p(n−1)
n−1=−q(n−1)
0=−∆nand this
will remains true at all iteration ending with p(0)
0=
−q(0)
0=−∆1.
If ∆n= 0 :
˜q(n)
0= 0
˜q(n)
k=p(n)
0q(n)
k−1−q(n)
0p(n)
k−1
k∈[1, n]
Note that the new ˜q(n)
1= 0.
In term of list manipulation we have (if ∆n= 0) :
pn−1=Drop[First[qn]pn−First[pn]qn,1]
qn−1=Drop[Last[qn]pn−Last[pn]qn,−1]
where First[list] and Last[list] takes 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 ∆n= 0
Received: April 27, 2022. Revised: October 28, 2022. Accepted: December 2, 2022. Published: December 31, 2022.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.99
Nardone Pasquale, Sonnino Giorgio
E-ISSN: 2224-2880
869
Volume 21, 2022
then we know that p(n)
0q(n)
n−q(n)
0p(n)
n= 0 so the list
p(n)
0qn−q(n)
0pnends with 0so the list manipulation
is :
˜qn=RotateRight[First[pn]qn−First[qn]pn]
where RotateRight[list] rotate the list to the right
(RotateRight[{a,b,c}]={c,a,b}).
So we have the same Bezout argument, the
gcd(Pn(x), Qn(x)) must divide Pn−1(x)and
Qn−1(x)or Pn(x)and ˜
Qn(x). Repeating ktimes the
iteration, it must divide Pn−k(x)and Qn−k(x).
If we reach a constant : P0(x) = p(0)
0and Q0(x) =
q(0)
0=−p(0)
0then gcd(Pn(x), Qn(x)) = 1. If we
reach, at some stage jof iteration, Pn−j(x)=0or
Qn−j(x) = 0 then the previous stage j−1contains
the gcd.
Repeating these steps decreases the degree of poly-
nomials. Reversing the process enables us to find
a combinations of Pn(x)and Qn(x)which gives a
monomial xkand the polynomials are co-prime, or
we reach a 0-polynomial before reaching the constant
and Pn(x),Qn(x)have a non trivial gcd.
2.1 Result
When dealing with numbers the recurrence could
gives large numbers so we can normalise the poly-
nomials by some constant
Pn−1(x) = αn−1
x(q(n)
0Pn(x)−p(n)
0Qn(x))
Qn(x) = βn−1(q(n)
nPn(x)−p(n)
nQn(x)) (3)
choosing for example αand βsuch that the sum
of absolute value of the coefficients of Pn−1(x)and
Qn−1(x)are 1:α−1
n−1=n−1
k=0 ∥p(n−1)
k∥,β−1
n−1=
n−1
k=0 ∥q(n−1)
k∥, or that the maximum of the coeffi-
cients is always 1:α−1
n−1=max(p(n−1)
k),β−1
n−1=
max(q(n−1)
k).
For example P8(x) = x8−4x6+ 4x5−29x4+
20x3+ 24x2+ 16x+ 48 and Q8(x) = x8+ 3x7−
7x4−21x3−6x2−18x, and let’s use the “max”
normalisation. The first iteration says that gcd must
divide P7(x)and Q7(x):
P7(x) = −1
21xQ8(x)and Q7(x) = 1
48(P8(x)−Q8(x))
P7(x) = −x7
21 −x6
7+x3
3+x2+2x
7+6
7and Q7(x) =
−x7
16 −x6
12 +x5
12 −11x4
24 +41x3
48 +5x2
8+17x
24 + 1, then
gcd divide
P6(x) = x6
78 −2x5
13 −2x4
13 +11x3
13 −67x2
78 +x−9
13
Q6(x) = x6
4+x5
5−11x4
10 +x3−33x2
20 +4x
5−3
10
then gcd divide
P5(x) = 22x5
57 +8x4
19 −31x3
19 +x2−115x
57 +11
19
Q5(x) = −32x5
187 −19x4
187 +155x3
187 −151x2
187 +x−12
17
etc.. finally gcd divide
P3(x) = x3+ 3x2+x+ 3
Q3(x) = x3
3+x2+x
3+ 1
the next step will give Q2(x) = 0
(3Q3(x)−P3(x) = 0), with the last step:
P2(x) = P8(x)88
63x4+50
63x3+229
378x2+143
378x−
Q8(x)−704
189x5−400
189x4+164
189x3−100
189x2+143
378x=
x3+ 3x2+x+ 3 and
Q2(x) = P8(x)−6
x3+x−1
x−
Q8(x)16
x4−8
x2+x+4
x−3= 0
so we have gcd(P8(x), Q8(x)) = x3+3x2+x+3
2.2 On formal polynomials
Doing the algorithm on formal polynomials gives au-
tomatically the resultant or the discriminant of Pn(x)
and Qn(x).
For example for the gcd of Pn(x)and Pn(x)′for
formal polynomials (we always cancel the term xm−1
by translation) we have:
P3(x) = x3+p x +q Q3(x) = P3(x)′= 3x2+p
gives after 3 iterations the well known discriminant
(4p3+ 27q2), and the Bezout expression is: p(9qx +
2p2)P3(x)−(3pqx2+(2p3+9q2)x+ 2p2q)Q3(x) =
−(4p3+ 27q2)x3and 3p(2px −3q)P3(x)−(px −
3q)(2px + 3q)Q3(x) = (4p3+ 27q2)x2
For the general polynomial of degree 4:
P4(x) = x4+p x2+q x+r Q4(x) = 4x3+2p x+q
in 5 iterations we have the discriminant is [3]
disc = 256r3−128p2r2+144pq2r−27q4+16p4r−4p3q2
A more formal case [3] is: Pm(x) = xm+a x +b
and Qm(x) = Pm(x)′=m xm−1+aapplying the
procedure gives then the discriminant [3]
mmbm−1+ (m−1)m−1am(4)
3 Conclusion
The algorithm developed here could be use for formal
or numerical calculation of the gcd of two polynomi-
als, or the discriminant and the resultant. It doesn’t
use matrix manipulation nor determinant calculations
and for polynomials of order n, it takes nsteps to
achieve the goal. It provide also the two polynomi-
als needed for Bezout identity.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.99
Nardone Pasquale, Sonnino Giorgio
E-ISSN: 2224-2880
870
Volume 21, 2022
References:
[1] Knuth, D.E. The Art of Computer Programming,
Vol. 2. Addison-Wesley, Reading, Mass., 1969
[2] W. S. Brown and J. F. Traub. 1971. On Eu-
clid’s Algorithm and the Theory of Subresul-
tants. J. ACM 18, 4 (Oct. 1971), 505-514.
DOI:https://doi.org/10.1145/321662.321665
[3] http://www2.math.uu.se/ svante/papers/sjN5.pdf
[4] Dario A. Bini and Paola Boito. 2007. Struc-
tured matrix-based methods for polynomial
ϵ-gcd: analysis and comparisons. In Proceed-
ings of the 2007 international symposium
on Symbolic and algebraic computation
(ISSAC ’07). Association for Computing
Machinery, New York, NY, USA, 9-16.
DOI:https://doi.org/10.1145/1277548.1277551
[5] Fazzi, A., Guglielmi, N., & Markovsky, I.
(2021). Generalized algorithms for the approx-
imate matrix polynomial GCD of reducing
data uncertainties with application to MIMO
system and control. Journal of Computational
and Applied Mathematics, 393, [113499].
https://doi.org/10.1016/j.cam.2021.113499
Contribution of individual authors to
the creation of a scientific article
(ghostwriting policy)
Pasquale Nardone and Giorgio Sonnino contributed
equally to the development of the algorithm.
Creative Commons Attribution
License 4.0 (Attribution 4.0
International , CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.99
Nardone Pasquale, Sonnino Giorgio
E-ISSN: 2224-2880
871
Volume 21, 2022
