P03-RationalRootTest.mws

High School Modules > Precalculus by Gregory A. Moore

     Rational Root Test


An exploration of the rational root test for factoring polynomials

[Directions : Execute the Code Resource section first. Although there will be no output immediately, these definitions are used later in this worksheet.]

  0. Code

>    restart;

>   

>    RatDiv  :=  proc( L, C)
    local n,m, i, j;
print(`The possible rational binomial divisors are :`);
n := numtheory[divisors](L);
m := numtheory[divisors](C);
for i from 1 to nops(n) do
  for j from 1 to nops(m) do
     print( n[i]*x + m[j],`   ` ,  n[i]*x - m[j] );
od; od;
end proc:

>    SynDiv  :=  proc( P, r)
    local A, C, d, i,j,k;
    d := degree( P);
    for k from 0 to d do   C||k := coeff(P, x, k) ;  od;
    A := array( [seq( [  seq(` `, j = 0..(d+2) ) ],   i = 1..4) ]);
    A[1,1] := r;
    for k from 0 to d do  A[1,d - k + 3] :=  C||k ; od;
    for k from 0 to d do  A[2,d - k + 3] :=  0; od;
    for k from 0 to d do  A[3,d - k + 3] :=  `__`; od;
    for k from 0 to d do  
       A[4,k + 3] := A[1,k + 3] + A[2,k + 3];
       if(k<d) then A[2,k + 4] := r * A[4,k + 3]; fi
        od;
    print(A);
    end proc:

>    RatRootTest  :=  proc( P)
    local A, C, d, i,j,k,n,m,row,rows;
    d := degree( P);
    for k from 0 to d do   C||k := coeff(P, x, k) ;  od;
    n := numtheory[divisors](C||d);
    m := numtheory[divisors](C||0);
    rows := 2*nops(n)*nops(m) + 2;
    A := array( [seq( [  seq(` `, j = 0..(d+3) ) ],   i = 1..rows) ]);
    for k from 0 to d do  A[1,d - k + 3] :=  C||k ; od;
    for k from 0 to d do  A[2,d - k + 3] :=  `__`; od;
    
    for i from 1 to nops(n) do
      for j from 1 to nops(m) do
        row := j + nops(m)*(i-1) + 2;
        A[row,1] := m[j]/n[i];
        A[row,2] := `|`;
        A[row,3] := C||d;
        for k from 1 to d do  
             A[row,k+3] := A[1,k+3] + A[row,1]*A[row,k+2];
        od;
        if( A[row, d+3] = 0) then A[row, d+4] := `Root!`; fi;
    od: od:

  for i from 1 to nops(n) do
      for j from 1 to nops(m) do
        row := j + nops(m)*(i-1) + 2 + nops(n)*nops(m);
        A[row,1] := -m[j]/n[i];
        A[row,2] := `|`;
        A[row,3] := C||d;
        for k from 1 to d do  
             A[row,k+3] := A[1,k+3] + A[row,1]*A[row,k+2];
        od;
        if( A[row, d+3] = 0) then A[row, d+4] := `Root!`; fi;
    od: od:

    print(A);
    end proc:

  1. The Relationship Between Polynomials Factors and Expanded Result


Please take a look at these examples for a moment. Look at the leading coefficients of each binomial and how they compare to the leading coefficient of the expanded polynomial. Also look at the constant terms and how they compare to the constant term of the expanded polynomial.

>    (2*x + 5)*(x + 3)*(4*x -9): % = expand(%);

(2*x+5)*(x+3)*(4*x-9) = 8*x^3+26*x^2-39*x-135

>    (100*x + 2)*(10*x + 8)*(1000*x - 4): % = expand(%);

(100*x+2)*(10*x+8)*(1000*x-4) = 1000000*x^3+816000*x^2+12720*x-64

>    (a[1]*x + b[1])*(a[2]*x + b[2])*(a[3]*x + b[3]); sort(expand(%));

