Rejection Theorem

q − p Rejection Lemma If

Proposition: Let f (x) be a polynomial of degree n with integer coefficients. is a rational root of f (x), then q − p must be a factor of f (1)1 .

p q

Proof: It is possible2 to write f (x) = s(x)(qx − p) for some (n − 1)st degree polynomial with integer coefficients. Hence f (1) = s(1)(q − p). Since s(x) ∈ Z[X], s(1) ∈ Z. It is also interesting to consider f (−1).

Example 1: Consider the polynomial f (x) = 3x3 −5x2 +5x−2. From the rational root theorem, the pool of rational root candidates is the set {±1, ±2, ± 13 , ± 32 }. Meanwhile, f (1) = 1. Hence, q − p Rejection Lemma tells us that whenever pq is a root, then q − p = ±1, the only factors of 1. (a)

1 1

(b)

−1 1

(c)

2 1

(d)

−2 1

is not a root since 1 − 1 = 0 6 | 1. is not a root since 1 − −1 = 2 6 | 1.

may be a root. is not a root since 1 − −2 = 3 6 | 1.

Doing this till the last(not very difficult to do mentally), we will only be left with 2 and 23 as possible roots. Example 2: Consider the polynomial f (x) = 6x3 −13x2 +2x+8. Note that f (1) = 3. The possible rational roots are ±1, ±2, ±4, ±8, ± 12 , ± 13 , ± 23 , ± 43 , ± 38 , ± 61 . But using our lemma, the pool is reduced to ±2, 4, ± 12 , 32 , 43 .

1 Note that f (1) is very simple to compute because it is just the sum of the coefficients of the polynomial f (x). 2 Polynomials in Z[X] which are reducible in Q are reducible in Z