## 6.2. 6.2 Common roots of polynomials

Let be an integral domain and let

be arbitrary polynomials with . Let us give a necessary and sufficient condition for and sharing a common root in .

### 6.2.1. 6.2.1 Classical and extended Euclidean algorithm

If is a field, then is a Euclidean domain. Recall that we call an integral domain Euclidean together with the function if for all , there exist such that , where or ; furthermore, for all , we have . The element is called the quotient and is called the remainder. If we are working in a Euclidean domain, we would like the greatest common divisor to be unique. For this, a unique element has to be chosen from each equivalence class obtained by multiplying by the units of the ring . (For example, in case of integers we always choose the non-negative one from the classes ) Thus, every element has a unique form

where is called the normal form of . Let us consider a Euclidean domain over a field . Let the normal form of be the corresponding normalised monic polynomial, that is, , where denotes the leading coefficient of polynomial . Let us summarise these important cases:

• If then and ,

• if ( is a field) then (the leading coefficient of polynomial with the convention ), and .

The following algorithm computes the greatest common divisor of two arbitrary elements of a Euclidean domain. Note that this is one of the most ancient algorithms of the world, already known by Euclid around 300 B.C.

Classical-Euclidean( )

  1     2     3
WHILE

4
DO

5          6          7
RETURN



In the ring of integers, the remainder in line 4 becomes . When , where is a field, the remainder in line 4 can be calculated by the algorithm Euclidean-Division-Univariate-Polynomials( ) , the analysis of which is left to Exercise 6.2-1.

Figure 6.2 shows the operation of the Classical-Euclidean algorithm in and . Note that in the program only enters the while loop with non-negative numbers and the remainder is always non-negative, so the normalisation in line 7 is not needed.

Before examining the running time of the Classical-Euclidean algorithm, we deal with an extended version of it.

Extended-Euclidean( )

  1     2     3
WHILE

4
DO

5          6          7          8          9         10
RETURN



It is known that in the Euclidean domain , the greatest common divisor of elements can be expressed in the form with appropriate elements . However, this pair is not unique. For if are appropriate, then so are and for all :

The Classical-Euclidean algorithm is completed in a way that beside the greatest common divisor it outputs an appropriate pair as discussed above.

Let , where is a Euclidean domain together with the function . The equations

are obviously fulfilled due to the initialisation in the first two lines of the pseudocode Extended-Euclidean . We show that equations (6.3) are invariant under the transformations of the while loop of the pseudocode. Let us presume that the conditions (6.3) are fulfilled before an iteration of the loop. Then lines 4–5 of the pseudocode imply

hence, because of lines 6–7,

Lines 8–9 perform the following operations: take the values of and , then take the values of and , while takes the value of and . Thus, the equalities in (6.3) are also fulfilled after the iteration of the while loop. Since in each iteration of the loop, the series obtained in lines 8–9 is a strictly decreasing series of natural numbers, so sooner or later the control steps out of the while loop. The greatest common divisor is the last non-zero remainder in the series of Euclidean divisions, that is, in lines 8–9.

Example 6.3 Let us examine the series of remainders in the case of polynomials

The values of the variables before the execution of line are

The return values are:

We can see that the size of the coefficients show a drastic growth. One might ask why we do not normalise in every iteration of the while loop? This idea leads to the normalised version of the Euclidean algorithm for polynomials.

Extended-Euclidean-Normalised( )

  1     2     3     4     5
WHILE

6
DO

7          8          9         10         11         12         13         14
RETURN



Example 6.4 Let us look at the series of remainders and series obtained in the Extended-Euclidean-Normalised algorithm in case of the polynomials (6.4) and (6.5)

Before the execution of line of the pseudocode, the values of the variables are

Looking at the size of the coefficients in, the advantage of the normalised version is obvious, but we could still not avoid the growth. To get a machine architecture-dependent description and analysis of the Extended-Euclidean-Normalised algorithm, we introduce the following notation. Let

