AATA El Algoritmo de División

Sección17.2El Algoritmo de División

Recuerde que el algoritmo de división para enteros (Teorema 2.9) dice que si $a$ y $b$ son enteros con $b \gt 0\text{,}$ entonces existen únicos enteros $q$ y $r$ tales que $a = bq+r\text{,}$ con $0 \leq r \lt b\text{.}$ Un teorema similar existe para polinomios. El algoritmo de división para polinomios tiene varias consecuencias importantes. Como su demostración es muy similar a la demostración correspondiente para los enteros, resulta conveniente revisar el Teorema 2.9 antes de seguir.

Teorema17.6Algoritmo de División

Sean $f(x)$ y $g(x)$ polinomios en $F[x]\text{,}$ donde $F$ es un cuerpo y $g(x)$ es un polinomio distinto de cero. Entonces existen polinomios únicos $q(x), r(x) \in F[x]$ tales que

$\begin{equation*} f(x) = g(x) q(x) + r(x), \end{equation*}$

con $\deg r(x) \lt \deg g(x)$ o $r(x)=0\text{.}$

Demostración

Primero demostraremos la existencia de $q(x)$ y $r(x)\text{.}$ Si $f(x)$ es el polinomio cero, entonces

\begin{equation*} 0 = 0 \cdot g(x) + 0; \end{equation*}

luego, tanto $q$ como $r$ también son el polinomio cero. Ahora supongamos que $f(x)$ no es polinomio cero y que $\deg f(x) = n$ y $\deg g(x) = m\text{.}$ Si $m \gt n\text{,}$ entonces $q(x) = 0$ y $r(x) = f(x)\text{.}$ Podemos ahora suponer que $m \leq n$ y proceder por inducción en $n\text{.}$ Si

\begin{align*} f(x) & = a_n x^n + a_{n-1} x^{n - 1} + \cdots + a_1 x + a_0\\ g(x) & = b_m x^m + b_{m-1} x^{m - 1} + \cdots + b_1 x + b_0 \end{align*}

entonces el polinomio

\begin{equation*} f'(x) = f(x) - \frac{a_n}{b_m} x^{n - m} g(x) \end{equation*}

tiene grado menor a $n$ o es el polinomio cero. Por la hipótesis de inducción, existens polinomios $q'(x)$ y $r(x)$ tales que

\begin{equation*} f'(x) = q'(x) g(x) + r(x), \end{equation*}

donde $r(x) = 0$ o el grado de $r(x)$ es menor al grado de $g(x)\text{.}$ Ahora, sea

\begin{equation*} q(x) = q'(x) + \frac{a_n}{b_m} x^{n - m}. \end{equation*}

Entonces

\begin{equation*} f(x) = g(x) q(x) + r(x), \end{equation*}

con $r(x)$ el polinomio cero o $\deg r(x) \lt \deg g(x)\text{.}$

Para mostrar que $q(x)$ y $r(x)$ son únicos, supongamos que además existen $q_1(x)$ y $r_1(x)$ tales que $f(x) = g(x) q_1(x) + r_1(x)$ con $\deg r_1(x) \lt \deg g(x)$ o $r_1(x) = 0\text{,}$ de manera que

\begin{equation*} f(x) = g(x) q(x) + r(x) = g(x) q_1(x) + r_1(x), \end{equation*}

\begin{equation*} g(x) [q(x) - q_1(x) ] = r_1(x) - r(x). \end{equation*}

Si $g(x)$ no es el polinomio cero, entonces

\begin{equation*} \deg( g(x) [q(x) - q_1(x) ] )= \deg( r_1(x) - r(x) ) \geq \deg g(x). \end{equation*}

Pero, los grados tanto de $r(x)$ como de $r_1(x)$ son estrictamente menores que el grado de $g(x)\text{;}$ por lo tanto, $r(x) = r_1(x)$ y $q(x) = q_1(x)\text{.}$

Ejemplo17.7

El algoritmo de división meramente formaliza la división larga de polinomios, una tarea con la que probablemente estamos familiarizados desde el colegio. Por ejemplo, supongamos que dividimos $x^3 - x^2 + 2 x - 3$ por $x - 2\text{.}$

			$x^2$	$+$	$x$	$+$	$4$