(a[1]*x+b[1])*(a[2]*x+b[2])*(a[3]*x+b[3])

x^3*a[1]*a[2]*a[3]+x^2*a[1]*a[2]*b[3]+x^2*a[1]*b[2]*a[3]+x^2*b[1]*a[2]*a[3]+x*a[1]*b[2]*b[3]+x*b[1]*a[2]*b[3]+x*b[1]*b[2]*a[3]+b[1]*b[2]*b[3]

>    (a[1]*x + b[1])*(a[2]*x + b[2])*(a[3]*x + b[3])*(a[4]*x + b[4]);
sort(expand(%));

(a[1]*x+b[1])*(a[2]*x+b[2])*(a[3]*x+b[3])*(a[4]*x+b[4])

x^4*a[1]*a[2]*a[3]*a[4]+x^3*a[1]*a[2]*a[3]*b[4]+x^3*a[1]*a[2]*b[3]*a[4]+x^3*a[1]*b[2]*a[3]*a[4]+x^3*b[1]*a[2]*a[3]*a[4]+x^2*a[1]*a[2]*b[3]*b[4]+x^2*a[1]*b[2]*a[3]*b[4]+x^2*a[1]*b[2]*b[3]*a[4]+x^2*b[1]*...
x^4*a[1]*a[2]*a[3]*a[4]+x^3*a[1]*a[2]*a[3]*b[4]+x^3*a[1]*a[2]*b[3]*a[4]+x^3*a[1]*b[2]*a[3]*a[4]+x^3*b[1]*a[2]*a[3]*a[4]+x^2*a[1]*a[2]*b[3]*b[4]+x^2*a[1]*b[2]*a[3]*b[4]+x^2*a[1]*b[2]*b[3]*a[4]+x^2*b[1]*...



The interesting thing you might notice is that the leading term of the result comes purely from the leading terms of the factors, and the constant term of the result comes purely from the constant terms of the factors. In fact, the leading term is the product of the leading terms of the factors, and constant is the product of  the constants of the factors!

  2. The Concept of the Rational Roots


Now we turn this thinking around. If we can see only the resulting polynomial, and we assume that it has rational factors, then those binomial factors must have coefficients which are factors of the resulting terms. In particular, if a binomial, ax + b , divides a polynomial P (x), then a  must be a factor of the leading coefficient, and b  must be a factor of the constant term.

>    P := 12*x^5 + 17*x^3 + 35;

P := 12*x^5+17*x^3+35


The divisors of the leading coefficient, 12, are :

>    numtheory[divisors](12);

{1, 2, 3, 4, 6, 12}


The divisors of the constant term, 35, are :

>    numtheory[divisors](35);

{1, 5, 7, 35}


If we form every possible binomial of the form ax + b , where a  is from the first list and b  is from the second, we get this.

>    RatDiv( 12, 35);

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+5, `   `, x-5

x+7, `   `, x-7

x+35, `   `, x-35

2*x+1, `   `, 2*x-1

2*x+5, `   `, 2*x-5

2*x+7, `   `, 2*x-7

2*x+35, `   `, 2*x-35

3*x+1, `   `, 3*x-1

3*x+5, `   `, 3*x-5

3*x+7, `   `, 3*x-7

3*x+35, `   `, 3*x-35

4*x+1, `   `, 4*x-1

4*x+5, `   `, 4*x-5

4*x+7, `   `, 4*x-7

4*x+35, `   `, 4*x-35

6*x+1, `   `, 6*x-1

6*x+5, `   `, 6*x-5

6*x+7, `   `, 6*x-7

6*x+35, `   `, 6*x-35

12*x+1, `   `, 12*x-1

12*x+5, `   `, 12*x-5

12*x+7, `   `, 12*x-7

12*x+35, `   `, 12*x-35


Although this list is long, it is exhaustive. It includes EVERY possible binomial factor of this polynomial. If none of these divides the polynomials then it is not divisible by a binomial with integer coefficients. So all we have to do is to check these out!


