La guerra mundial

ALGORITMO DE DESCARTE DE RAÍCES ENTERAS DE POLINOMIOS.
¿A quién no le ha ocurrido alguna vez, en su periplo como estudiante, encontrarse con un polinomio hostil, que se resiste a mostrar sus raíces enteras, bien porque no las tenga, bien porque el término independiente posee numerosos divisores y en los ensayos rigen las leyes de Murphy?. Motivados por esta dificultad, desarrollaremos unprocedimiento simplificador de la búsqueda de raíces enteras en ecuaciones polinómicas, estableciendo criterios de eliminación entre los candidatos a raíz entera seleccionados mediante el burdo y usual criterio de los divisores del término independiente. Obviamente, para que el algoritmo de descarte sea interesante en la práctica, debe ser rigurosamente fiable, sencillo y rápido. Comenzaremos enunciandoy probando las propiedades subyacentes al mismo. Por pragmatismo, la sencillez y eficiencia del mismo se hará patente a través de un ejemplo. Sea p ( x) = an x n + a n − 1xn − 1 + L + a1x + a 0

un polinomio de coeficientes enteros. FUNDAMENTACIÓN. Propiedades de las raíces enteras de un polinomio con coeficientes enteros: ¨ Si x0 es una raíz entera de p(x), x0 ≠ 0, entonces x0 es un divisor dea 0 :
n n n p ( x0 ) = a n xn + an − 1x0 − 1 + L + a1 x0 + a0 = 0 ⇒ a0 = − x0 ( a n x0 − 1 + a n − 1x0 − 2 + L + a1 ) ⇒ 0

⇒

a0 n n = −( an x0 − 1 + a n − 1x0 − 2 + L + a1 ) ∈ Ζ . x0

¨ Si x0 es una raíz entera de p(x) , x0 ∉ {−1, 0, 1}, − entonces x0 – 1 es un divisor de p(+1) :
n a0 = −a n x0 − a n − 1xn − 1 − L − a1 x0  0 n a ( xn − 1) + a n − 1( x0 − 1 − 1) + L + a1( x0 − 1) p ( +1) ⇒ =− n 0 . p ( +1) a n + a n − 1 + L + a1 + a0  x0 − 1 x0 − 1 =  x0 − 1 x0 − 1  k Por el teorema del resto, es inmediato que los binomios x0 − 1, considerados como polinomios en x0 , k son divisibles por x0 – 1. En efecto, sea pk ( x0 ) = x0 − 1. Entonces, el resto de la división es pk (1) = 0 .

Sea Se tiene:

k x0 − 1 , k = 1, 2 , L , n . x0 − 1 p ( +1) xn − 1 xn − 1 − 1 x −1 n = −a n 0 −an − 1 0 − L − a1 0 = ∑ a k q k ( x0 ), x0 − 1 x0 − 1 x0 − 1 x0 − 1 k = 1

q k ( x0 ) =

y considerando, de nuevo, la indeterminada x0 como constante entera, resulta que
n p ( +1) = − ∑ ak qk ( x0 ) ∈ Ζ ~ {−1, 0 , 1}, − x0 − 1 k =1

es decir, x0 – 1 divide a p(+1) .
Observación: Aunque la propiedad se verifica, trivialmente, para x0 = 0, no se considera esta posibilidad por carecer deinterés práctico en la aplicación del algoritmo.

¨ Si x0 es una raíz entera de p(x) , x0 ∈ Ζ ~ {−1, 0, 1}, − entonces x0 + 1 es un divisor de p(–1) . La prueba de esta propiedad es análoga a la de la anterior.

Jesús Álvarez Lobo. Oviedo. Asturias. España. lobo@matematicas.net.

IMPLEMENTACIÓN DEL ALGORITMO. Seleccionados los candidatos iniciales a raíces enteras por el bien conocido criteriode los divisores del término independiente, si éstos son numerosos puede resultar rentable aplicar el algoritmo de descarte a fin de reducir el número de divisiones necesarias para descubrir las raíces enteras. Este algoritmo, fundamentado en las tres propiedades probadas en el anterior epígrafe, es un “tamiz” mucho más fino, ya que involucra dos nuevos criterios, determinando un “filtrado” muchomás selectivo; con frecuencia, los enteros que lo atraviesan son únicamente las raíces del polinomio. Optimizaremos el diseño del algoritmo, de forma que resulte minimizado el volumen de cálculos y escritura, y que su ejecución resulte intuitiva y nemotécnica. Si el término independiente, a0 , tiene d divisores positivos, mayores que la unidad, a0 también tiene d divisores negativos menores quela unidad. Para aplicar las dos últimas propiedades, estos 2d divisores deben ser incrementados en ±1, lo que produce otros 4d números a considerar, y el número de divisores sería 6d. Así pues, la aplicación directa de las propiedades anteriores tendría el siguiente precio: sería necesario efectuar 4d pruebas “extra” de divisibilidad, y escribir el triple de divisores de valor absoluto mayor...