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

Copyright Licence

© 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 (x)   Q n (x) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaiaabccacaqGGaGaamyuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaaaa@4191@ :

P n (x)= k=0 n p k (n) x k ; Q n (x)= k=0 n q k (n) x k MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaiaai2dadaaeWbqabSqaaiaadUgacaaI9aGaaGimaaqaaiaad6gaa0GaeyyeIuoakiaadchadaqhaaWcbaGaam4AaaqaaiaaiIcacaWGUbGaaGykaaaakiaadIhadaahaaWcbeqaaiaadUgaaaGccaaMf8UaaG4oaiaaywW7caWGrbWaaSbaaSqaaiaad6gaaeqaaOGaaGikaiaadIhacaaIPaGaaGypamaaqahabeWcbaGaam4Aaiaai2dacaaIWaaabaGaamOBaaqdcqGHris5aOGaamyCamaaDaaaleaacaWGRbaabaGaaGikaiaad6gacaaIPaaaaOGaamiEamaaCaaaleqabaGaam4Aaaaaaaa@5E43@

with p 0 (n) 0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacaaIPaaaaOGaeyiyIKRaaGimaaaa@3E49@ and p n (n) 0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaWGUbaabaGaaGikaiaad6gacaaIPaaaaOGaeyiyIKRaaGimaaaa@3E82@ . The corresponding list of coefficients is:

p n ={ p 0 (n) , p 1 (n) ,, p n1 (n) , p n (n) };q n ={ q 0 (n) , q 1 (n) ,, q n1 (n) , q n (n) } MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGjcVlaaysW7caWGWbGaaGjcVpaaBaaaleaacaWGUbaabeaakiaai2dacaaI7bGaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacaaIPaaaaOGaaGilaiaadchadaqhaaWcbaGaaGymaaqaaiaaiIcacaWGUbGaaGykaaaakiaaiYcacqWIVlctcaaISaGaamiCamaaDaaaleaacaWGUbGaeyOeI0IaaGymaaqaaiaaiIcacaWGUbGaaGykaaaakiaaiYcacaWGWbWaa0baaSqaaiaad6gaaeaacaaIOaGaamOBaiaaiMcaaaGccaaI9bGaaGzbVlaaiUdacaaMf8UaaGjcVlaaysW7caWGXbGaaGjcVpaaBaaaleaacaWGUbaabeaakiaai2dacaaI7bGaamyCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacaaIPaaaaOGaaGilaiaadghadaqhaaWcbaGaaGymaaqaaiaaiIcacaWGUbGaaGykaaaakiaaiYcacqWIVlctcaaISaGaamyCamaaDaaaleaacaWGUbGaeyOeI0IaaGymaaqaaiaaiIcacaWGUbGaaGykaaaakiaaiYcacaWGXbWaa0baaSqaaiaad6gaaeaacaaIOaGaamOBaiaaiMcaaaGccaaI9baaaa@7E62@

Let's define Δ n = q n (n) p 0 (n) p n (n) q 0 (n) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeuiLdq0aaSbaaSqaaiaad6gaaeqaaOGaaGypaiaadghadaqhaaWcbaGaamOBaaqaaiaaiIcacaWGUbGaaGykaaaakiaadchadaqhaaWcbaGaaGimaaqaaiaaiIcacaWGUbGaaGykaaaakiabgkHiTiaadchadaqhaaWcbaGaamOBaaqaaiaaiIcacaWGUbGaaGykaaaakiaadghadaqhaaWcbaGaaGimaaqaaiaaiIcacaWGUbGaaGykaaaaaaa@4D2F@ . If Δ n 0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeuiLdq0aaSbaaSqaaiaad6gaaeqaaOGaeyiyIKRaaGimaaaa@3C9A@ , we can build two new polynomials of degree n-1 by canceling the lowest degree term and the highest degree term:

{ P n1 (x)=1/x( q 0 (n) P n (x) p 0 (n) Q n (x) ) Q n1 (x)= q n (n) P n (x) p n (n) Q n (x)       (1) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiqaaeaafaqaaeGacaaabaaabaGaamiuamaaBaaaleaacaWGUbGaeyOeI0IaaGymaaqabaGccaaIOaGaamiEaiaaiMcacaaI9aGaaGymaKqzaeGaai4laOGaamiEamaabmaabaGaamyCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacaaIPaaaaOGaamiuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaiabgkHiTiaadchadaqhaaWcbaGaaGimaaqaaiaaiIcacaWGUbGaaGykaaaakiaadgfadaWgaaWcbaGaamOBaaqabaGccaaIOaGaamiEaiaaiMcaaiaawIcacaGLPaaaaeaaaeaacaWGrbWaaSbaaSqaaiaad6gacqGHsislcaaIXaaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWGXbWaa0baaSqaaiaad6gaaeaacaaIOaGaamOBaiaaiMcaaaGccaWGqbWaaSbaaSqaaiaad6gaaeqaaOGaaGikaiaadIhacaaIPaGaeyOeI0IaamiCamaaDaaaleaacaWGUbaabaGaaGikaiaad6gacaaIPaaaaOGaamyuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaaaaaiaawUhaaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabIcacaqGXaGaaeykaaaa@7564@

If Δ n =0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeuiLdq0aaSbaaSqaaiaad6gaaeqaaOGaaGypaiaaicdaaaa@3B9A@ then we replace Q n (x) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaaaa@3BEB@ it by Q ˜ n (x) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGabmyuayaaiaWaaSbaaSqaaiaad6gaaeqaaOGaaGikaiaadIhacaaIPaaaaa@3BFA@ :

{ P n (x)= P n (x) Q ˜ n (x)=x( p 0 (n) Q n (x) q 0 (n) P n (x))      (2) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiqaaeaafaqaaeGacaaabaaabaGaamiuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWGqbWaaSbaaSqaaiaad6gaaeqaaOGaaGikaiaadIhacaaIPaaabaaabaGabmyuayaaiaWaaSbaaSqaaiaad6gaaeqaaOGaaGikaiaadIhacaaIPaGaaGypaiaadIhacaaIOaGaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacaaIPaaaaOGaamyuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaiabgkHiTiaadghadaqhaaWcbaGaaGimaaqaaiaaiIcacaWGUbGaaGykaaaakiaadcfadaWgaaWcbaGaamOBaaqabaGccaaIOaGaamiEaiaaiMcacaaIPaaaaaGaay5EaaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGOaGaaeOmaiaabMcaaaa@6139@

This corresponds to the manipulation on the list of coefficients:

if Δ n 0{ p k (n1) = q 0 (n) p k+1 (n) p 0 (n) q k+1 (n) q k (n1) = q n (n) p k (n) p n (n) q k (n) k[0,n1]     (3) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaeyAaiaabAgacaaMe8UaeuiLdq0aaSbaaSqaaiaad6gaaeqaaOGaeyiyIKRaaGimaiaaywW7daGabaqaauaabeqadeaaaeaacaWGWbWaa0baaSqaaiaadUgaaeaacaaIOaGaamOBaiabgkHiTiaaigdacaaIPaaaaOGaaGypaiaadghadaqhaaWcbaGaaGimaaqaaiaaiIcacaWGUbGaaGykaaaakiaadchadaqhaaWcbaGaam4AaiabgUcaRiaaigdaaeaacaaIOaGaamOBaiaaiMcaaaGccqGHsislcaWGWbWaa0baaSqaaiaaicdaaeaacaaIOaGaamOBaiaaiMcaaaGccaWGXbWaa0baaSqaaiaadUgacqGHRaWkcaaIXaaabaGaaGikaiaad6gacaaIPaaaaaGcbaaabaGaamyCamaaDaaaleaacaWGRbaabaGaaGikaiaad6gacqGHsislcaaIXaGaaGykaaaakiaai2dacaWGXbWaa0baaSqaaiaad6gaaeaacaaIOaGaamOBaiaaiMcaaaGccaWGWbWaa0baaSqaaiaadUgaaeaacaaIOaGaamOBaiaaiMcaaaGccqGHsislcaWGWbWaa0baaSqaaiaad6gaaeaacaaIOaGaamOBaiaaiMcaaaGccaWGXbWaa0baaSqaaiaadUgaaeaacaaIOaGaamOBaiaaiMcaaaaaaaGccaGL7baacaaMf8Uaam4AaiabgIGiolaaiUfacaaIWaGaaGilaiaad6gacqGHsislcaaIXaGaaGyxaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeikaiaabodacaqGPaaaaa@87E1@

Note also that p n1 (n1) = q 0 (n1) = Δ n MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaWGUbGaeyOeI0IaaGymaaqaaiaaiIcacaWGUbGaeyOeI0IaaGymaiaaiMcaaaGccaaI9aGaeyOeI0IaamyCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacqGHsislcaaIXaGaaGykaaaakiaai2dacqGHsislcqqHuoardaWgaaWcbaGaamOBaaqabaaaaa@4B25@ this will remains true at all iterations ending with p 0 (0) = q 0 (0) = Δ 1 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaaicdacaaIPaaaaOGaaGypaiabgkHiTiaadghadaqhaaWcbaGaaGimaaqaaiaaiIcacaaIWaGaaGykaaaakiaai2dacqGHsislcqqHuoardaWgaaWcbaGaaGymaaqabaaaaa@454A@ .

if Δ n =0{ q ˜ 0 (n) =0 q ˜ k (n) = p 0 (n) q k1 (n) q 0 (n) p k1 (n) k[1,n]     (4) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaeyAaiaabAgacaaMe8UaeuiLdq0aaSbaaSqaaiaad6gaaeqaaOGaaGypaiaaicdacaaMf8+aaiqaaeaafaqabeGabaaabaGabmyCayaaiaWaa0baaSqaaiaaicdaaeaacaaIOaGaamOBaiaaiMcaaaGccaaI9aGaaGimaaqaaiqadghagaacamaaDaaaleaacaWGRbaabaGaaGikaiaad6gacaaIPaaaaOGaaGypaiaadchadaqhaaWcbaGaaGimaaqaaiaaiIcacaWGUbGaaGykaaaakiaadghadaqhaaWcbaGaam4AaiabgkHiTiaaigdaaeaacaaIOaGaamOBaiaaiMcaaaGccqGHsislcaWGXbWaa0baaSqaaiaaicdaaeaacaaIOaGaamOBaiaaiMcaaaGccaWGWbWaa0baaSqaaiaadUgacqGHsislcaaIXaaabaGaaGikaiaad6gacaaIPaaaaaaaaOGaay5EaaGaaGzbVlaadUgacqGHiiIZcaaIBbGaaGymaiaaiYcacaWGUbGaaGyxaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeikaiaabsdacaqGPaaaaa@6FDD@

Note that the new q ˜ 1 (n) =0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGabmyCayaaiaWaa0baaSqaaiaaigdaaeaacaaIOaGaamOBaiaaiMcaaaGccaaI9aGaaGimaaaa@3D5A@ .

In terms of list manipulation we have:

if Δ n 0 p n1 =Drop[First[q n ]p n First[p n ]q n ,1] q n1 =Drop[Last[q n ]p n Last[p n ]q n ,1] MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaeyAaiaabAgacaaMe8UaeuiLdq0aaSbaaSqaaiaad6gaaeqaaOGaeyiyIKRaaGimaiaaywW7faqabeGabaaabaGaaGjcVlaaysW7caWGWbGaaGjcVpaaBaaaleaacaWGUbGaeyOeI0IaaGymaaqabaGccaaI9aGaamiraiaadkhacaWGVbGaamiCaiaaiUfacaWGgbGaamyAaiaadkhacaWGZbGaamiDaiaaiUfacaaMi8UaaGjbVlaadghacaaMi8+aaSbaaSqaaiaad6gaaeqaaOGaaGyxaiaaysW7caaMi8UaaGjbVlaadchacaaMi8+aaSbaaSqaaiaad6gaaeqaaOGaeyOeI0IaamOraiaadMgacaWGYbGaam4CaiaadshacaaIBbGaaGjcVlaaysW7caWGWbGaaGjcVpaaBaaaleaacaWGUbaabeaakiaai2facaaMe8UaaGjcVlaaysW7caWGXbGaaGjcVpaaBaaaleaacaWGUbaabeaakiaaiYcacaaIXaGaaGyxaaqaaiaayIW7caaMe8UaamyCaiaayIW7daWgaaWcbaGaamOBaiabgkHiTiaaigdaaeqaaOGaaGypaiaadseacaWGYbGaam4BaiaadchacaaIBbGaamitaiaadggacaWGZbGaamiDaiaaiUfacaaMi8UaaGjbVlaadghacaaMi8+aaSbaaSqaaiaad6gaaeqaaOGaaGyxaiaaysW7caaMi8UaaGjbVlaadchacaaMi8+aaSbaaSqaaiaad6gaaeqaaOGaeyOeI0IaamitaiaadggacaWGZbGaamiDaiaaiUfacaaMi8UaaGjbVlaadchacaaMi8+aaSbaaSqaaiaad6gaaeqaaOGaaGyxaiaaysW7caaMi8UaaGjbVlaadghacaaMi8+aaSbaaSqaaiaad6gaaeqaaOGaaGilaiabgkHiTiaaigdacaaIDbaaaaaa@B905@

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 Δ n =0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeuiLdq0aaSbaaSqaaiaad6gaaeqaaOGaaGypaiaaicdaaaa@3B9A@ then we know that p 0 (n) q n (n) q 0 (n) p n (n) =0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacaaIPaaaaOGaamyCamaaDaaaleaacaWGUbaabaGaaGikaiaad6gacaaIPaaaaOGaeyOeI0IaamyCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacaaIPaaaaOGaamiCamaaDaaaleaacaWGUbaabaGaaGikaiaad6gacaaIPaaaaOGaaGypaiaaicdaaaa@4B64@ so the list p 0 (n) q n q 0 (n) p n MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacaaIPaaaaOGaaGjcVlaaysW7caWGXbGaaGjcVpaaBaaaleaacaWGUbaabeaakiabgkHiTiaadghadaqhaaWcbaGaaGimaaqaaiaaiIcacaWGUbGaaGykaaaakiaayIW7caaMe8UaamiCaiaayIW7daWgaaWcbaGaamOBaaqabaaaaa@4E85@ ends with 0 so the list manipulation is :

q ˜ n =RotateRight[First[p n ]q n First[q n ]p n ] MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGabmyCayaaiaWaaSbaaSqaaiaad6gaaeqaaOGaaGypaiaadkfacaWGVbGaamiDaiaadggacaWG0bGaamyzaiaadkfacaWGPbGaam4zaiaadIgacaWG0bGaaG4waiaadAeacaWGPbGaamOCaiaadohacaWG0bGaaG4waiaayIW7caaMe8UaamiCaiaayIW7daWgaaWcbaGaamOBaaqabaGccaaIDbGaaGjcVlaaysW7caWGXbGaaGjcVpaaBaaaleaacaWGUbaabeaakiabgkHiTiaadAeacaWGPbGaamOCaiaadohacaWG0bGaaG4waiaayIW7caaMe8UaamyCaiaayIW7daWgaaWcbaGaamOBaaqabaGccaaIDbGaaGjcVlaaysW7caWGWbGaaGjcVpaaBaaaleaacaWGUbaabeaakiaai2faaaa@6F6C@

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 (x)= p 0 (0) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaBaaaleaacaaIWaaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWGWbWaa0baaSqaaiaaicdaaeaacaaIOaGaaGimaiaaiMcaaaaaaa@4073@ and Q 0 (x)= q 0 (0) = p 0 (0) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyuamaaBaaaleaacaaIWaaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWGXbWaa0baaSqaaiaaicdaaeaacaaIOaGaaGimaiaaiMcaaaGccaaI9aGaeyOeI0IaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaaicdacaaIPaaaaaaa@462E@ then gcd( P n (x), Q n (x))=1 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4zaiaadogacaWGKbGaaGikaiaadcfadaWgaaWcbaGaamOBaaqabaGccaaIOaGaamiEaiaaiMcacaaISaGaamyuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaiaaiMcacaaI9aGaaGymaaaa@46A5@ . If we reach, some stage j of iteration, P nj (x)=0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaBaaaleaacaWGUbGaeyOeI0IaamOAaaqabaGccaaIOaGaamiEaiaaiMcacaaI9aGaaGimaaaa@3F47@ or Q nj (x)=0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyuamaaBaaaleaacaWGUbGaeyOeI0IaamOAaaqabaGccaaIOaGaamiEaiaaiMcacaaI9aGaaGimaaaa@3F48@ 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

P n1 (x)= α n1 x( q 0 (n) P n (x) p 0 (n) Q n (x) ) Q n (x)= β n1 ( q n (n) P n (x) p n (n) Q n (x) )        (5) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabiGaaaqaaaqaaiaadcfadaWgaaWcbaGaamOBaiabgkHiTiaaigdaaeqaaOGaaGikaiaadIhacaaIPaGaaGypaiabeg7aHnaaBaaaleaacaWGUbGaeyOeI0IaaGymaaqabaGccaWG4bWaaeWaaeaacaWGXbWaa0baaSqaaiaaicdaaeaacaaIOaGaamOBaiaaiMcaaaGccaWGqbWaaSbaaSqaaiaad6gaaeqaaOGaaGikaiaadIhacaaIPaGaeyOeI0IaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaad6gacaaIPaaaaOGaamyuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaaGaayjkaiaawMcaaaqaaaqaaiaadgfadaWgaaWcbaGaamOBaaqabaGccaaIOaGaamiEaiaaiMcacaaI9aGaeqOSdi2aaSbaaSqaaiaad6gacqGHsislcaaIXaaabeaakmaabmaabaGaamyCamaaDaaaleaacaWGUbaabaGaaGikaiaad6gacaaIPaaaaOGaamiuamaaBaaaleaacaWGUbaabeaakiaaiIcacaWG4bGaaGykaiabgkHiTiaadchadaqhaaWcbaGaamOBaaqaaiaaiIcacaWGUbGaaGykaaaakiaadgfadaWgaaWcbaGaamOBaaqabaGccaaIOaGaamiEaiaaiMcaaiaawIcacaGLPaaaaaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabIcacaqG1aGaaeykaaaa@7BCD@

Choosing for example α and β such that the sum of the absolute value of the coefficients of Pn-1 (x) and Qn-1 (x) are : α n1 1 = k=0 n1 p k (n1) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqySde2aa0baaSqaaiaad6gacqGHsislcaaIXaaabaGaeyOeI0IaaGymaaaakiaai2dadaaeWaqabSqaaiaadUgacaaI9aGaaGimaaqaaiaad6gacqGHsislcaaIXaaaniabggHiLdqeeuuDJXwAKbsr4rNCHbacfaGccqWFLicucaWGWbWaa0baaSqaaiaadUgaaeaacaaIOaGaamOBaiabgkHiTiaaigdacaaIPaaaaOGae8xjIafaaa@5273@ , β n1 1 = k=0 n1 q k (n1) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqOSdi2aa0baaSqaaiaad6gacqGHsislcaaIXaaabaGaeyOeI0IaaGymaaaakiaai2dadaaeWaqabSqaaiaadUgacaaI9aGaaGimaaqaaiaad6gacqGHsislcaaIXaaaniabggHiLdqeeuuDJXwAKbsr4rNCHbacfaGccqWFLicucaWGXbWaa0baaSqaaiaadUgaaeaacaaIOaGaamOBaiabgkHiTiaaigdacaaIPaaaaOGae8xjIafaaa@5276@ , or that the maximum of the coefficients is always : α n1 1 =max( p k (n1) ) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqySde2aa0baaSqaaiaad6gacqGHsislcaaIXaaabaGaeyOeI0IaaGymaaaakiaai2dacaWGTbGaamyyaiaadIhacaaIOaGaamiCamaaDaaaleaacaWGRbaabaGaaGikaiaad6gacqGHsislcaaIXaGaaGykaaaakiaaiMcaaaa@48C0@ , β n1 1 =max( q k (n1) ) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqOSdi2aa0baaSqaaiaad6gacqGHsislcaaIXaaabaGaeyOeI0IaaGymaaaakiaai2dacaWGTbGaamyyaiaadIhacaaIOaGaamyCamaaDaaaleaacaWGRbaabaGaaGikaiaad6gacqGHsislcaaIXaGaaGykaaaakiaaiMcaaaa@48C3@ .

For example

{ P 8 (x)= x 8 4 x 6 +4 x 5 29 x 4 +20 x 3 +24 x 2 +16x+48 Q 8 (x)= x 8 +3 x 7 7 x 4 21 x 3 6 x 2 18x { p 8 ={48,16,24,20,29,4,4,0,1} q 8 ={0,18,6,21,7,0,0,3,1}        (6) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabiGaaaqaaaqaamaaceaabaqbaeaabiGaaaqaaaqaaiaadcfadaWgaaWcbaGaaGioaaqabaGccaaIOaGaamiEaiaaiMcacaaI9aGaamiEamaaCaaaleqabaGaaGioaaaakiabgkHiTiaaisdacaWG4bWaaWbaaSqabeaacaaI2aaaaOGaey4kaSIaaGinaiaadIhadaahaaWcbeqaaiaaiwdaaaGccqGHsislcaaIYaGaaGyoaiaadIhadaahaaWcbeqaaiaaisdaaaGccqGHRaWkcaaIYaGaaGimaiaadIhadaahaaWcbeqaaiaaiodaaaGccqGHRaWkcaaIYaGaaGinaiaadIhadaahaaWcbeqaaiaaikdaaaGccqGHRaWkcaaIXaGaaGOnaiaadIhacqGHRaWkcaaI0aGaaGioaaqaaaqaaiaadgfadaWgaaWcbaGaaGioaaqabaGccaaIOaGaamiEaiaaiMcacaaI9aGaamiEamaaCaaaleqabaGaaGioaaaakiabgUcaRiaaiodacaWG4bWaaWbaaSqabeaacaaI3aaaaOGaeyOeI0IaaG4naiaadIhadaahaaWcbeqaaiaaisdaaaGccqGHsislcaaIYaGaaGymaiaadIhadaahaaWcbeqaaiaaiodaaaGccqGHsislcaaI2aGaamiEamaaCaaaleqabaGaaGOmaaaakiabgkHiTiaaigdacaaI4aGaamiEaaaaaiaawUhaaaqaaaqaamaaceaabaqbaeaabiGaaaqaaaqaaiaayIW7caaMe8UaamiCaiaayIW7daWgaaWcbaGaaGioaaqabaGccaaI9aGaaG4EaiaaisdacaaI4aGaaGilaiaaigdacaaI2aGaaGilaiaaikdacaaI0aGaaGilaiaaikdacaaIWaGaaGilaiabgkHiTiaaikdacaaI5aGaaGilaiaaisdacaaISaGaeyOeI0IaaGinaiaaiYcacaaIWaGaaGilaiaaigdacaaI9baabaaabaGaaGjcVlaaysW7caWGXbGaaGjcVpaaBaaaleaacaaI4aaabeaakiaai2dacaaI7bGaaGimaiaaiYcacqGHsislcaaIXaGaaGioaiaaiYcacqGHsislcaaI2aGaaGilaiabgkHiTiaaikdacaaIXaGaaGilaiabgkHiTiaaiEdacaaISaGaaGimaiaaiYcacaaIWaGaaGilaiaaiodacaaISaGaaGymaiaai2haaaaacaGL7baaaaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabIcacaqG2aGaaeykaaaa@B0FA@

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

P 7 (x)=121x Q 8 (x)and Q 7 (x)=148( P 8 (x) Q 8 (x)) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaBaaaleaacaaI3aaabeaakiaaiIcacaWG4bGaaGykaiaai2dacqGHsislcaaIXaGaaGOmaiaaigdacaWG4bGaamyuamaaBaaaleaacaaI4aaabeaakiaaiIcacaWG4bGaaGykaiaaysW7caqGHbGaaeOBaiaabsgacaaMe8UaamyuamaaBaaaleaacaaI3aaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaaIXaGaaGinaiaaiIdacaaIOaGaamiuamaaBaaaleaacaaI4aaabeaakiaaiIcacaWG4bGaaGykaiabgkHiTiaadgfadaWgaaWcbaGaaGioaaqabaGccaaIOaGaamiEaiaaiMcacaaIPaaaaa@5C83@

{ P 7 (x)= x 7 21 x 6 7 + x 3 3 + x 2 + 2x 7 + 6 7 Q 7 (x)= x 7 16 x 6 12 + x 5 12 11 x 4 24 + 41 x 3 48 + 5 x 2 8 + 17x 24 +1 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiqaaeaafaqaaeGacaaabaaabaGaamiuamaaBaaaleaacaaI3aaabeaakiaaiIcacaWG4bGaaGykaiaai2dacqGHsisldaWcaaqaaiaadIhadaahaaWcbeqaaiaaiEdaaaaakeaacaaIYaGaaGymaaaacqGHsisldaWcaaqaaiaadIhadaahaaWcbeqaaiaaiAdaaaaakeaacaaI3aaaaiabgUcaRmaalaaabaGaamiEamaaCaaaleqabaGaaG4maaaaaOqaaiaaiodaaaGaey4kaSIaamiEamaaCaaaleqabaGaaGOmaaaakiabgUcaRmaalaaabaGaaGOmaiaadIhaaeaacaaI3aaaaiabgUcaRmaalaaabaGaaGOnaaqaaiaaiEdaaaaabaaabaGaamyuamaaBaaaleaacaaI3aaabeaakiaaiIcacaWG4bGaaGykaiaai2dacqGHsisldaWcaaqaaiaadIhadaahaaWcbeqaaiaaiEdaaaaakeaacaaIXaGaaGOnaaaacqGHsisldaWcaaqaaiaadIhadaahaaWcbeqaaiaaiAdaaaaakeaacaaIXaGaaGOmaaaacqGHRaWkdaWcaaqaaiaadIhadaahaaWcbeqaaiaaiwdaaaaakeaacaaIXaGaaGOmaaaacqGHsisldaWcaaqaaiaaigdacaaIXaGaamiEamaaCaaaleqabaGaaGinaaaaaOqaaiaaikdacaaI0aaaaiabgUcaRmaalaaabaGaaGinaiaaigdacaWG4bWaaWbaaSqabeaacaaIZaaaaaGcbaGaaGinaiaaiIdaaaGaey4kaSYaaSaaaeaacaaI1aGaamiEamaaCaaaleqabaGaaGOmaaaaaOqaaiaaiIdaaaGaey4kaSYaaSaaaeaacaaIXaGaaG4naiaadIhaaeaacaaIYaGaaGinaaaacqGHRaWkcaaIXaaaaaGaay5Eaaaaaa@7ADB@

then gcd divide

{ P 6 (x)= x 6 78 2 x 5 13 2 x 4 13 + 11 x 3 13 67 x 2 78 +x 9 13 Q 6 (x)= x 6 4 + x 5 5 11 x 4 10 + x 3 33 x 2 20 + 4x 5 3 10 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiqaaeaafaqaaeGacaaabaaabaGaamiuamaaBaaaleaacaaI2aaabeaakiaaiIcacaWG4bGaaGykaiaai2dadaWcaaqaaiaadIhadaahaaWcbeqaaiaaiAdaaaaakeaacaaI3aGaaGioaaaacqGHsisldaWcaaqaaiaaikdacaWG4bWaaWbaaSqabeaacaaI1aaaaaGcbaGaaGymaiaaiodaaaGaeyOeI0YaaSaaaeaacaaIYaGaamiEamaaCaaaleqabaGaaGinaaaaaOqaaiaaigdacaaIZaaaaiabgUcaRmaalaaabaGaaGymaiaaigdacaWG4bWaaWbaaSqabeaacaaIZaaaaaGcbaGaaGymaiaaiodaaaGaeyOeI0YaaSaaaeaacaaI2aGaaG4naiaadIhadaahaaWcbeqaaiaaikdaaaaakeaacaaI3aGaaGioaaaacqGHRaWkcaWG4bGaeyOeI0YaaSaaaeaacaaI5aaabaGaaGymaiaaiodaaaaabaaabaGaamyuamaaBaaaleaacaaI2aaabeaakiaaiIcacaWG4bGaaGykaiaai2dadaWcaaqaaiaadIhadaahaaWcbeqaaiaaiAdaaaaakeaacaaI0aaaaiabgUcaRmaalaaabaGaamiEamaaCaaaleqabaGaaGynaaaaaOqaaiaaiwdaaaGaeyOeI0YaaSaaaeaacaaIXaGaaGymaiaadIhadaahaaWcbeqaaiaaisdaaaaakeaacaaIXaGaaGimaaaacqGHRaWkcaWG4bWaaWbaaSqabeaacaaIZaaaaOGaeyOeI0YaaSaaaeaacaaIZaGaaG4maiaadIhadaahaaWcbeqaaiaaikdaaaaakeaacaaIYaGaaGimaaaacqGHRaWkdaWcaaqaaiaaisdacaWG4baabaGaaGynaaaacqGHsisldaWcaaqaaiaaiodaaeaacaaIXaGaaGimaaaaaaaacaGL7baaaaa@7CCE@

then gcd divide

{ P 5 (x)= 22 x 5 57 + 8 x 4 19 31 x 3 19 + x 2 115x 57 + 11 19 Q 5 (x)= 32 x 5 187 19 x 4 187 + 155 x 3 187 151 x 2 187 +x 12 17 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiqaaeaafaqaaeGacaaabaaabaGaamiuamaaBaaaleaacaaI1aaabeaakiaaiIcacaWG4bGaaGykaiaai2dadaWcaaqaaiaaikdacaaIYaGaamiEamaaCaaaleqabaGaaGynaaaaaOqaaiaaiwdacaaI3aaaaiabgUcaRmaalaaabaGaaGioaiaadIhadaahaaWcbeqaaiaaisdaaaaakeaacaaIXaGaaGyoaaaacqGHsisldaWcaaqaaiaaiodacaaIXaGaamiEamaaCaaaleqabaGaaG4maaaaaOqaaiaaigdacaaI5aaaaiabgUcaRiaadIhadaahaaWcbeqaaiaaikdaaaGccqGHsisldaWcaaqaaiaaigdacaaIXaGaaGynaiaadIhaaeaacaaI1aGaaG4naaaacqGHRaWkdaWcaaqaaiaaigdacaaIXaaabaGaaGymaiaaiMdaaaaabaaabaGaamyuamaaBaaaleaacaaI1aaabeaakiaaiIcacaWG4bGaaGykaiaai2dacqGHsisldaWcaaqaaiaaiodacaaIYaGaamiEamaaCaaaleqabaGaaGynaaaaaOqaaiaaigdacaaI4aGaaG4naaaacqGHsisldaWcaaqaaiaaigdacaaI5aGaamiEamaaCaaaleqabaGaaGinaaaaaOqaaiaaigdacaaI4aGaaG4naaaacqGHRaWkdaWcaaqaaiaaigdacaaI1aGaaGynaiaadIhadaahaaWcbeqaaiaaiodaaaaakeaacaaIXaGaaGioaiaaiEdaaaGaeyOeI0YaaSaaaeaacaaIXaGaaGynaiaaigdacaWG4bWaaWbaaSqabeaacaaIYaaaaaGcbaGaaGymaiaaiIdacaaI3aaaaiabgUcaRiaadIhacqGHsisldaWcaaqaaiaaigdacaaIYaaabaGaaGymaiaaiEdaaaaaaaGaay5Eaaaaaa@80DF@

etc.. finally gcd divide

{ P 3 (x)= x 3 +3 x 2 +x+3 Q 3 (x)= x 3 3 + x 2 + x 3 +1 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiqaaeaafaqaaeGacaaabaaabaGaamiuamaaBaaaleaacaaIZaaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWG4bWaaWbaaSqabeaacaaIZaaaaOGaey4kaSIaaG4maiaadIhadaahaaWcbeqaaiaaikdaaaGccqGHRaWkcaWG4bGaey4kaSIaaG4maaqaaaqaaiaadgfadaWgaaWcbaGaaG4maaqabaGccaaIOaGaamiEaiaaiMcacaaI9aWaaSaaaeaacaWG4bWaaWbaaSqabeaacaaIZaaaaaGcbaGaaG4maaaacqGHRaWkcaWG4bWaaWbaaSqabeaacaaIYaaaaOGaey4kaSYaaSaaaeaacaWG4baabaGaaG4maaaacqGHRaWkcaaIXaaaaaGaay5Eaaaaaa@556D@

the next step will give Q 2 (x)=0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyuamaaBaaaleaacaaIYaaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaaIWaaaaa@3D35@ ( 3 Q 3 (x) P 3 (x)=0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaG4maiaadgfadaWgaaWcbaGaaG4maaqabaGccaaIOaGaamiEaiaaiMcacqGHsislcaWGqbWaaSbaaSqaaiaaiodaaeqaaOGaaGikaiaadIhacaaIPaGaaGypaiaaicdaaaa@430A@ ), with the last step:

{ P 2 (x)= P 8 (x)( 88 63 x 4 + 50 63 x 3 + 229 378 x 2 + 143 378x )+ Q 8 (x)( 704 189 x 5 400 189 x 4 + 164 189 x 3 100 189 x 2 + 143 378x )= x 3 +3 x 2 +x+3 Q 2 (x)= P 8 (x)( 6 x 3 +x 1 x ) Q 8 (x)( 16 x 4 8 x 2 +x+ 4 x 3 )=0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiqaaeaafaqaaeWacaaabaaabaGaamiuamaaBaaaleaacaaIYaaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWGqbWaaSbaaSqaaiaaiIdaaeqaaOGaaGikaiaadIhacaaIPaWaaeWaaeaadaWcaaqaaiaaiIdacaaI4aaabaGaaGOnaiaaiodacaWG4bWaaWbaaSqabeaacaaI0aaaaaaakiabgUcaRmaalaaabaGaaGynaiaaicdaaeaacaaI2aGaaG4maiaadIhadaahaaWcbeqaaiaaiodaaaaaaOGaey4kaSYaaSaaaeaacaaIYaGaaGOmaiaaiMdaaeaacaaIZaGaaG4naiaaiIdacaWG4bWaaWbaaSqabeaacaaIYaaaaaaakiabgUcaRmaalaaabaGaaGymaiaaisdacaaIZaaabaGaaG4maiaaiEdacaaI4aGaamiEaaaaaiaawIcacaGLPaaacqGHRaWkaeaaaeaacqGHsislcaWGrbWaaSbaaSqaaiaaiIdaaeqaaOGaaGikaiaadIhacaaIPaWaaeWaaeaacqGHsisldaWcaaqaaiaaiEdacaaIWaGaaGinaaqaaiaaigdacaaI4aGaaGyoaiaadIhadaahaaWcbeqaaiaaiwdaaaaaaOGaeyOeI0YaaSaaaeaacaaI0aGaaGimaiaaicdaaeaacaaIXaGaaGioaiaaiMdacaWG4bWaaWbaaSqabeaacaaI0aaaaaaakiabgUcaRmaalaaabaGaaGymaiaaiAdacaaI0aaabaGaaGymaiaaiIdacaaI5aGaamiEamaaCaaaleqabaGaaG4maaaaaaGccqGHsisldaWcaaqaaiaaigdacaaIWaGaaGimaaqaaiaaigdacaaI4aGaaGyoaiaadIhadaahaaWcbeqaaiaaikdaaaaaaOGaey4kaSYaaSaaaeaacaaIXaGaaGinaiaaiodaaeaacaaIZaGaaG4naiaaiIdacaWG4baaaaGaayjkaiaawMcaaiaai2dacaWG4bWaaWbaaSqabeaacaaIZaaaaOGaey4kaSIaaG4maiaadIhadaahaaWcbeqaaiaaikdaaaGccqGHRaWkcaWG4bGaey4kaSIaaG4maaqaaaqaaiaadgfadaWgaaWcbaGaaGOmaaqabaGccaaIOaGaamiEaiaaiMcacaaI9aGaamiuamaaBaaaleaacaaI4aaabeaakiaaiIcacaWG4bGaaGykamaabmaabaGaeyOeI0YaaSaaaeaacaaI2aaabaGaamiEamaaCaaaleqabaGaaG4maaaaaaGccqGHRaWkcaWG4bGaeyOeI0YaaSaaaeaacaaIXaaabaGaamiEaaaaaiaawIcacaGLPaaacqGHsislcaWGrbWaaSbaaSqaaiaaiIdaaeqaaOGaaGikaiaadIhacaaIPaWaaeWaaeaadaWcaaqaaiaaigdacaaI2aaabaGaamiEamaaCaaaleqabaGaaGinaaaaaaGccqGHsisldaWcaaqaaiaaiIdaaeaacaWG4bWaaWbaaSqabeaacaaIYaaaaaaakiabgUcaRiaadIhacqGHRaWkdaWcaaqaaiaaisdaaeaacaWG4baaaiabgkHiTiaaiodaaiaawIcacaGLPaaacaaI9aGaaGimaaaaaiaawUhaaaaa@B9A4@

so we have gcd( P 8 (x), Q 8 (x))= x 3 +3 x 2 +x+3 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4zaiaadogacaWGKbGaaGikaiaadcfadaWgaaWcbaGaaGioaaqabaGccaaIOaGaamiEaiaaiMcacaaISaGaamyuamaaBaaaleaacaaI4aaabeaakiaaiIcacaWG4bGaaGykaiaaiMcacaaI9aGaamiEamaaCaaaleqabaGaaG4maaaakiabgUcaRiaaiodacaWG4bWaaWbaaSqabeaacaaIYaaaaOGaey4kaSIaamiEaiabgUcaRiaaiodaaaa@4E86@

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 (x)= x 3 +px+q Q 3 (x)= P 3 (x ) =3 x 2 +p MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaBaaaleaacaaIZaaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWG4bWaaWbaaSqabeaacaaIZaaaaOGaey4kaSIaamiCaiaaysW7caWG4bGaey4kaSIaamyCaiaaywW7caWGrbWaaSbaaSqaaiaaiodaaeqaaOGaaGikaiaadIhacaaIPaGaaGypaiaadcfadaWgaaWcbaGaaG4maaqabaGccaaIOaGaamiEaiqaiMcagaqbaiaai2dacaaIZaGaamiEamaaCaaaleqabaGaaGOmaaaakiabgUcaRiaadchaaaa@54A6@

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

p(9qx+2 p 2 ) P 3 (x)(3pq x 2 +(2 p 3 +9 q 2 )x+2 p 2 q) Q 3 (x)=(4 p 3 +27 q 2 ) x 3 3p(2px3q) P 3 (x)(px3q)(2px+3q) Q 3 (x)=(4 p 3 +27 q 2 ) x 2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabiGaaaqaaaqaaiaadchacaaIOaGaaGyoaiaadghacaWG4bGaey4kaSIaaGOmaiaadchadaahaaWcbeqaaiaaikdaaaGccaaIPaGaamiuamaaBaaaleaacaaIZaaabeaakiaaiIcacaWG4bGaaGykaiabgkHiTiaaiIcacaaIZaGaamiCaiaadghacaWG4bWaaWbaaSqabeaacaaIYaaaaOGaey4kaSIaaGikaiaaikdacaWGWbWaaWbaaSqabeaacaaIZaaaaOGaey4kaSIaaGyoaiaadghadaahaaWcbeqaaiaaikdaaaGccaaIPaGaamiEaiabgUcaRiaaikdacaWGWbWaaWbaaSqabeaacaaIYaaaaOGaamyCaiaaiMcacaWGrbWaaSbaaSqaaiaaiodaaeqaaOGaaGikaiaadIhacaaIPaGaaGypaiabgkHiTiaaiIcacaaI0aGaamiCamaaCaaaleqabaGaaG4maaaakiabgUcaRiaaikdacaaI3aGaamyCamaaCaaaleqabaGaaGOmaaaakiaaiMcacaWG4bWaaWbaaSqabeaacaaIZaaaaaGcbaaabaGaaG4maiaadchacaaIOaGaaGOmaiaadchacaWG4bGaeyOeI0IaaG4maiaadghacaaIPaGaamiuamaaBaaaleaacaaIZaaabeaakiaaiIcacaWG4bGaaGykaiabgkHiTiaaiIcacaWGWbGaamiEaiabgkHiTiaaiodacaWGXbGaaGykaiaaiIcacaaIYaGaamiCaiaadIhacqGHRaWkcaaIZaGaamyCaiaaiMcacaWGrbWaaSbaaSqaaiaaiodaaeqaaOGaaGikaiaadIhacaaIPaGaaGypaiaaiIcacaaI0aGaamiCamaaCaaaleqabaGaaG4maaaakiabgUcaRiaaikdacaaI3aGaamyCamaaCaaaleqabaGaaGOmaaaakiaaiMcacaWG4bWaaWbaaSqabeaacaaIYaaaaaaaaaa@92A1@

For the general polynomial of degree :

P 4 (x)= x 4 +p x 2 +qx+r Q 4 (x)=4 x 3 +2px+q MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaBaaaleaacaaI0aaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWG4bWaaWbaaSqabeaacaaI0aaaaOGaey4kaSIaamiCaiaaysW7caWG4bWaaWbaaSqabeaacaaIYaaaaOGaey4kaSIaamyCaiaaysW7caWG4bGaey4kaSIaamOCaiaaywW7caWGrbWaaSbaaSqaaiaaisdaaeqaaOGaaGikaiaadIhacaaIPaGaaGypaiaaisdacaWG4bWaaWbaaSqabeaacaaIZaaaaOGaey4kaSIaaGOmaiaadchacaaMe8UaamiEaiabgUcaRiaadghaaaa@5A22@

in 5 iterations we have the discriminant is [5]

disc=256 r 3 128 p 2 r 2 +144p q 2 r27 q 4 +16 p 4 r4 p 3 q 2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamizaiaadMgacaWGZbGaam4yaiaai2dacaaIYaGaaGynaiaaiAdacaWGYbWaaWbaaSqabeaacaaIZaaaaOGaeyOeI0IaaGymaiaaikdacaaI4aGaamiCamaaCaaaleqabaGaaGOmaaaakiaadkhadaahaaWcbeqaaiaaikdaaaGccqGHRaWkcaaIXaGaaGinaiaaisdacaWGWbGaamyCamaaCaaaleqabaGaaGOmaaaakiaadkhacqGHsislcaaIYaGaaG4naiaadghadaahaaWcbeqaaiaaisdaaaGccqGHRaWkcaaIXaGaaGOnaiaadchadaahaaWcbeqaaiaaisdaaaGccaWGYbGaeyOeI0IaaGinaiaadchadaahaaWcbeqaaiaaiodaaaGccaWGXbWaaWbaaSqabeaacaaIYaaaaaaa@5D1A@

A more formal case [5] is:

P m (x)= x m +ax+b; Q m (x)= P m (x ) =m x m1 +a MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaBaaaleaacaWGTbaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWG4bWaaWbaaSqabeaacaWGTbaaaOGaey4kaSIaamyyaiaaysW7caWG4bGaey4kaSIaamOyaiaaiUdacaaMf8UaamyuamaaBaaaleaacaWGTbaabeaakiaaiIcacaWG4bGaaGykaiaai2dacaWGqbWaaSbaaSqaaiaad2gaaeqaaOGaaGikaiaadIhaceaIPaGbauaacaaI9aGaamyBaiaaysW7caWG4bWaaWbaaSqabeaacaWGTbGaeyOeI0IaaGymaaaakiabgUcaRiaadggaaaa@59B2@

so we have successively:

k[0,m]: p k (m) =b δ 0 k +a δ 1 k + δ m k and q k (m) =a δ 0 k +m δ m1 k        (7) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4AaiabgIGiolaaiUfacaaIWaGaaGilaiaad2gacaaIDbGaaGjbVlaaiQdacaaMe8UaamiCamaaDaaaleaacaWGRbaabaGaaGikaiaad2gacaaIPaaaaOGaaGypaiaadkgacaaMe8UaeqiTdq2aa0baaSqaaiaaicdaaeaacaWGRbaaaOGaey4kaSIaamyyaiaaysW7cqaH0oazdaqhaaWcbaGaaGymaaqaaiaadUgaaaGccqGHRaWkcqaH0oazdaqhaaWcbaGaamyBaaqaaiaadUgaaaGccaaMe8Uaaeyyaiaab6gacaqGKbGaaGjbVlaadghadaqhaaWcbaGaam4AaaqaaiaaiIcacaWGTbGaaGykaaaakiaai2dacaWGHbGaaGjbVlabes7aKnaaDaaaleaacaaIWaaabaGaam4AaaaakiabgUcaRiaad2gacaaMe8UaeqiTdq2aa0baaSqaaiaad2gacqGHsislcaaIXaaabaGaam4AaaaakiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGOaGaae4naiaabMcaaaa@7911@

so

p 0 (m) =b; p m (m) =1; q 0 (m) =a; q m (m) =0; Δ m =a k[0,m1]{ p k (m1) = a 2 δ 0 k mb δ m2 k +a δ m1 k q k (m1) =a δ 0 k m δ m1 k       (8) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabiGaaaqaaaqaaiaadchadaqhaaWcbaGaaGimaaqaaiaaiIcacaWGTbGaaGykaaaakiaai2dacaWGIbGaaGjbVlaaiUdacaaMe8UaamiCamaaDaaaleaacaWGTbaabaGaaGikaiaad2gacaaIPaaaaOGaaGypaiaaigdacaaMe8UaaG4oaiaaysW7caWGXbWaa0baaSqaaiaaicdaaeaacaaIOaGaamyBaiaaiMcaaaGccaaI9aGaamyyaiaaysW7caaI7aGaaGjbVlaadghadaqhaaWcbaGaamyBaaqaaiaaiIcacaWGTbGaaGykaaaakiaai2dacaaIWaGaaGjbVlaaiUdacaaMe8UaeuiLdq0aaSbaaSqaaiaad2gaaeqaaOGaaGypaiabgkHiTiaadggaaeaaaeaacaWGRbGaeyicI4SaaG4waiaaicdacaaISaGaamyBaiabgkHiTiaaigdacaaIDbGaaGjbVpaaceaabaqbaeqabiqaaaqaaiaadchadaqhaaWcbaGaam4AaaqaaiaaiIcacaWGTbGaeyOeI0IaaGymaiaaiMcaaaGccaaI9aGaamyyamaaCaaaleqabaGaaGOmaaaakiabes7aKnaaDaaaleaacaaIWaaabaGaam4AaaaakiabgkHiTiaad2gacaWGIbGaaGjbVlabes7aKnaaDaaaleaacaWGTbGaeyOeI0IaaGOmaaqaaiaadUgaaaGccqGHRaWkcaWGHbGaaGjbVlabes7aKnaaDaaaleaacaWGTbGaeyOeI0IaaGymaaqaaiaadUgaaaaakeaacaWGXbWaa0baaSqaaiaadUgaaeaacaaIOaGaamyBaiabgkHiTiaaigdacaaIPaaaaOGaaGypaiabgkHiTiaadggacqaH0oazdaqhaaWcbaGaaGimaaqaaiaadUgaaaGccqGHsislcaWGTbGaeqiTdq2aa0baaSqaaiaad2gacqGHsislcaaIXaaabaGaam4AaaaaaaaakiaawUhaaaaacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGOaGaaeioaiaabMcaaaa@A71A@

then

p 0 (m1) = a 2 ; p m1 (m1) =a; q 0 (m1) =a; q m1 (m1) =m; Δ m1 =(m1) a 2 k[0,m2]{ p k (m2) =mab δ m3 k +(m1) a 2 δ m2 k q k (m2) =(m1) a 2 δ 0 k + m 2 b δ m2 k        (9) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeaabiGaaaqaaaqaaiaadchadaqhaaWcbaGaaGimaaqaaiaaiIcacaWGTbGaeyOeI0IaaGymaiaaiMcaaaGccaaI9aGaamyyamaaCaaaleqabaGaaGOmaaaakiaaysW7caaI7aGaaGjbVlaadchadaqhaaWcbaGaamyBaiabgkHiTiaaigdaaeaacaaIOaGaamyBaiabgkHiTiaaigdacaaIPaaaaOGaaGypaiaadggacaaMe8UaaG4oaiaaysW7caWGXbWaa0baaSqaaiaaicdaaeaacaaIOaGaamyBaiabgkHiTiaaigdacaaIPaaaaOGaaGypaiabgkHiTiaadggacaaMe8UaaG4oaiaaysW7caWGXbWaa0baaSqaaiaad2gacqGHsislcaaIXaaabaGaaGikaiaad2gacqGHsislcaaIXaGaaGykaaaakiaai2dacqGHsislcaWGTbGaaGjbVlaaiUdacaaMe8UaeuiLdq0aaSbaaSqaaiaad2gacqGHsislcaaIXaaabeaakiaai2dacqGHsislcaaIOaGaamyBaiabgkHiTiaaigdacaaIPaGaamyyamaaCaaaleqabaGaaGOmaaaaaOqaaaqaaiaadUgacqGHiiIZcaaIBbGaaGimaiaaiYcacaWGTbGaeyOeI0IaaGOmaiaai2facaaMe8+aaiqaaeaafaqabeGabaaabaGaamiCamaaDaaaleaacaWGRbaabaGaaGikaiaad2gacqGHsislcaaIYaGaaGykaaaakiaai2dacaWGTbGaamyyaiaadkgacaaMe8UaeqiTdq2aa0baaSqaaiaad2gacqGHsislcaaIZaaabaGaam4AaaaakiabgUcaRiaaiIcacaWGTbGaeyOeI0IaaGymaiaaiMcacaWGHbWaaWbaaSqabeaacaaIYaaaaOGaaGjbVlabes7aKnaaDaaaleaacaWGTbGaeyOeI0IaaGOmaaqaaiaadUgaaaaakeaacaWGXbWaa0baaSqaaiaadUgaaeaacaaIOaGaamyBaiabgkHiTiaaikdacaaIPaaaaOGaaGypaiabgkHiTiaaiIcacaWGTbGaeyOeI0IaaGymaiaaiMcacaWGHbWaaWbaaSqabeaacaaIYaaaaOGaeqiTdq2aa0baaSqaaiaaicdaaeaacaWGRbaaaOGaey4kaSIaamyBamaaCaaaleqabaGaaGOmaaaakiaadkgacaaMe8UaeqiTdq2aa0baaSqaaiaad2gacqGHsislcaaIYaaabaGaam4AaaaaaaaakiaawUhaaaaacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeikaiaabMdacaqGPaaaaa@C357@

this structure will repeat, indeed, if

k[0,mj]{ p k (mj) = A j δ mj1 k + B j δ mj k q k (mj) = B j δ 0 k + C j δ mj k       (10) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4AaiabgIGiolaaiUfacaaIWaGaaGilaiaad2gacqGHsislcaWGQbGaaGyxaiaaysW7daGabaqaauaabeqaceaaaeaacaWGWbWaa0baaSqaaiaadUgaaeaacaaIOaGaamyBaiabgkHiTiaadQgacaaIPaaaaOGaaGypaiaadgeadaWgaaWcbaGaamOAaaqabaGccaaMe8UaeqiTdq2aa0baaSqaaiaad2gacqGHsislcaWGQbGaeyOeI0IaaGymaaqaaiaadUgaaaGccqGHRaWkcaWGcbWaaSbaaSqaaiaadQgaaeqaaOGaaGjbVlabes7aKnaaDaaaleaacaWGTbGaeyOeI0IaamOAaaqaaiaadUgaaaaakeaacaWGXbWaa0baaSqaaiaadUgaaeaacaaIOaGaamyBaiabgkHiTiaadQgacaaIPaaaaOGaaGypaiabgkHiTiaadkeadaWgaaWcbaGaamOAaaqabaGccqaH0oazdaqhaaWcbaGaaGimaaqaaiaadUgaaaGccqGHRaWkcaWGdbWaaSbaaSqaaiaadQgaaeqaaOGaaGjbVlabes7aKnaaDaaaleaacaWGTbGaeyOeI0IaamOAaaqaaiaadUgaaaaaaaGccaGL7baacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGOaGaaeymaiaabcdacaqGPaaaaa@7C7D@

then p 0 (mj) =0 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaad2gacqGHsislcaWGQbGaaGykaaaakiaai2dacaaIWaaaaa@3F24@ , p mj (mj) = B j MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaWGTbGaeyOeI0IaamOAaaqaaiaaiIcacaWGTbGaeyOeI0IaamOAaiaaiMcaaaGccaaI9aGaamOqamaaBaaaleaacaWGQbaabeaaaaa@4260@ , q 0 (mj) = B j MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyCamaaDaaaleaacaaIWaaabaGaaGikaiaad2gacqGHsislcaWGQbGaaGykaaaakiaai2dacqGHsislcaWGcbWaaSbaaSqaaiaadQgaaeqaaaaa@413A@ , q mj (mj) = C j MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyCamaaDaaaleaacaWGTbGaeyOeI0IaamOAaaqaaiaaiIcacaWGTbGaeyOeI0IaamOAaiaaiMcaaaGccaaI9aGaam4qamaaBaaaleaacaWGQbaabeaaaaa@4262@ , then Δ mj = B j 2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeuiLdq0aaSbaaSqaaiaad2gacqGHsislcaWGQbaabeaakiaai2dacaWGcbWaa0baaSqaaiaadQgaaeaacaaIYaaaaaaa@3F5A@ and the next coefficients are:

k[0,mj1]{ p k (mj1) = B j A j δ mj2 k B j 2 δ mj1 k q k (mj1) = B j 2 δ 0 k + C j A j δ mj1 k      (11) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4AaiabgIGiolaaiUfacaaIWaGaaGilaiaad2gacqGHsislcaWGQbGaeyOeI0IaaGymaiaai2facaaMe8+aaiqaaeaafaqabeGabaaabaGaamiCamaaDaaaleaacaWGRbaabaGaaGikaiaad2gacqGHsislcaWGQbGaeyOeI0IaaGymaiaaiMcaaaGccaaI9aGaeyOeI0IaamOqamaaBaaaleaacaWGQbaabeaakiaadgeadaWgaaWcbaGaamOAaaqabaGccaaMe8UaeqiTdq2aa0baaSqaaiaad2gacqGHsislcaWGQbGaeyOeI0IaaGOmaaqaaiaadUgaaaGccqGHsislcaWGcbWaa0baaSqaaiaadQgaaeaacaaIYaaaaOGaaGjbVlabes7aKnaaDaaaleaacaWGTbGaeyOeI0IaamOAaiabgkHiTiaaigdaaeaacaWGRbaaaaGcbaGaamyCamaaDaaaleaacaWGRbaabaGaaGikaiaad2gacqGHsislcaWGQbGaeyOeI0IaaGymaiaaiMcaaaGccaaI9aGaamOqamaaDaaaleaacaWGQbaabaGaaGOmaaaakiabes7aKnaaDaaaleaacaaIWaaabaGaam4AaaaakiabgUcaRiaadoeadaWgaaWcbaGaamOAaaqabaGccaWGbbWaaSbaaSqaaiaadQgaaeqaaOGaaGjbVlabes7aKnaaDaaaleaacaWGTbGaeyOeI0IaamOAaiabgkHiTiaaigdaaeaacaWGRbaaaaaaaOGaay5EaaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGOaGaaeymaiaabgdacaqGPaaaaa@8980@

so we have the recurrence A j+1 = B j A j MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqamaaBaaaleaacaWGQbGaey4kaSIaaGymaaqabaGccaaI9aGaeyOeI0IaamOqamaaBaaaleaacaWGQbaabeaakiaadgeadaWgaaWcbaGaamOAaaqabaaaaa@4093@ , B j+1 = B j 2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOqamaaBaaaleaacaWGQbGaey4kaSIaaGymaaqabaGccaaI9aGaeyOeI0IaamOqamaaDaaaleaacaWGQbaabaGaaGOmaaaaaaa@3F66@ and C j+1 = C j A j MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qamaaBaaaleaacaWGQbGaey4kaSIaaGymaaqabaGccaaI9aGaam4qamaaBaaaleaacaWGQbaabeaakiaadgeadaWgaaWcbaGaamOAaaqabaaaaa@3FA9@ from j=2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOAaiaai2dacaaIYaaaaa@39FC@ (with A 2 =mab MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqamaaBaaaleaacaaIYaaabeaakiaai2dacaWGTbGaamyyaiaadkgaaaa@3CC8@ , B 2 =(m1) a 2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOqamaaBaaaleaacaaIYaaabeaakiaai2dacaaIOaGaamyBaiabgkHiTiaaigdacaaIPaGaamyyamaaCaaaleqabaGaaGOmaaaaaaa@3FD8@ , C 2 = m 2 b MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qamaaBaaaleaacaaIYaaabeaakiaai2dacaWGTbWaaWbaaSqabeaacaaIYaaaaOGaamOyaaaa@3CD7@ ) up to j=m2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOAaiaai2dacaWGTbGaeyOeI0IaaGOmaaaa@3BDB@ . At j=m1 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOAaiaai2dacaWGTbGaeyOeI0IaaGymaaaa@3BDA@ we arrive then to:

k[0,1]{ p k (1) = A m1 δ 0 k + B m1 δ 1 k q k (1) = B m1 δ 0 k + C m1 δ 1 k        (12) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4AaiabgIGiolaaiUfacaaIWaGaaGilaiaaigdacaaIDbGaaGjbVpaaceaabaqbaeqabiqaaaqaaiaadchadaqhaaWcbaGaam4AaaqaaiaaiIcacaaIXaGaaGykaaaakiaai2dacaWGbbWaaSbaaSqaaiaad2gacqGHsislcaaIXaaabeaakiaaysW7cqaH0oazdaqhaaWcbaGaaGimaaqaaiaadUgaaaGccqGHRaWkcaWGcbWaaSbaaSqaaiaad2gacqGHsislcaaIXaaabeaakiaaysW7cqaH0oazdaqhaaWcbaGaaGymaaqaaiaadUgaaaaakeaacaWGXbWaa0baaSqaaiaadUgaaeaacaaIOaGaaGymaiaaiMcaaaGccaaI9aGaeyOeI0IaamOqamaaBaaaleaacaWGTbGaeyOeI0IaaGymaaqabaGccqaH0oazdaqhaaWcbaGaaGimaaqaaiaadUgaaaGccqGHRaWkcaWGdbWaaSbaaSqaaiaad2gacqGHsislcaaIXaaabeaakiaaysW7cqaH0oazdaqhaaWcbaGaaGymaaqaaiaadUgaaaaaaaGccaGL7baacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeikaiaabgdacaqGYaGaaeykaaaa@75B3@

with p 0 (1) = A m1 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaaigdacaaIPaaaaOGaaGypaiaadgeadaWgaaWcbaGaamyBaiabgkHiTiaaigdaaeqaaaaa@3FE3@ , p 1 (1) = B m1 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaDaaaleaacaaIXaaabaGaaGikaiaaigdacaaIPaaaaOGaaGypaiaadkeadaWgaaWcbaGaamyBaiabgkHiTiaaigdaaeqaaaaa@3FE5@ , q 1 (1) = C m1 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyCamaaDaaaleaacaaIXaaabaGaaGikaiaaigdacaaIPaaaaOGaaGypaiaadoeadaWgaaWcbaGaamyBaiabgkHiTiaaigdaaeqaaaaa@3FE7@ and q 0 (1) = B m1 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyCamaaDaaaleaacaaIWaaabaGaaGikaiaaigdacaaIPaaaaOGaaGypaiabgkHiTiaadkeadaWgaaWcbaGaamyBaiabgkHiTiaaigdaaeqaaaaa@40D2@ so Δ 1 = C m1 A m1 + B m1 2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeuiLdq0aaSbaaSqaaiaaigdaaeqaaOGaaGypaiaadoeadaWgaaWcbaGaamyBaiabgkHiTiaaigdaaeqaaOGaamyqamaaBaaaleaacaWGTbGaeyOeI0IaaGymaaqabaGccqGHRaWkcaWGcbWaa0baaSqaaiaad2gacqGHsislcaaIXaaabaGaaGOmaaaaaaa@4702@ and the last iteration gives the constant:

{ p 0 (0) = B m1 2 A m1 C m1 q 0 (0) = C m1 A m1 + B m1 2       (13) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiqaaeaafaqabeGabaaabaGaamiCamaaDaaaleaacaaIWaaabaGaaGikaiaaicdacaaIPaaaaOGaaGypaiabgkHiTiaadkeadaqhaaWcbaGaamyBaiabgkHiTiaaigdaaeaacaaIYaaaaOGaeyOeI0IaamyqamaaBaaaleaacaWGTbGaeyOeI0IaaGymaaqabaGccaWGdbWaaSbaaSqaaiaad2gacqGHsislcaaIXaaabeaaaOqaaiaadghadaqhaaWcbaGaaGimaaqaaiaaiIcacaaIWaGaaGykaaaakiaai2dacaWGdbWaaSbaaSqaaiaad2gacqGHsislcaaIXaaabeaakiaadgeadaWgaaWcbaGaamyBaiabgkHiTiaaigdaaeqaaOGaey4kaSIaamOqamaaDaaaleaacaWGTbGaeyOeI0IaaGymaaqaaiaaikdaaaaaaaGccaGL7baacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGOaGaaeymaiaabodacaqGPaaaaa@629D@

the recurrence on B j MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOqamaaBaaaleaacaWGQbaabeaaaaa@396C@ , A j MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqamaaBaaaleaacaWGQbaabeaaaaa@396B@ and C j MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qamaaBaaaleaacaWGQbaabeaaaaa@396D@ gives ( j2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOAaiabgwMiZkaaikdaaaa@3AFB@ )

B j = ( (m1) a 2 ) 2 j2 ; A j =mab ( (m1) a 2 ) 1+ 2 j2 MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOqamaaBaaaleaacaWGQbaabeaakiaai2dacqGHsisldaqadaqaaiaaiIcacaWGTbGaeyOeI0IaaGymaiaaiMcacaWGHbWaaWbaaSqabeaacaaIYaaaaaGccaGLOaGaayzkaaWaaWbaaSqabeaacaaIYaWaaWbaaeqabaGaamOAaiabgkHiTiaaikdaaaaaaOGaaGjbVlaaiUdacaaMe8UaamyqamaaBaaaleaacaWGQbaabeaakiaai2dacaWGTbGaaGjbVlaadggacaaMe8UaamOyamaabmaabaGaaGikaiaad2gacqGHsislcaaIXaGaaGykaiaadggadaahaaWcbeqaaiaaikdaaaaakiaawIcacaGLPaaadaahaaWcbeqaaiabgkHiTiaaigdacqGHRaWkcaaIYaWaaWbaaeqabaGaamOAaiabgkHiTiaaikdaaaaaaaaa@6030@

C j =(m1) m j a j b j1 ( (m1) a 2 ) 2 j2 j MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qamaaBaaaleaacaWGQbaabeaakiaai2dacaaIOaGaamyBaiabgkHiTiaaigdacaaIPaGaamyBamaaCaaaleqabaGaamOAaaaakiaadggadaahaaWcbeqaaiaadQgaaaGccaWGIbWaaWbaaSqabeaacaWGQbGaeyOeI0IaaGymaaaakmaabmaabaGaaGikaiaad2gacqGHsislcaaIXaGaaGykaiaadggadaahaaWcbeqaaiaaikdaaaaakiaawIcacaGLPaaadaahaaWcbeqaaiaaikdadaahaaqabeaacaWGQbGaeyOeI0IaaGOmaaaacqGHsislcaWGQbaaaaaa@52F6@

so the final constant term is

(m1) m+ 2 m2 +1 a 2 m1 m ( m m b m1 + (m1) m1 p m ) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGikaiaad2gacqGHsislcaaIXaGaaGykamaaCaaaleqabaGaeyOeI0IaamyBaiabgUcaRiaaikdadaahaaqabeaacaWGTbGaeyOeI0IaaGOmaaaacqGHRaWkcaaIXaaaaOGaamyyamaaCaaaleqabaGaaGOmamaaCaaabeqaaiaad2gacqGHsislcaaIXaaaaiabgkHiTiaad2gaaaGcdaqadaqaaiaad2gadaahaaWcbeqaaiaad2gaaaGccaWGIbWaaWbaaSqabeaacaWGTbGaeyOeI0IaaGymaaaakiabgUcaRiaaiIcacaWGTbGaeyOeI0IaaGymaiaaiMcadaahaaWcbeqaaiaad2gacqGHsislcaaIXaaaaOGaamiCamaaCaaaleqabaGaamyBaaaaaOGaayjkaiaawMcaaaaa@5B37@

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

m m b m1 + (m1) m1 a m      (14) MathType@MTEF@5@5@+=feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbnvMCYL2DLfgDOvMCaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGak0Jf9crFfpeea0xh9v8qiW7rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyBamaaCaaaleqabaGaamyBaaaakiaadkgadaahaaWcbeqaaiaad2gacqGHsislcaaIXaaaaOGaey4kaSIaaGikaiaad2gacqGHsislcaaIXaGaaGykamaaCaaaleqabaGaamyBaiabgkHiTiaaigdaaaGccaWGHbWaaWbaaSqabeaacaWGTbaaaOGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGOaGaaeymaiaabsdacaqGPaaaaa@4D0F@

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.

Appendix

  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