17.2: El algoritmo de división

Recordemos 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 enteros únicos\(q\) y\(r\) tal que\(a = bq + r\text{,}\) donde\(0 \leq r \lt b\text{.}\) El algoritmo por el que\(r\) se encuentran\(q\) y es simplemente largo división. Un teorema similar existe para los polinomios. El algoritmo de división para polinomios tiene varias consecuencias importantes. Dado que su prueba es muy similar a la prueba correspondiente para enteros, vale la pena revisar el Teorema 2.9 en este punto.

Teorema\(17.6\). Division Algorithm

Dejar\(f(x)\) y\(g(x)\) ser polinomios en\(F[x]\text{,}\) donde\(F\) es un campo y\(g(x)\) es un polinomio distinto de cero. Entonces existen polinomios únicos de\(q(x), r(x) \in F[x]\) tal manera que

\[ f(x) = g(x) q(x) + r(x)\text{,} \nonumber \]

donde cualquiera\(\deg r(x) \lt \deg g(x)\) o\(r(x)\) es el polinomio cero.

Prueba

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

\[ 0 = 0 \cdot g(x) + 0; \nonumber \]

de ahí que ambos\(q\) y también\(r\) deben ser el polinomio cero. Ahora supongamos que no\(f(x)\) es el polinomio cero y eso\(\deg f(x) = n\) y\(\deg g(x) = m\text{.}\) si\(m \gt n\text{,}\) entonces podemos dejar\(q(x) = 0\) y\(r(x) = f(x)\text{.}\) por lo tanto, podemos suponer que\(m \leq n\) y proceder por inducción en\(n\text{.}\) Si

\ begin {alinear*} 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*}

el polinomio

\[ f'(x) = f(x) - \frac{a_n}{b_m} x^{n - m} g(x) \nonumber \]

tiene grado menor\(n\) o es el polinomio cero. Por inducción, existen polinomios\(q'(x)\) y\(r(x)\) tal que

\[ f'(x) = q'(x) g(x) + r(x)\text{,} \nonumber \]

donde\(r(x) = 0\) o el grado de\(r(x)\) es menor que el grado de\(g(x)\text{.}\) Ahora vamos

\[ q(x) = q'(x) + \frac{a_n}{b_m} x^{n - m}\text{.} \nonumber \]

Entonces

\[ f(x) = g(x) q(x) + r(x)\text{,} \nonumber \]

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

Para demostrar eso\(q(x)\) y\(r(x)\) son únicos, supongamos que existen otros dos polinomios\(q_1(x)\) y\(r_1(x)\) tal 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{,}\) para que

\[ f(x) = g(x) q(x) + r(x) = g(x) q_1(x) + r_1(x)\text{,} \nonumber \]

y

\[ g(x) [q(x) - q_1(x) ] = r_1(x) - r(x)\text{.} \nonumber \]

Si no\(q(x) - q_1(x)\) es el polinomio cero, entonces

\[ \deg( g(x) [q(x) - q_1(x) ] )= \deg( r_1(x) - r(x) ) \geq \deg g(x)\text{.} \nonumber \]

Sin embargo, los grados de ambos\(r(x)\) y\(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{.}\)

Ejemplo\(17.7\)

El algoritmo de división simplemente formaliza la división larga de polinomios, una tarea que conocemos desde la secundaria.

Solución

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\)

Por lo tanto,\(x^3 - x^2 + 2 x - 3 = (x - 2) (x^2 + x + 4 ) + 5\text{.}\)

Que\(p(x)\) sea 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 de la evaluación homomorfismo\(\phi_{\alpha}\text{.}\) Todo lo que realmente estamos diciendo aquí es que\(\alpha\) es un cero de\(p(x)\) si\(p(\alpha) = 0\text{.}\)

Corolario\(17.8\)

\(F\)Déjese ser un campo. Un elemento\(\alpha \in F\) es un cero de\(p(x) \in F[x]\) si y solo si\(x - \alpha\) es un factor de\(p(x)\) in\(F[x]\text{.}\)

Prueba

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

\[ p(x) = (x -\alpha) q(x) + r(x) \nonumber \]

y el grado de\(r(x)\) debe ser menor que el grado de\(x -\alpha\text{.}\) Dado que el grado de\(r(x)\) es inferior a 1,\(r(x) = a\) por\(a \in F\text{;}\) lo tanto,

\[ p(x) = (x -\alpha) q(x) + a\text{.} \nonumber \]

Pero

\[ 0 = p(\alpha) = 0 \cdot q(\alpha) + a = a; \nonumber \]

en consecuencia,\(p(x) = (x - \alpha) q(x)\text{,}\) y\(x - \alpha\) es un factor de\(p(x)\text{.}\)

Por el contrario, supongamos que\(x - \alpha\) es un factor de\(p(x)\text{;}\) decir\(p(x) = (x - \alpha) q(x)\text{.}\) Entonces\(p( \alpha ) = 0 \cdot q(\alpha) = 0\text{.}\)

 

Corolario\(17.9\)

\(F\)Déjese ser un campo. Un polinomio distinto de cero\(p(x)\) de grado\(n\) en\(F[x]\) puede tener como máximo ceros\(n\) distintos en\(F\text{.}\)

Prueba

Utilizaremos inducción en el grado de\(p(x)\text{.}\) Si\(\deg p(x) = 0\text{,}\) entonces\(p(x)\) es un polinomio constante y no tiene ceros. Vamos\(\deg p(x) = 1\text{.}\) Entonces\(p(x) = ax + b\) para algunos\(a\) y\(b\) en\(F\text{.}\) Si\(\alpha_1\) y\(\alpha_2\) son ceros de\(p(x)\text{,}\) entonces\(a\alpha_1 + b = a\alpha_2 +b\) o\(\alpha_1 = \alpha_2\text{.}\)

Ahora supongamos que\(\deg p(x) \gt 1\text{.}\) si\(p(x)\) no tiene un cero en\(F\text{,}\) entonces ya estamos hechos. Por otro lado, si\(\alpha\) es un cero de\(p(x)\text{,}\) entonces\(p(x) = (x - \alpha ) q(x)\) para algunos\(q(x) \in F[x]\) por Corolario 17.8. El grado de\(q(x)\) es\(n-1\) por la Proposición 17.4. \(\beta\)Sea algún otro cero de\(p(x)\) eso es distinto de\(\alpha\text{.}\) Entonces\(p(\beta) = (\beta - \alpha) q(\beta) = 0\text{.}\) Desde\(\alpha \neq \beta\) y\(F\) es un campo,\(q(\beta ) = 0\text{.}\) Por nuestra hipótesis de inducción,\(q(x)\) puede tener a lo sumo\(n - 1\) ceros en\(F\) que son distintos de\(\alpha\text{.}\) Por lo tanto, \(p(x)\)tiene como máximo ceros\(n\) distintos en\(F\text{.}\)

\(F\)Déjese ser un campo. Un polinomio monico\(d(x)\) es un mayor divisor común de polinomios\(p(x), q(x) \in F[x]\) si divide\(d(x)\) uniformemente ambos\(p(x)\) y\(q(x)\text{;}\) y, si para cualquier otro polinomio\(d'(x)\) dividiendo ambos\(p(x)\) y\(q(x)\text{,}\)\(d'(x) \mid d(x)\text{.}\) escribimos\(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ón\(17.10\)

\(F\)Sea un campo y supongamos que\(d(x)\) es un mayor divisor común de dos polinomios\(p(x)\) y\(q(x)\) en\(F[x]\text{.}\) Entonces existen polinomios\(r(x)\) y\(s(x)\) de tal manera que

\[ d(x) = r(x) p(x) + s(x) q(x)\text{.} \nonumber \]

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

Prueba

Dejar\(d(x)\) ser el polinomio mónico de menor grado en el conjunto

\[ S = \{ f(x) p(x) + g(x) q(x) : f(x), g(x) \in F[x] \}\text{.} \nonumber \]

Podemos escribir\(d(x) = r(x) p(x) + s(x) q(x)\) para dos polinomios\(r(x)\) y\(s(x)\) en\(F[x]\text{.}\) Necesitamos mostrar que\(d(x)\) divide ambos\(p(x)\) y Primero\(q(x)\text{.}\) mostraremos que\(d(x)\) divide\(p(x)\text{.}\) Por el algoritmo de división, existen polinomios\(a(x)\) y\(b(x)\) tal 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 {alinear*} 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))\ final {alinear*}