$x$	$-$	$2$	$x^3$	$-$	$x^2$	$+$	$2x$	$-$	$3$
			$x^3$	$-$	$2x^2$
					$x^2$	$+$	$2x$	$-$	$3$
					$x^2$	$-$	$2x$
							$4x$	$-$	$3$
							$4x$	$-$	$8$
									$5$

Luego, $x^3 - x^2 + 2 x - 3 = (x - 2) (x^2 + x + 4 ) + 5\text{.}$

Sea $p(x)$ un polinomio en $F[x]$ y $\alpha \in F\text{.}$ Decimos que $\alpha$ es un cero o raíz de $p(x)$ si $p(x)$ está en el núcleo del homomorfismo de evaluación $\phi_{\alpha}\text{.}$ Lo único que estamos dicendo realmente es que $\alpha$ es un cero de $p(x)$ si $p(\alpha) = 0\text{.}$

Corolario17.8

Sea $F$ un cuerpo. Un elemento $\alpha \in F$ es un cero de $p(x) \in F[x]$ si y solo si $x - \alpha$ divide a $p(x)$ en $F[x]\text{.}$

Demostración

Supongamos que $\alpha \in F$ y $p( \alpha ) = 0\text{.}$ Por el algoritmo de la división, existen polinomios $q(x)$ y $r(x)$ tales que

\begin{equation*} p(x) = (x -\alpha) q(x) + r(x) \end{equation*}

y el grado de $r(x)$ es menor que el grado de $x -\alpha\text{.}$ Como el grado de $r(x)$ es menor a 1, $r(x) = a$ para algún $a \in F\text{;}$ por lo tanto,

\begin{equation*} p(x) = (x -\alpha) q(x) + a. \end{equation*}

Pero

\begin{equation*} 0 = p(\alpha) = 0 \cdot q(\alpha) + a = a; \end{equation*}

Por ende, $p(x) = (x - \alpha) q(x)\text{,}$ y $x - \alpha$ es un factor de $p(x)\text{.}$

Recíprocamente, supongamos que $x - \alpha$ es un factor de $p(x)\text{;}$ digamos $p(x) = (x - \alpha) q(x)\text{.}$ Entonces $p( \alpha ) = 0 \cdot q(\alpha) = 0\text{.}$

Corolario17.9

Sea $F$ un cuerpo. Un polinomio $p(x)$ distinto de cero y de grado $n$ en $F[x]$ puede tener a lo sumo $n$ ceros distintos en $F\text{.}$

Demostración

Procederemos por inducción sobre el grado de $p(x)\text{.}$ Si $\deg p(x) = 0\text{,}$ entonces $p(x)$ es un polinomio constante y no tiene ceros. Si $\deg p(x) = 1\text{,}$ entonces $p(x) = ax +b$ para ciertos $a$ y $b$ en $F\text{.}$ Si $\alpha_1$ y $\alpha_2$ so ceros de $p(x)\text{,}$ entonces $a\alpha_1 + b = a\alpha_2 +b$ y $\alpha_1 = \alpha_2\text{.}$

Ahora supongamos que $\deg p(x) \gt 1\text{.}$ Si $p(x)$ no tiene ceros en $F\text{,}$ estamos listos. Por otra parte, si $\alpha$ es un cero de $p(x)\text{,}$ entonces $p(x) = (x - \alpha ) q(x)$ para cierto $q(x) \in F[x]$ por el Corolario 17.8. El grado de $q(x)$ es $n-1$ por la Proposición 17.4. Sea $\beta$ algún otro cero de $p(x)$ distinto de $\alpha\text{.}$ Entonces $p(\beta) = (\beta - \alpha) q(\beta) = 0\text{.}$ Como $\alpha \neq \beta$ y $F$ es un cuerpo, $q(\beta ) = 0\text{.}$ Por la hipótesis de inducción, $q(x)$ puede tener a lo sumo $n -1$ ceros distintos en $F\text{.}$ Por lo tanto, $p(x)$ tiene a lo sumo $n$ ceros distintos en $F\text{.}$

Sea $F$ un cuerpo. Un polinomio mónico $d(x)$ es un máximo común divisor de los polinomios $p(x), q(x) \in F[x]$ si $d(x)$ divide tanto a $p(x)$ como a $q(x)\text{;}$ y, si para cualquier otro polinomio $d'(x)$ que divida tanto a $p(x)$ como a $q(x)\text{,}$ $d'(x) \mid d(x)\text{.}$ Escribiremos $d(x) = \gcd( p(x), q( x))\text{.}$ Dos polinomios $p(x)$ y $q(x)$ son relativamente primos si $\gcd(p(x), q(x) ) = 1\text{.}$

