A simple proof of the validity of the reduced prs algorithm
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)\).
reduced polynomial remainder sequence algorithm
scientific article; zbMATH DE number 4040048