An Iterative Algorithm for Determining the Greatest Common Divisor of Two or More Univariate Polynomials

Verica Milutinovic’
Faculty of Education, University of Kragujevac – Jagodina (Serbia)

https://doi.org/10.53656/math2024-4-3-ani

Abstract. The GCD problem in polynomial rings has long intrigued mathematicians for its diverse applications, leading to methods like the Euclidean algorithm, Routh array, and matrix-based approaches. Despite the
low costs of the Euclidean algorithm, it faces numerical instability, while matrix-based techniques, though stable, involve higher computational expenses. The goal of this paper is to introduce a novel approach to determining
the greatest common divisor (GCD) of multiple polynomials in a single variable, particularly suitable for interdisciplinary teaching in mathematics and programming. Our methodology involves iterating through the
entire set of polynomials directly, aiming to enhance the procedure’s efficiency while maintaining low computational costs. Numerous examples are provided to illustrate its practical application in teaching, ranging
from easy to challenging scenarios, as well as Python implementation of the given procedure.
Keywords: greatest common divisor, univariate polynomials, algorithm, Python program

Свързани статии:

On the Time Complexity of an Algorithm Шелинг – от логос към мит Компетентности и междупредметна интеграция при обучението по български език – възможности, перспективи и предизвикателства „Има ли Срба у Серезу“? Сръбското консулство в Сяр и Македонският въпрос на прага на ХХ век