Proposición17.10

Sea $F$ un cuerpo y supongamos que $d(x)$ es un máximo común divisor de dos polinomios $p(x)$ y $q(x)$ en $F[x]\text{.}$ Entonces existen polinomios $r(x)$ y $s(x)$ tales que

$\begin{equation*} d(x) = r(x) p(x) + s(x) q(x). \end{equation*}$

Además, el máximo común divisor de dos polinomios es único.

Demostración

Sea $d(x)$ el polinomio mónico de menor grado en el conjunto

\begin{equation*} S = \{ f(x) p(x) + g(x) q(x) : f(x), g(x) \in F[x] \}. \end{equation*}

Podemos escribir $d(x) = r(x) p(x) + s(x) q(x)$ para dos polinomios $r(x)$ y $s(x)$ en $F[x]\text{.}$ Debemos demostrar que $d(x)$ divide a $p(x)$ y a $q(x)\text{.}$ Primero mostraremos que $d(x)$ divide a $p(x)\text{.}$ Por el algoritmo de división, existen polinomios $a(x)$ y $b(x)$ tales que $p(x) = a(x) d(x) + b(x)\text{,}$ donde $b(x)$ es el polinomio cero o $\deg b(x) \lt \deg d(x)\text{.}$ Por lo tanto,

\begin{align*} b(x) & = p(x) - a(x) d(x)\\ & = p(x) - a(x)( r(x) p(x) + s(x) q(x)) \\ & = p(x) - a(x) r(x) p(x) - a(x) s(x) q(x)\\ & = p(x)( 1 - a(x) r(x) ) + q(x) ( - a(x) s(x) ) \end{align*}

es una combinación lineal de $p(x)$ y $q(x)$ y por lo tanto está en $S\text{.}$ Entonces, $b(x)$ debe ser el polinomio cero pues $d(x)$ fue elegido de grado minimal; Concluimos que $d(x)$ divide a $p(x)\text{.}$ Un argumento simétrico muestra que $d(x)$ también divide a $q(x)\text{;}$ luego, $d(x)$ es un divisor común de $p(x)$ y $q(x)\text{.}$

Para mostrar que $d(x)$ es un máximo común divisor de $p(x)$ y $q(x)\text{,}$ supongamos que $d'(x)$ es otro divisor común de $p(x)$ y $q(x)\text{.}$ Mostraremos que $d'(x) \mid d(x)\text{.}$ Como $d'(x)$ es un divisor común de $p(x)$ y $q(x)\text{,}$ existen polinomios $u(x)$ y $v(x)$ tales que $p(x) = u(x) d'(x)$ y $q(x) = v(x) d'(x)\text{.}$ Por lo tanto,

\begin{align*} d(x) & = r(x) p(x) + s(x) q(x)\\ & = r(x) u(x) d'(x) + s(x) v(x) d'(x)\\ & = d'(x) [r(x) u(x) + s(x) v(x)]. \end{align*}

Como $d'(x) \mid d(x)\text{,}$ $d(x)$ es un máximo común divisor de $p(x)$ y $q(x)\text{.}$

Finalmente, debemos mostrar que el máximo común divisor de $p(x)$ y $q(x)$ es único. Supongamos que $d'(x)$ también es un máximo común divisor de $p(x)$ y $q(x)\text{.}$ Acabamos de mostrar que existen polinomios $u(x)$ y $v(x)$ en $F[x]$ tales que $d(x) = d'(x)[r(x) u(x) + s(x) v(x)]\text{.}$ Como

\begin{equation*} \deg d(x) = \deg d'(x) + \deg[r(x) u(x) + s(x) v(x)] \end{equation*}

y $d(x)$ y $d'(x)$ son ambos máximo común divisor, $\deg d(x) = \deg d'(x)\text{.}$ Como $d(x)$ y $d'(x)$ son ambos polinomios mónicos del mismo grado, se debe tener que $d(x) =~d'(x)\text{.}$

Notemos la similaridad entre la demostración de la Proposición 17.10 y la demostración del Teorema 2.10.