where is the word length of the computer in bits. It is easy to verify that if and , then

We give the following theorems without proof.

Theorem 6.1 If and , then the Classical-Euclidean and Extended-Euclidean algorithms require machine-word arithmetic operations.

Theorem 6.2 If is a field and , then the Classical-Euclidean , Extended-Euclidean and Extended-Euclidean-Normalised algorithms require elementary operations in .

Can the growth of the coefficients be due to the choice of our polynomials? Let us examine a single Euclidean division in the Extended-Euclidean-Normalised algorithm. Let , where

and are monic polynomials, , , , and consider the case . Then

Note that the bound (6.6) is valid for the coefficients of the remainder polynomial as well, that is, . So in case , the size of the coefficients may only grow by a factor of around three in each Euclidean division. This estimate seems accurate for pseudorandom polynomials, the interested reader should look at Problem 6-1. The worst case estimate suggests that

where denotes the running time of the Extended-Euclidean-Normalised algorithm, practically, the number of times the while loop is executed. Luckily, this exponential growth is not achieved in each iteration of the loop, and altogether the growth of the coefficients is bounded polynomially in terms of the input. Later we will see that the growth can be eliminated using modular techniques.

Summarising: after computing the greatest common divisor of the polynomials ( is a field), and have a common root if and only if their greatest common divisor is not a constant. For if is not a constant, then the roots of are also roots of and , since divides and . On the other hand, if and have a root in common, then their greatest common divisor cannot be a constant, since the common root is also a root of it.

### 6.2.2. 6.2.2 Primitive Euclidean algorithm

If is a UFD (unique factorisation domain, where every non-zero, non-unit element can be written as a product of irreducible elements in a unique way up to reordering and multiplication by units) but not necessarily a Euclidean domain then, the situation is more complicated, since we may not have a Euclidean algorithm in . Luckily, there are several useful methods due to: (1) unique factorisation in , (2) the existence of a greatest common divisor of two or more arbitrary elements.

The first possible method is to perform the calculations in the field of fractions of . The polynomial is called a primitive polynomial if there is no prime in that divides all coefficients of . A famous lemma by Gauss says that the product of primitive polynomials is also primitive, hence, for the primitive polynomials , if and only if , where denotes the field of fractions of . So we can calculate greatest common divisors in instead of . Unfortunately, this approach is not really effective because arithmetic in the field of fractions is much more expensive than in .

A second possibility is an algorithm similar to the Euclidean algorithm: in the ring of polynomials in one variable over an integral domain, a so-called pseudo-division can be defined. Using the polynomials (6.1), (6.2), if , then there exist , such that

where or . The polynomial is called the pseudo-quotient of and and is called the pseudo-remainder. The notation is .

Example 6.5 Let

Then .

On the other hand, each polynomial can be written in a unique form

up to a unit factor, where and are primitive polynomials. In this case, is called the content, is called the primitive part of . The uniqueness of the form can be achieved by the normalisation of units. For example, in the case of integers, we always choose the positive ones from the equivalence classes of .

The following algorithm performs a series of pseudo-divisions. The algorithm uses the function , which computes the pseudo-remainder, and it assumes that we can calculate greatest common divisors in , contents and primitive parts in . The input is , where is a UFD. The output is the polynomial .

Primitive-Euclidean( )

  1     2     3
WHILE

4
DO

5          6          7     8     9
RETURN



The operation of the algorithm is illustrated by Figure 6.3. The running time of the Primitive-Euclidean algorithm is the same as the running time of the previous versions of the Euclidean algorithm.

The Primitive-Euclidean algorithm is very important because the ring of multivariate polynomials is a UFD, so we apply the algorithm recursively, e.g. in , using computations in the UFDs . In other words, the recursive view of multivariate polynomial rings leads to the recursive application of the Primitive-Euclidean algorithm in a straightforward way.

We may note that, like above, the algorithm shows a growth in the coefficients.