es una combinación lineal de\(p(x)\) y\(q(x)\) y por lo tanto debe estar en\(S\text{.}\) Sin embargo,\(b(x)\) debe ser el polinomio cero ya que\(d(x)\) fue elegido para ser de menor grado; consecuentemente,\(d(x)\) divide\(p(x)\text{.}\) Un argumento simétrico muestra que también\(d(x)\) debe dividir\(q(x)\text{;}\) por lo tanto,\(d(x)\) es un divisor común de\(p(x)\) y\(q(x)\text{.}\)

Para demostrar que\(d(x)\) es un mayor divisor común 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{.}\) Desde\(d'(x)\) es un divisor común de\(p(x)\) y\(q(x)\text{,}\) existen polinomios\(u(x)\) y \(v(x)\)tal que\(p(x) = u(x) d'(x)\) y\(q(x) = v(x) d'(x)\text{.}\) Por lo tanto,

\ begin {alinear*} 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)]\ texto {.} \ end {alinear*}

Dado que\(d'(x) \mid d(x)\text{,}\)\(d(x)\) es un mayor divisor común de\(p(x)\) y\(q(x)\text{.}\)

Por último, debemos demostrar que el mayor divisor común de\(p(x)\) y\(q(x)\) es único. Supongamos que\(d'(x)\) es otro mayor divisor común de\(p(x)\) y\(q(x)\text{.}\) acabamos de demostrar que existen polinomios\(u(x)\) y\(v(x)\) en\(F[x]\) tal que\(d(x) = d'(x)[r(x) u(x) + s(x) v(x)]\text{.}\) Desde

\[ \deg d(x) = \deg d'(x) + \deg[r(x) u(x) + s(x) v(x)] \nonumber \]

y\(d(x)\) y\(d'(x)\) son ambos mayores divisores comunes,\(\deg d(x) = \deg d'(x)\text{.}\) ya que\(d(x)\) y\(d'(x)\) son ambos polinomios monicos del mismo grado, debe darse el caso que\(d(x) = d'(x)\text{.}\)

Observe la similitud entre la prueba de Proposición\(17.10\) y la prueba del Teorema\(2.10\).