Rational root theorem

related topics
{math, number, function}

In algebra, the rational root theorem (or rational root test) states a constraint on rational solutions (or roots) of the polynomial equation

with integer coefficients.

If a0 and an are nonzero, then each rational solution x, when written as a fraction x = p/q in lowest terms (i.e., the greatest common divisor of p and q is 1), satisfies

Thus, a list of possible rational roots of the equation can be derived using the formula x = \pm \frac{p}{q}.

The rational root theorem is a special case (for a single linear factor) of Gauss's lemma on the factorization of polynomials. The integral root theorem is a special case of the rational root theorem if the leading coefficient an = 1.

Contents

Proof

Let P(x) = anxn + an-1xn-1 + ... + a1x + a0 for some a0, ..., anZ, and suppose P(p/q) = 0 for some coprime p, qZ:

Shifting the constant term and multiplying by qn,

Shifting the leading term and multiplying by qn,

All terms in these equations are integers, which implies p | a0qn and q | anpn. But p, qn and q, pn are coprime. Hence, by Euclid's lemma, p | a0 and q | an.[1]

Example

For example, every rational solution of the equation

must be among the numbers symbolically indicated by

which gives the list of possible answers:

These root candidates can be tested using the Horner scheme (for instance). In this particular case there is exactly one rational root. If a root candidate does not satisfy the equation, it can be used to shorten the list of remaining candidates. For example, x = 1 does not satisfy the equation as the left hand side equals 1. This means that substituting x = 1 + t yields a polynomial in t with constant term 1, while the coefficient of t3 remains the same as the coefficient of x3. Applying the rational root theorem thus yields the following possible roots for t:

Therefore,

Root candidates that do not occur on both lists are ruled out. The list of rational root candidates has thus shrunk to just x = 2 and x = 2/3.

If a root r1 is found, the Horner scheme will also yield a polynomial of degree n − 1 whose roots, together with r1, are exactly the roots of the original polynomial. It may also be the case that none of the candidates is a solution; in this case the equation has no rational solution. If the equation lacks a constant term a0, then 0 is one of the rational roots of the equation.

Full article ▸

related documents
Entire function
Equation
Sum rule in integration
Exponential time
Hyperplane
Unification
Euler number
Noetherian ring
EXPTIME
Linear span
Field of fractions
Most significant bit
Dirichlet's theorem on arithmetic progressions
Special functions
Automorphism
Minkowski's theorem
Condition number
Null set
Infinite set
Ceva's theorem
Complete graph
Canonical LR parser
Bernoulli's inequality
NP-equivalent
Matrix addition
Single precision
Cipher
Algebraic closure
Linear prediction
Constant term