A simple proof of the validity of the reduced prs algorithm
type: Item
instance of: scholarly article
title: A simple proof of the validity of the reduced prs algorithm
zbMATH Open document ID: 0638.13009
DOI: 10.1007/BF02278715
author: B. George
published in: Computing
publication date: 1987-01-01T00:00:00Z
review text: The author restricts the discussion to univariate polynomials with integer coefficients and to computations in \({\mathbb{Z}}[x]\) as a unique factorization domain. \({\mathbb{Z}}[x]\) is the set of all univariate polynomials with integer coefficients. The author presents a theorem by \textit{J. J. Sylvester} from 1853 [Philosophical Transactions 143, 407-548 (1853)] which indicates that the reduced polynomial remainder sequence algorithm (prs), as used only for normal prs's, is at least 133 year old. He modifies Sylvester's proof and obtains the following theorem: Let \(p_ 1(x),p_ 2(x),p_ 3(x),...,p_ n(x)\) be a normal polynomial remainder sequence, \(p_ i(x)\in {\mathbb{Z}}[x]\), for \(i=1,2,...,n\). Then: The square of the leading coefficient of \(p_ i(x)\) is a divisor of \(p_{i+2}(x)\).
Mathematics Subject Classification ID: 13B25
Mathematics Subject Classification ID: 65H05
zbMATH DE Number: 4040048
zbMATH Keywords: univariate polynomials
zbMATH Keywords: reduced polynomial remainder sequence algorithm
reviewed by: Vikramaditya Singh
MaRDI profile type: Publication
cites work: Subresultants and Reduced Polynomial Remainder Sequences
cites work: Q5585021
description: scientific article; zbMATH DE number 4040048