Let us take a detailed look at the UFD . The bound on the size of the coefficients of the greatest common divisor is given by the following theorem, which we state without proof.

Theorem 6.3 (Landau-Mignotte) Let , , and . Then

Corollary 6.4 With the notations of the previous theorem, the absolute value of any coefficient of the polynomial is smaller than

Proof. The greatest common divisor of and obviously divides both and , and its degree is at most the minimum of their degrees. Furthermore, the leading coefficient of the greatest common divisor divides and , so it also divides .

Example 6.6 Corollary 6.4 implies that the absolute value of the coefficients of the greatest common divisor is at most for the polynomials (6.4), (6.5), and at most for the polynomials (6.7) and (6.8).

### 6.2.3. 6.2.3 The resultant

The following method describes the necessary and sufficient conditions for the common roots of (6.1) and (6.2) in the most general context. As a further advantage, it can be applied to solve algebraic equation systems of higher degree.

Let be an integral domain and its field of fractions. Let us consider the smallest extension of over which both of (6.1) and of (6.2) splits into linear factors. Let us denote the roots (in ) of the polynomial by , and the roots of by . Let us form the following product:

It is obvious that equals to if and only if for some and , that is, and have a common root. The product is called the resultant of the polynomials and . Note that the value of the resultant depends on the order of and , but the resultants obtained in the two ways can only differ in sign.

Evidently, this form of the resultant cannot be applied in practice, since it presumes that the roots are known. Let us examine the different forms of the resultant. Since

hence,

Thus,

Although it looks a lot more friendly, this form still requires the roots of at least one polynomial. Next we examine how the resultant may be expressed only in terms of the coefficients of the polynomials. This leads to the Sylvester form of the resultant.

Let us presume that polynomial in (6.1) and polynomial in (6.2) have a common root. This means that there exists a number such that

Multiply these equations by the numbers , and , respectively. We get equations from the first one and from the second one. Consider these equations as a homogeneous system of linear equations in indeterminates. This system has the obviously non-trivial solution . It is a well-known fact that a homogeneous system with as many equations as indeterminates has non-trivial solutions if and only if its determinant is zero. We get that and can only have common roots if the determinant

equals to (there are 0s everywhere outside the dotted areas). Thus, a necessary condition for the existence of common roots is that the determinant of order is 0. Below we prove that equals to the resultant of and , hence, is also a sufficient condition for common roots. The determinant (6.9) is called the Sylvester form of the resultant.

Theorem 6.5 Using the above notation

Proof. We will precede by induction on . If , then , so the right-hand side is . The left-hand side is a determinant of order with everywhere in the diagonal, and 0 everywhere else. Thus, , so the statement is true. In the following, presume that and the statement is true for . If we take the polynomial

instead of , then and fulfil the condition:

Since , the coefficients of and satisfy

Thus,

We transform the determinant in the following way: add times the first column to the second column, then add times the new second column to the third column, etc. This way the -s disappear from the first lines, so the first lines of and the transformed are identical. In the last rows, subtract times the second one from the first one, and similarly, always subtract times a row from the row right above it. In the end, becomes

Using the last row for expansion, we get , which implies by the induction hypothesis.

We get that , that is, polynomials and have a common root in if and only if determinant vanishes.

From an algorithmic point of view, the computation of the resultant in Sylvester form for higher degree polynomials means the computation of a large determinant. The following theorem implies that pseudo-division may simplify the computation.

Theorem 6.6 For the polynomials of (6.1) and of (6.2), in case of

Proof. Multiply the first line of the determinant (6.9) by . Let and be the uniquely determined polynomials with

where . Then multiplying row of the resultant by , row by etc., and subtracting them from the first row we get the determinant

Here is in the th column of the first row, and is in the th column of the first row.

Similarly, multiply the second row by , then multiply rows by etc., and subtract them from the second row. Continue the same way for the third, th row. The result is

After reordering the rows

Note that

thus,

and therefore