Here are other examples. Note that it depends on how many divisors the leading coefficient and constant have.. the more divisors, the more possible factors.

>    P := x^2 + 17*x^3 + 25;
RatDiv( 1, 25);

P := x^2+17*x^3+25

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+5, `   `, x-5

x+25, `   `, x-25

>    P := 81*x^2 + 17*x^3 + 1;
RatDiv( 81, 1);

P := 81*x^2+17*x^3+1

`The possible rational binomial divisors are :`

x+1, `   `, x-1

3*x+1, `   `, 3*x-1

9*x+1, `   `, 9*x-1

27*x+1, `   `, 27*x-1

81*x+1, `   `, 81*x-1

>    P := 32*x^2 + 17*x^3 + 81;
RatDiv( 32, 81);

P := 32*x^2+17*x^3+81

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+3, `   `, x-3

x+9, `   `, x-9

x+27, `   `, x-27

x+81, `   `, x-81

2*x+1, `   `, 2*x-1

2*x+3, `   `, 2*x-3

2*x+9, `   `, 2*x-9

2*x+27, `   `, 2*x-27

2*x+81, `   `, 2*x-81

4*x+1, `   `, 4*x-1

4*x+3, `   `, 4*x-3

4*x+9, `   `, 4*x-9

4*x+27, `   `, 4*x-27

4*x+81, `   `, 4*x-81

8*x+1, `   `, 8*x-1

8*x+3, `   `, 8*x-3

8*x+9, `   `, 8*x-9

8*x+27, `   `, 8*x-27

8*x+81, `   `, 8*x-81

16*x+1, `   `, 16*x-1

16*x+3, `   `, 16*x-3

16*x+9, `   `, 16*x-9

16*x+27, `   `, 16*x-27

16*x+81, `   `, 16*x-81

32*x+1, `   `, 32*x-1

32*x+3, `   `, 32*x-3

32*x+9, `   `, 32*x-9

32*x+27, `   `, 32*x-27

32*x+81, `   `, 32*x-81


Notice that when the two numbers are not relatively prime, there may be some duplications among the list of potential factors - for example, (x+5) and (3x + 15).

>    P := 6*x^3+5*x^2-44*x-15 ;
RatDiv( 6, 15);

P := 6*x^3+5*x^2-44*x-15

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+3, `   `, x-3

x+5, `   `, x-5

x+15, `   `, x-15

2*x+1, `   `, 2*x-1

2*x+3, `   `, 2*x-3

2*x+5, `   `, 2*x-5

2*x+15, `   `, 2*x-15

3*x+1, `   `, 3*x-1

3*x+3, `   `, 3*x-3

3*x+5, `   `, 3*x-5

3*x+15, `   `, 3*x-15

6*x+1, `   `, 6*x-1

6*x+3, `   `, 6*x-3

6*x+5, `   `, 6*x-5

6*x+15, `   `, 6*x-15

  3. The Method of Rational Roots


Suppose we want to factor the following polynomial. We look at its leading coefficient and constant term (a.k.a. trailing coeffficient). We find all diviors of each, then form all of the possible divisors using these numbers.

>    P := 5*x^3+18*x^2+7*x-6 ;

P := 5*x^3+18*x^2+7*x-6

>    RatDiv( 5, 6);

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+2, `   `, x-2

x+3, `   `, x-3

x+6, `   `, x-6

5*x+1, `   `, 5*x-1

5*x+2, `   `, 5*x-2

5*x+3, `   `, 5*x-3

5*x+6, `   `, 5*x-6


Its not pretty, but we can perform a synthetic division on each possible factor. If ( ax+b ) is a factor, then we will test -b/a  in the synthetic division. We are looking for a zero remainder. Lets try a few of the 16 possible cases :

>    SynDiv( P,+1);

