17.2: El algoritmo de división
- Page ID
- 111107
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\).