Equation (6.10) describes an important relationship. Instead of computing the possibly gigantic determinant , we perform a series of pseudo-divisions and apply (6.10) in each step. We calculate the resultant only when no more pseudo-division can be done. An important consequence of the theorem is the following corollary.

Corollary 6.7 There exist polynomials such that , with , .

Proof. Multiply the th column of the determinant form of the resultant by and add it to the last column for . Then

Using the last column for expansion and factoring and , we get the statement with the restrictions on the degrees.

The most important benefit of the resultant method, compared to the previously discussed methods, is that the input polynomials may contain symbolic coefficients as well.

Example 6.7 Let

Then the existence of common rational roots of and cannot be decided by variants of the Euclidean algorithm, but we can decide it with the resultant method. Such a root exists if and only if

that is, when or .

The significance of the resultant is not only that we can decide the existence of common roots of polynomials, but also that using it we can reduce the solution of algebraic equation systems to solving univariate equations.

Example 6.8 Let

Consider polynomials and as elements of . They have a common root if and only if

Common roots in can exist for . For each , we substitute into equations (6.11) and (6.12) (already in ) and get that the integer solutions are .

We note that the resultant method can also be applied to solve polynomial equations in several variables, but it is not really effective. One problem is that computational space explosion occurs in the computation of the determinant. Note that computing the resultant of two univariate polynomials in determinant form using the usual Gauss-elimination requires operations, while the variants of the Euclidean algorithm are quadratic. The other problem is that computational complexity depends strongly on the order of the indeterminates. Eliminating all variables together in a polynomial equation system is much more effective. This leads to the introduction of multivariate resultants.

### 6.2.4. 6.2.4 Modular greatest common divisor

All methods considered so far for the existence and calculation of common roots of polynomials are characterised by an explosion of computational space. The natural question arises: can we apply modular techniques? Below we examine the case with . Let us consider the polynomials (6.4), (6.5) and let a prime number. Then the series of remainders in in the Classical-Euclidean algorithm is

We get that polynomials and are relatively prime in . The following theorem describes the connection between greatest common divisors in and .

Theorem 6.8 Let . Let be a prime such that and . Let furthermore , , and . Then

(1) ,

(2) if , then .

Proof. (1): Since and , thus . So

By the hypothesis , which implies

(2): Since and is non-trivial,

If , then the right-hand side of (6.13) is non-trivial, thus . But the resultant is the sum of the corresponding products of the coefficients, so , contradiction.

Corollary 6.9 There are at most a finite number of primes such that , and .

In case statement (1) of Theorem 6.8 is fulfilled, we call a “lucky prime'”. We can outline a modular algorithm for the computation of the gcd.

Modular-Gcd-Bigprime( )

  1   the Landau-Mignotte constant (from Corollary 6.4)   2     3
WHILE

TRUE
4
DO

a prime with , ,  and    5          6
IF

and    7
THEN

RETURN

8
ELSE



The first line of the algorithm requires the calculation of the Landau-Mignotte bound. The fourth line requires a “sufficiently large” prime which does not divide the leading coefficient of and . The fifth line computes the greatest common divisor of polynomials and modulo (for example with the Classical-Euclidean algorithm in ). We store the coefficients of the resulting polynomials with symmetrical representation. The sixth line examines whether and are fulfilled, in which case is the required greatest common divisor. If this is not the case, then is an “unlucky prime”, so we choose another prime. Since, by Theorem 6.8, there are only finitely many “unlucky primes”, the algorithm eventually terminates. If the primes are chosen according to a given strategy, set is not needed.