matrix([[1, ` `, 5, 18, 7, -6], [` `, ` `, 0, 5, 23, 30], [` `, ` `, __, __, __, __], [` `, ` `, 5, 23, 30, 24]])

>    SynDiv( P,+1/5);

matrix([[1/5, ` `, 5, 18, 7, -6], [` `, ` `, 0, 1, 19/5, 54/25], [` `, ` `, __, __, __, __], [` `, ` `, 5, 19, 54/5, -96/25]])

>    SynDiv( P,+6/5);

matrix([[6/5, ` `, 5, 18, 7, -6], [` `, ` `, 0, 6, 144/5, 1074/25], [` `, ` `, __, __, __, __], [` `, ` `, 5, 24, 179/5, 924/25]])

>    SynDiv( P,-3);

matrix([[-3, ` `, 5, 18, 7, -6], [` `, ` `, 0, -15, -9, 6], [` `, ` `, __, __, __, __], [` `, ` `, 5, 3, -2, 0]])


We got lucky! We found a root... x = -3. This means that (x+3) is a factor.

Now we can continue the factoring process on the quotient - which is second degree and easier to deal with. We can do the rational root test on this smaller polynomial,....noting that there are fewer candidates for being rational factors.

>    RatDiv( 5, 2);

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+2, `   `, x-2

5*x+1, `   `, 5*x-1

5*x+2, `   `, 5*x-2

>    SynDiv( 5*x^2 + 3*x - 2, -1);

matrix([[-1, ` `, 5, 3, -2], [` `, ` `, 0, -5, 2], [` `, ` `, __, __, __], [` `, ` `, 5, -2, 0]])

We found another root! And the quotient is a linear term.

.... or in this case, we could have simply factored the quadratic expression ....

>    factor( 5*x^2 + 3*x - 2);

(x+1)*(5*x-2)

>    P = factor(P);

5*x^3+18*x^2+7*x-6 = (5*x-2)*(x+3)*(x+1)


 

  4. The Fast Method of Rational Roots


Instead of doing all of those individually, we can speed up the process by putting the synthetic divisions in one chart. We write the polynomial coefficients at top, and then each of the "bottom lines" on one row - hiding the former middle lines by doing those calculations in our heads.

         Example 4.1 :     

>    P := 5*x^2 + 3*x - 2;

P := 5*x^2+3*x-2

>    RatDiv( 5, 2);

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+2, `   `, x-2

5*x+1, `   `, 5*x-1

5*x+2, `   `, 5*x-2

>    RatRootTest(P);