The disadvantage of the Modular-gcd-bigprime algorithm is that the Landau-Mignotte constant grows exponentially in terms of the degree of the input polynomials, so we have to work with large primes. The question is how we could modify the algorithm so that we can work with “many small primes”. Since the greatest common divisor in is only unique up to a constant factor, we have to be careful with the coefficients of the polynomials in the new algorithm. So, before applying the Chinese remainder theorem for the coefficients of the modular greatest common divisors taken modulo different primes, we have to normalise the leading coefficient of . If and are the leading coefficients of and , then the leading coefficient of divides . Therefore, we normalise the leading coefficient of to in case of primitive polynomials and ; and finally take the primitive part of the resulting polynomial. Just like in the Modular-gcd-bigprime algorithm, modular values are stored with symmetrical representation. These observations lead to the following modular gcd algorithm using small primes.

Modular-Gcd-Smallprimes( )

  1     2   a prime such that    3     4     5     6     7     8
WHILE

true
9
DO

IF

10
THEN

IF

11
THEN

RETURN

12         13
IF

14
THEN

15
IF

and   16
THEN

RETURN

17     a prime such that  and   18      19      20      21
IF

22
THEN

23
IF

24
THEN

IF

25
THEN

Coeff-build(

)
26
IF

27
THEN

28
ELSE

29               30


Coeff-Build( )

  1     2     3
FOR

DOWNTO

4
DO

5          6          7
RETURN



We may note that the algorithm Modular-Gcd-Smallprimes does not require as many small primes as the Landau-Mignotte bound tells us. When the value of polynomial does not change during a few iterations, we test in lines 13–16 if is a greatest common divisor. The number of these iterations is stored in the variable of line six. Note that the value of could vary according to the input polynomial. The primes used in the algorithms could preferably be chosen from an (architecture-dependent) prestored list containing primes that fit in a machine word, so the use of set becomes unnecessary. Corollary 6.9 implies that the Modular-Gcd-Smallprimes algorithm always terminates.

The Coeff-Build algorithm computes the solution of the equation system obtained by taking congruence relations modulo and for the coefficients of identical degree in the input polynomials and . This is done according to the Chinese remainder theorem. It is very important to store the results in symmetrical modular representation form.

Example 6.9 Let us examine the operation of the Modular-Gcd-Smallprimes algorithm for the previously seen polynomials (6.4), (6.5). For simplicity, we calculate with small primes. Recall that

After the execution of the first six lines of the algorithm with , we have and . Since due to line 7, lines 10–12 are executed. Polynomial is not zero, so , and will be the values after the execution. The condition in line 13 is not fulfilled, so we choose another prime, is a bad choice, but is allowed. According to lines 19–20, , . Since , we have and lines 25–30 are not executed. Polynomial is constant, so the return value in line 11 is 1, which means that polynomials and are relatively prime.

Example 6.10 In our second example, consider the already discussed polynomials

Let again . After the first six lines of the polynomials . After the execution of lines 10–12, we have . Let the next prime be . So the new values are . Since , and the new value of is after lines 25–30. The value of the variable is still 1. Let the next prime be 11. Then . Polynomials and have the same degree, so we modify the coefficients of . Then and since , we get and . Let the new prime be 13. Then . The degrees of and are still equal, thus lines 25–30 are executed and the variables become .After the execution of lines 17–18, it turns out that and , so is the greatest common divisor.

We give the following theorem without proof.

Theorem 6.10 The Modular-Gcd-Smallprimes algorithm works correctly. The computational complexity of the algorithm is machine word operations, where , and is the Landau-Mignotte bound for polynomials and .

Exercises

6.2-1 Let be a commutative ring with identity element, , , furthermore, a unit, . The following algorithm performs Euclidean division for and and outputs polynomials for which and or holds.

Euclidean-Division-Univariate-Polynomials( )

  1     2
FOR

DOWNTO

3
DO

IF

4
THEN

5             6
ELSE

7   and    8
RETURN



Prove that the algorithm uses at most

operations in .

6.2-2 What is the difference between the algorithms Extended-Euclidean and Extended-Euclidean-Normalised in ?

6.2-3 Prove that .

6.2-4 The discriminant of polynomial (, ) is the element

where denotes the derivative of with respect to . Polynomial has a multiple root if and only if its discriminant is 0. Compute for general polynomials of second and third degree.