matrix([[` `, ` `, 5, 3, -2, ` `], [` `, ` `, __, __, __, ` `], [1, `|`, 5, 8, 6, ` `], [2, `|`, 5, 13, 24, ` `], [1/5, `|`, 5, 4, -6/5, ` `], [2/5, `|`, 5, 5, 0, `Root!`], [-1, `|`, 5, -2, 0, `Root!`]...

 
Here is another example.
        

        Example 4.2 :

    

>    P := 2*x^3+17*x^2+27*x-18;

P := 2*x^3+17*x^2+27*x-18

>    RatDiv(2, 18);

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+2, `   `, x-2

x+3, `   `, x-3

x+6, `   `, x-6

x+9, `   `, x-9

x+18, `   `, x-18

2*x+1, `   `, 2*x-1

2*x+2, `   `, 2*x-2

2*x+3, `   `, 2*x-3

2*x+6, `   `, 2*x-6

2*x+9, `   `, 2*x-9

2*x+18, `   `, 2*x-18

>    RatRootTest( P );

matrix([[` `, ` `, 2, 17, 27, -18, ` `], [` `, ` `, __, __, __, __, ` `], [1, `|`, 2, 19, 46, 28, ` `], [2, `|`, 2, 21, 69, 120, ` `], [3, `|`, 2, 23, 96, 270, ` `], [6, `|`, 2, 29, 201, 1188, ` `], [9...


The sweet site of success! We found all four roots : 1/2, -3, -6, -3. Wait a second... this is a third degree polynomial so there are at most three roots. Actually, -3 is a duplicate.

        

        Example 4.3 :

    

>    P := x^3+5*x^2-18*x-72;

P := x^3+5*x^2-18*x-72

>    RatDiv(1, 72);

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+2, `   `, x-2

x+3, `   `, x-3

x+4, `   `, x-4

x+6, `   `, x-6

x+8, `   `, x-8

x+9, `   `, x-9

x+12, `   `, x-12

x+18, `   `, x-18

x+24, `   `, x-24

x+36, `   `, x-36

x+72, `   `, x-72

>    RatRootTest( P);

matrix([[` `, ` `, 1, 5, -18, -72, ` `], [` `, ` `, __, __, __, __, ` `], [1, `|`, 1, 6, -12, -84, ` `], [2, `|`, 1, 7, -4, -80, ` `], [3, `|`, 1, 8, 6, -54, ` `], [4, `|`, 1, 9, 18, 0, `Root!`], [6, `...


Here is about as easy as it gets!
        

        Example 4.4 :

    

>    P := x^5+x^4-2*x^3-2*x^2+x+1;

P := x^5+x^4-2*x^3-2*x^2+x+1

>    RatDiv(1, 1);

`The possible rational binomial divisors are :`

x+1, `   `, x-1

>    RatRootTest( P);

matrix([[` `, ` `, 1, 1, -2, -2, 1, 1, ` `], [` `, ` `, __, __, __, __, __, __, ` `], [1, `|`, 1, 2, 0, -2, -1, 0, `Root!`], [-1, `|`, 1, 0, -2, 0, 1, 0, `Root!`]])


However, we only found two roots in a fifth degree equation. Lets remove these roots to see what remains.

>    P/((x-1)*(x+1)): % = simplify(%);

(x^5+x^4-2*x^3-2*x^2+x+1)/(x-1)/(x+1) = x^3+x^2-x-1

>    P2 := x^3 + x^2 - x  -1;
RatRootTest( P2 );

P2 := x^3+x^2-x-1

matrix([[` `, ` `, 1, 1, -1, -1, ` `], [` `, ` `, __, __, __, __, ` `], [1, `|`, 1, 2, 1, 0, `Root!`], [-1, `|`, 1, 0, -1, 0, `Root!`]])

>    P = ((x-1)^2)*(x+1)^3;

x^5+x^4-2*x^3-2*x^2+x+1 = (x-1)^2*(x+1)^3



 

  5. When the Method of Rational Roots Fails


Sometimes the test fails to find any roots at all.

>    P := 3*x^3+5*x^2-18*x + 14;

P := 3*x^3+5*x^2-18*x+14

>    RatDiv(3, 14);

`The possible rational binomial divisors are :`

x+1, `   `, x-1

x+2, `   `, x-2

x+7, `   `, x-7

x+14, `   `, x-14

3*x+1, `   `, 3*x-1

3*x+2, `   `, 3*x-2

3*x+7, `   `, 3*x-7

3*x+14, `   `, 3*x-14

>    RatRootTest( P);

matrix([[` `, ` `, 3, 5, -18, 14, ` `], [` `, ` `, __, __, __, __, ` `], [1, `|`, 3, 8, -10, 4, ` `], [2, `|`, 3, 11, 4, 22, ` `], [7, `|`, 3, 26, 164, 1162, ` `], [14, `|`, 3, 47, 640, 8974, ` `], [1/...


Evidently, this polynomial does not have any binomials with integer coefficients, and thus no rational roots. Any roots are irrational. Since all odd-degreed polynomials have at least one real root.

>    plot( P, x = -5..4, y = -50..120,  color = blue, thickness = 2 );

[Maple Plot]


We can use Maple's floating-point solving function to find a decimal approximation to this irrational root.

>    fsolve( P = 0, x);

-3.656573460

>   


         © 2002 Waterloo Maple Inc