Archivo de la etiqueta: divisibilidad

Álgebra Superior II: El criterio de la raíz racional para polinomios de coeficientes enteros

Introducción

En esta entrada veremos el criterio de la raíz racional. Este es un método que nos permite determinar las únicas raíces racionales que puede tener un polinomio con coeficientes enteros. Es una más de las herramientas que podemos usar cuando estamos estudiando polinomios en \mathbb{R}[x].

Si encontramos una raíz con este método, luego podemos encontrar su multiplicidad mediante el teorema de derivadas y multiplicidad. Esto puede ayudarnos a factorizar el polinomio. Otras herramientas que hemos visto que nos pueden ayudar son el algoritmo de Euclides, la fórmula cuadrática, el teorema del factor y propiedades de continuidad y diferenciabilidad de polinomios.

El criterio de la raíz racional

Si un polinomio p(x) en \mathbb{R}[x] cumple que todos sus coeficientes son números enteros, entonces decimos que es un polinomio sobre los enteros. Al conjunto de polinomios sobre los enteros se le denota \mathbb{Z}[x].

Teorema (criterio de la raíz racional). Tomemos un polinomio p(x) en \mathbb{Z}[x] de la forma

    \[p(x)=a_0+a_1x+\ldots+a_nx^n.\]

Supongamos que el número \frac{p}{q} es número racional simplificado, es decir con p y q\neq 0 enteros primos relativos. Si \frac{p}{q} es raíz de p(x), entonces p divide a a_0, y q divide a a_n.

Demostración. Por definición, si \frac{p}{q} es una raíz, tenemos que

    \[0=a_0+a_1\cdot \frac{p}{q} + \ldots + a_n \cdot \frac{p^n}{q^n}.\]

Multiplicando ambos lados de esta igualdad por q^n, tenemos que

    \[0=a_0q^n+a_1pq^{n-1}+\ldots+a_{n-1}p^{n-1}q+a_np^n.\]

Despejando a_0q^n, tenemos que

    \begin{align*}a_0q^n&=-(a_1pq^{n-1}+\ldots+a_{n-1}p^{n-1}q+a_np^n)\\&=-p(a_1q^{n-1}+\ldots+a_{n-1}p^{n-2}q+a_np^{n-1})\end{align*}

Esto muestra que a_0q^n es múltiplo de p. Pero como \MCD{p,q}=1, tenemos que p debe dividir a a_0.

De manera similar, tenemos que

    \begin{align*}a_np^n&=-(a_0q^n+a_1pq^{n-1}+\ldots+a_{n-1}p^{n-1}q)\\&=-q(a_0q^{n-1}+a_1pq^{n-2}+\ldots+a_{n-1}p^{n-1}).\end{align*}

De aquí, q divide a a_np^n, y como \MCD{p,q}=1, entonces q divide a a_n.

\square

Como cualquier natural tiene una cantidad finita de divisores, el criterio de la raíz racional nos permite restringir la cantidad posible de raíces de un polinomio con coeficientes enteros a una cantidad finita de candidatos. Veamos un par de ejemplos.

Aplicación directa del criterio de la raíz racional

Ejercicio. Usa el criterio de la raíz racional para enlistar a todos los posibles números racionales que son candidatos a ser raíces del polinomio

    \[h(x)=2x^3-x^2+12x-6.\]

Después, encuentra las raíces racionales de p(x).

Solución. El polinomio h(x) tiene coeficientes enteros, así que podemos usar el criterio de la raíz racional. Las raíces racionales son de la forma \frac{p}{q} con p divisor de -6, con q divisor de 2 y además \MCD{p,q}=1. Los divisores enteros de -6 son

    \[-6,-3,-2,-1,1,2,3,6.\]

Los divisores enteros de 2 son

    \[-2,-1,1,2.\]

Pareciera que hay muchas posibilidades por considerar. Sin embargo, nota que basta ponerle el signo menos a uno de p o q para considerar todos los casos. Así, sin pérdida de generalidad, q>0. Si q=1, obtenemos a los candidatos

    \[-6,-3,-2,-1,1,2,3,6.\]

Si q=2, por la condición de primos relativos basta usar los valores -3,-1,1,3 para p. De aquí, obtenemos al resto de los candidatos

    \[-\frac{3}{2},-\frac{1}{2},\frac{1}{2},\frac{3}{2}.\]

En el peor de los casos, ya solo bastaría evaluar el polinomio en estos 12 candidatos para determinar si son o no son raíz. Sin embargo, a veces podemos hacer algunos trucos para disminuir todavía más la lista.

Observa que si evaluamos

    \[h(x)=2x^3-x^2+12x-6\]

en un número negativo, entonces la expresión quedará estrictamente negativa, así que ninguno de los candidatos negativos puede ser raíz. De este modo, sólo nos quedan los candidatos

    \[1,2,3,6,\frac{1}{2},\frac{3}{2}.\]

Si evaluamos en x=2 o x=6, entonces la parte de la expresión 2x^3-x^2+12x es múltiplo de 4, pero -6 no. De esta forma, h(x) no sería un múltiplo de 4, y por lo tanto no puede ser 0. Si evaluamos en x=1 o x=3, tendríamos que la parte de la expresión 2x^3+12x-6 sería par, pero -x^2 sería impar, de modo que h(x) sería impar, y no podría ser cero. Así, ya sólo nos quedan los candidatos

    \[\frac{1}{2},\frac{3}{2}.\]

Para ellos ya no hagamos trucos, y evaluemos directamente. Tenemos que

    \begin{align*}h\left(\frac{1}{2}\right) &= 2\cdot \frac{1}{8} - \frac{1}{4} + 12 \cdot \frac{1}{2}-6\\&=\frac{1}{4}-\frac{1}{4}+6-6\\&=0.\end{align*}

y que

    \begin{align*}h\left(\frac{3}{2}\right) &= 2\cdot \frac{27}{8} - \frac{9}{4} + 12 \cdot \frac{3}{2}-6\\&=\frac{27}{4}-\frac{9}{4}+18-6\\&=\frac{9}{2}+12\\&=\frac{33}{2}.\end{align*}

Habiendo considerado todos los casos, llegamos a que la única raíz racional de h(x) es \frac{1}{2}.

\square

Aplicación indirecta del criterio de la raíz racional

El criterio de la raíz racional lo podemos usar en algunos problemas, aunque en ellos no esté escrito un polinomio de manera explícita.

Problema. Muestra que \sqrt[7]{13} no es un número racional.

Solución. Por definición, el número \sqrt[7]{13} es el único real positivo r que cumple que r^7=13. Se puede mostrar su existencia usando que la función f:\mathbb{R}\to\mathbb{R} dada por f(x)=x^7 es continua, que f(0)=0, que f(2)=128, y aplicando el teorema del valor intermedio. Se puede mostrar su unicidad mostrando que la función f es estrictamente creciente en los reales positivos. Lo que tenemos que mostrar es que este número real no es racional.

Si consideramos el polinomio p(x)=x^7-13, tenemos que p(r)=r^7-13=0, de modo que r es raíz de p(x). Así, para terminar el problema, basta mostrar que p(x) no tiene raíces racionales.

El polinomio p(x) tiene coeficientes enteros, así que podemos aplicarle el criterio de la raíz racional. Una raíz racional tiene que ser de la forma \frac{p}{q} con p divisor de -13 y q divisor de 1.

Sin perder generalidad, q>0, así que q=1. De esta forma, los únicos candidatos a ser raíces racionales de p(x) son -13,-1,1,13. Sin embargo, una verificación de cada una de estas posibilidades muestra que ninguna de ellas es raíz de p(x). Por lo tanto, p(x) no tiene raíces racionales, lo cual termina la solución del problema.

\square

Aplicación en polinomio con coeficientes racionales

A veces un polinomio tiene coeficientes racionales, por ejemplo,

    \[r(x)=\frac{x^3}{2}+\frac{x^2}{3}-4x-1.\]

A un polinomio con todos sus coeficientes en \mathbb{Q} se les conoce como polinomio sobre los racionales y al conjunto de todos ellos se le denota \mathbb{Q}[x]. Para fines de encontrar raíces racionales, los polinomios en \mathbb{Q}[x] y los polinomios en \mathbb{Z}[x] son muy parecidos.

Si tenemos un polinomio q(x) en \mathbb{Q}[x], basta con multiplicar por el mínimo común múltiplo de los denominadores de los coeficientes para obtener un polinomio p(x) con coeficientes enteros. Como q(x) y p(x) varían sólo por un factor no cero, entonces tienen las mismas raíces. Por ejemplo, el polinomio r(x) de arriba tiene las mismas raíces que el polinomio

    \[s(x)=6r(x)=3x^3+2x^2-24x-6.\]

A este nuevo polinomio se le puede aplicar el criterio de la raíz racional para encontrar todas sus raíces racionales.

Ejemplo. Consideremos el polinomio

    \[q(x)=x^3+\frac{x^2}{3}+5x+\frac{5}{3}.\]

Vamos a encontrar todos los candidatos a raíces racionales. Para ello, notamos que q(x) y p(x):=3q(x) varían sólo por un factor multiplicativo no nulo y por lo tanto tienen las mismas raíces. El polinomio

    \[p(x)=3x^3+x^2+15x+5\]

tiene coeficientes enteros, así que los candidatos a raíces racionales son de la forma \frac{a}{b} con a y b primos relativos, a\mid 5 y b\mid 3. Sin pérdida de generalidad b>0.

Los divisores de 5 son -5,-1,1,5. Los divisores positivos de 3 son 1 y 3. De esta forma, los candidatos a raíces racionales son

    \[-5,-1,1,5,-\frac{5}{3},-\frac{1}{3},\frac{1}{3},\frac{5}{3}.\]

Si ponemos un número positivo en p(x), como sus coeficientes son todos positivos, tenemos que la evaluación sería positiva, así que podemos descartar estos casos. Sólo nos quedan los candidatos

    \[-5,-1,-\frac{5}{3},-\frac{1}{3}.\]

La evaluación en -5 da

    \begin{align*}-3\cdot 125 + 25 - 15\cdot 5 +5&=-375+25-75+5\\&=-295,\end{align*}

así que -5 no es raíz.

La evaluación en -1 da

    \begin{align*}-3+1-15+5=-12,\end{align*}

así que -1 tampoco es raíz.

Como tarea moral, queda verificar que -\frac{5}{3} tampoco es raíz, pero que -\frac{1}{3} sí lo es.

\square

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Realiza las evaluaciones que faltan en el último ejemplo.
  • Determina las raíces racionales del polinomio

        \[x^7-6x^4+3x^3+18x-1.\]

  • Muestra que \sqrt[3]{12} no es un número racional.
  • Encuentra todos los candidatos a ser raíces racionales de

        \[x^3+\frac{2x^2}{3}-7x-\frac{14}{3}.\]

    Determina cuáles sí son raíces.
  • Puede que un polinomio en \mathbb{Z}[x] no tenga raíces racionales, pero que sí se pueda factorizar en \mathbb{Z}[x]. Investiga acerca del criterio de irreducibilidad de Eisenstein.

Álgebra Superior II: Algoritmo de la división, teorema del factor y teorema del residuo

Introducción

Tal vez te hayas dado cuenta de que ya hablamos de suma, producto y resta de polinomios, pero aún no hemos hablado de la división. Una razón es que no todos los polinomios tienen inverso multiplicativo. Sin embargo, los polinomios sí tienen un algoritmo de la división parecido al que estudiamos para el conjunto \mathbb{Z} de enteros. A partir de él podemos extender varios de los conceptos aritméticos de \mathbb{Z} a \mathbb{R}[x]: divisibilidad, máximo común divisor, factorización, etc. Luego, estos aspectos se pueden conectar a evaluación de polinomios mediante el un teorema clave: el teorema del factor.

Como recordatorio, hasta ahora, ya construimos el anillo \mathbb{R}[x] de polinomios con coeficientes reales y vimos que era un dominio entero. También, vimos que una copia de \mathbb{R} vive en \mathbb{R}[x], con lo justificamos pasar de la notación de sucesiones, a la notación usual de polinomios usando el símbolo x y sus potencias. En la entrada anterior también hablamos de del grado de un polinomio (cuando no es el polinomio cero), de la evaluación de polinomios y de raíces.

Algoritmo de la división

Recordemos que en \mathbb{Z} tenemos un algoritmo de la división que dice que para enteros a y b\neq 0 existen únicos enteros q y r tales que a=qb+r y 0\leq r < |b|.

En \mathbb{R}[x] hay un resultado similar. Pero hay que tener cuidado al generalizar. En \mathbb{R}[x] no tenemos una función valor absoluto que nos permita decir que encontramos un «residuo más chiquito». Para la versión polinomial del algoritmo de la división tenemos que usar una función que diga «qué tan grande es un polinomio»: el grado.

Teorema (algoritmo de la división en \mathbb{R}[x]). Sean f(x) y g(x) polinomios en \mathbb{R}[x], donde g(x) no es el polinomio cero. Entonces, existen únicos polinomios q(x) y r(x) en \mathbb{R}[x] tales que

    \[f(x)=q(x)g(x)+r(x),\]

en donde r(x) es el polinomio cero, o \deg(r(x))<\deg(g(x)).

Demostración. Probaremos la parte de existencia. La parte de unicidad queda como tarea moral. Para probar la existencia, haremos inducción fuerte sobre el grado de f(x). Sin embargo, antes de poder hacer esto, necesitamos hacer el caso en el que f(x) no tiene grado, es decir, cuando es el polinomio cero.

Si f(x) es el polinomio cero, entonces g(x)=0 y r(x)=0 son polinomios que funcionan, pues 0=0\cdot 0 y r(x) es el polinomio cero.

Asumamos entonces a partir de ahora que f(x) no es el polinomio cero. Hagamos inducción sobre el grado de f(x). Si f(x) es de grado 0, entonces es un polinomio de la forma f(x)=a para a en \mathbb{R}. Hay dos casos de acuerdo al grado de g(x):

  • Si g(x) es de grado 0, es de la forma g(x)=b para un real no cero y podemos tomar q(x)=a/b y r(x)=0.
  • Si g(x) es de grado mayor a 0, entonces tomamos q(x)=0 y r(x)=f(x). Esta es una elección válida pues se cumple

        \begin{align*}\deg(r(x))&=\deg(f(x))\\& =0\\& <\deg(g(x)).\end{align*}

Esto termina la demostración de la base inductiva.

Supongamos que el resultado es cierto para cuando f(x) tiene grado menor a n y tomemos un caso en el que f(x) tiene grado n. Hagamos de nuevo casos con respecto al grado de g(x), al que llamaremos m. Si m>n, entonces tomamos q(x)=0 y r(x)=f(x), que es una elección válida pues

    \[\deg(r(x))=n<m.\]

En el caso de que m\leq n, escribamos explícitamente a f(x) y a g(x) en términos de sus coeficientes como sigue:

    \begin{align*}f(x)&=a_0+\ldots+a_nx^n\\g(x)&=b_0+\ldots+b_mx^m.\end{align*}

Consideremos el polinomio

    \[h(x):=f(x)-\frac{a_n}{b_m}x^{n-m}g(x).\]

En h(x) justo se cancela el término con x^n, así que su grado es menor al de f(x) y por lo tanto podemos usar la hipótesis inductiva para escribir

    \[h(x)=t(x)g(x)+u(x)\]

con u(x) el polinomio 0 o \deg(u(x))<\deg(g(x)). De esta forma,

    \begin{align*}f(x)&=t(x)g(x)+u(x)+\frac{a_n}{b_m}x^{n-m}g(x)\\&=\left(t(x)+\frac{a_n}{b_m}x^{n-m}\right)g(x)+u(x).\end{align*}

Así, eligiendo q(x)=t(x)+\frac{a_n}{b_m}x^{n-m} y r(x)=u(x), terminamos la hipótesis inductiva.

\square

Aplicando el algoritmo de la división de forma práctica

Veamos ahora un ejemplo de cómo se puede aplicar este teorema anterior de forma práctica. A grandes rasgos, lo que podemos hacer es «ir acumulando» en q(x) a los términos \frac{a_n}{b_m}x^{n-m} que van apareciendo en la inducción, y cuando h(x) se vuelve de grado menor a q(x), lo usamos como residuo. Hagamos un ejemplo concreto.

Ejemplo. Tomemos f(x)=x^5+x^4+x^3+x^2+2x+3 y g(x)=x^2+x+1. Vamos a aplicar iteradamente las ideas de la demostración del teorema anterior para encontrar los polinomios q(x) y r(x) tales que

    \[f(x)=q(x)g(x)+r(x),\]

con r(x) el polinomio 0 o de grado menor a g(x).

Como el grado de f(x) es 5, el de g(x) es 2 y 5>2, lo primero que hacemos es restar x^{5-2}g(x)=x^3g(x) a f(x) y obtenemos:

    \[h_1(x)=f(x)-x^3g(x)=x^2+2x+3.\]

Hasta ahora, sabemos que q(x)=x^3+\ldots, donde en los puntos suspensivos va el cociente que le toca a h_1(x)=x^2+2x+3. Como el grado de h_1(x) es 2, el de g(x) es 2 y 2\geq 2, restamos x^{2-2}g(x)=1\cdot g(x) a h_1(x) y obtenemos.

    \[h_2(x)=h_1(x)-g(x)=x+2.\]

Hasta ahora, sabemos que q(x)=x^3+1+\ldots, donde en los puntos suspensivos va el cociente que le toca a h_2(x)=x+2. Como el grado de h_2(x) es 1, el de g(x) es 2 y 2>1, entonces el cociente es 0 y el residuo es h_2(x)=x+2.

De esta forma, concluimos que

    \[q(x)=x^3+1\]

y

    \[r(x)=x+2.\]

En conclusión,

    \begin{align*}x^5+ & x^4+x^3+x^2+2x+3\\&= (x^3+1)(x^2+x+1) + x+2.\end{align*}

Esto se puede verificar fácilmente haciendo la operación polinomial.

\square

Hay una forma más visual de hacer divisiones de polinomios «haciendo una casita». Puedes ver cómo se hace esto en el siguiente video en Khan Academy, y los videos que le siguen en la lista.

Divisibilidad en polinomios

Cuando trabajamos en \mathbb{Z}, estudiamos la noción de divisibilidad. Si en el algoritmo de la división obtenemos que r(x) es el polinomio 0, entonces obtenemos una noción similar para \mathbb{R}[x].

Definición. Sean f(x) y g(x) polinomios en \mathbb{R}[x]. Decimos que g(x) divide a f(x) si existe un polinomio q(x) tal que f(x)=q(x)g(x).

Ejemplo. El polinomio x^3-1 divide al polinomio x^4+x^3-x-1, pues

    \[x^4+x^3-x-1 = (x^3-1)(x+1).\]

\square

Ejemplo. Si g(x) es un polinomio no cero y constante, es decir, de la forma g(x)=a para a\neq 0 un real, entonces divide a cualquier otro polinomio en \mathbb{R}[x]. En efecto, si

    \[f(x)=a_0+a_1x+\ldots + a_nx^n\]

es cualquier polinomio y tomamos el polinomio

    \[q(x)=\frac{a_0}{a}+\frac{a_1}{a}x+\ldots + \frac{a_n}{a}x^n,\]

entonces f(x)=g(x)q(x).

\square

El último ejemplo nos dice que los polinomios constantes y no cero se comportan «como el 1 se comporta en los enteros». También nos dice que cualquier polinomio tiene una infinidad de divisores. Eso nos pone en aprietos para definir algo así como los «polinomios primos» en términos del número de divisores. En la siguiente sección hablaremos de cómo hacer esta definición de manera adecuada.

Polinomios irreducibles

Cuando trabajamos con enteros, vimos que es muy útil poder encontrar la factorización en términos de números primos. En polinomios no tenemos «polinomios primos», pero tenemos un concepto parecido.

Definición. Un polinomio p(x) en \mathbb{R}[x] es irreducible en \mathbb{R}[x] si no es un polinomio constante, y no es posible escribirlo como producto de dos polinomios en \mathbb{R}[x] no constantes.

Ejemplo. El polinomio

    \[x^4+x^2+1\]

no es irreducible en \mathbb{R}[x] pues

    \[x^4+x^2+1=(x^2+x+1)(x^2-x+1).\]

Los polinomios x^2+x+1 y x^2-x+1 sí son irreducibles en \mathbb{R}[x]. Más adelante veremos por qué.

\square

La razón por la cual quitamos a los polinomios constantes es parecida a la cual en \mathbb{Z} no consideramos que 1 sea primo: ayuda a enunciar algunos teoremas más cómodamente.

Hay unos polinomios que fácilmente se puede ver que son irreducibles: los de grado 1.

Proposición. Los polinomios de grado 1 en \mathbb{R}[x] son irreducibles.

Demostración. Si f(x) es un polinomio de grado 1, entonces no es constante. Además, no se puede escribir a f(x) como el producto de dos polinomios no constantes pues dicho producto tiene grado al menos 2.

\square

Hay otros polinomios en \mathbb{R}[x] que no son de grado 1 y que son irreducibles. Por ejemplo, con la teoría que tenemos ahora te debe ser fácil mostrar de tarea moral que x^2+1 es irreducible en \mathbb{R}[x].

La razón por la que siempre insistimos en que la irreducibilidad sea en \mathbb{R}[x] es por que a veces un polinomio no se puede factorizar en polinomios con coeficientes reales, pero sí con coeficientes complejos. Aunque x^2+1 sea irreducible en \mathbb{R}[x], si permitimos coeficientes complejos se puede factorizar como

    \[x^2+1=(x+i)(x-i).\]

Más adelante seguiremos hablando de irreducibilidad. Por ahora, nos enfocaremos en los polinomios de grado 1.

Teorema del factor

Una propiedad clave de los polinomios de grado 1 es que es que es lo mismo que x-a divida a un polinomio p(x), a que a sea una raíz de p(x).

Teorema (del factor). Sea a un real y p(x) un polinomio en \mathbb{R}[x]. El polinomio x-a divide a p(x) si y sólo si p(a)=0.

Demostración. De acuerdo al algoritmo de la división, podemos escribir

    \[p(x)=(x-a)q(x)+r(x),\]

en donde r(x) es 0 o un polinomio de grado menor estricto al de x-a. Como el grado de x-a es 1, la única posibilidad es que r(x) sea un polinomio constante r(x)=r. Así, p(x)=(x-a)q(x)+r, con r un real.

Si p(a)=0, tenemos que

    \[0=p(a)=(a-a)q(a)+r=r,\]

de donde r=0 y entonces p(x)=(x-a)q(x), lo que muestra que x-a divide a p(x).

Si x-a divide a p(x), entonces p(x)=(x-a)q(x), de donde p(a)=(a-a)q(a)=0, por lo que a es raíz de p(x).

\square

Ejemplo. Consideremos el polinomio p(x)=x^3-6x^2+11x-6. ¿Podremos encontrar algunos polinomios lineales que lo dividan? A simple vista, notamos que la suma de sus coeficientes es 1-6+11-6=0. Esto nos dice que p(1)=0. Por el teorema del factor, tenemos que x-1 divide a p(x). Tras hacer la división, notamos que

    \[p(x)=(x-1)(x^2-5x+6).\]

Veamos si podemos seguir factorizando polinomios lineales que no sean x-1. Si un polinomio x-a divide a p(x), por el teorema del factor debemos tener

    \[0=p(a)=(a-1)(a^2-5a+6).\]

Como a\neq 1, entonces a-1\neq 0, de modo que tiene que pasar

    \[a^2-5a+6=0,\]

en otras palabras, hay que encontrar las raíces de x^2-5x+6.

Usando la fórmula general cuadrática, tenemos que las raíces de x^2-5x+6 son

    \begin{align*}x_1&=\frac{5+\sqrt{25-24}}{2}=3\\x_2&=\frac{5-\sqrt{25-24}}{2}=2.\end{align*}

Usando el teorema del factor, concluimos que tanto x-2 como x-3 dividen a p(x). Hasta ahora, sabemos entonces que

    \[p(x)=(x-1)(x-2)(x-3)h(x),\]

donde h(x) es otro polinomio. Pero (x-1)(x-2)(x-3) ya es un polinomio de grado 3, como p(x) y su coeficiente de x^3 es 1, como el de p(x). Concluimos que h(x)=1 y entonces

    \[p(x)=(x-1)(x-2)(x-3).\]

\square

Teorema del residuo

En realidad, la técnica que usamos para el teorema del factor nos dice algo un poco más general. Cuando escribimos

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

y evaluamos en a, obtenemos que p(a)=r. Reescribimos esta observación como un teorema.

Teorema (del residuo). Sea a un real y p(x) un polinomio en \mathbb{R}[x]. El residuo de dividir p(x) entre x-a es p(a).

Problema. Encuentra el residuo de dividir el polinomio p(x)=x^8-x^5+2x^3+2x entre el polinomio x+1.

Solución. Se podría hacer la división polinomial, pero esto es largo y no nos piden el polinomio cociente, sólo el residuo. Así, podemos resolver este problema más fácilmente usando el teorema del residuo.

Como x+1=x-(-1), el residuo de la división de p(x) entre x+1 es p(-1). Este número es

    \begin{align*}p(-1)&=(-1)^8-(-1)^5+2(-1)^3+2(-1)\\&=1+1-2-2\\&=-2.\end{align*}

\square

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Muestra que el polinomio x no tiene inverso multiplicativo.
  • Demuestra la parte de unicidad del algoritmo de la división.
  • Muestra que el polinomio x^2+1 es irreducible en \mathbb{R}[x]. Sugerencia. Procede por contradicción. Una factorización tiene que ser de la forma x^2+1=p(x)q(x) con p y q de grado 1.
  • Factoriza en términos lineales al polinomio p(x)=x^3-12x^2+44x-48. Sugerencia. Intenta enteros pequeños (digamos de -3 a 3) para ver si son raíces. Uno de ellos funciona. Luego, usa el teorema del factor para expresar a p(x) como un polinomio lineal por uno cuadrático. Para encontrar el resto de factores lineales, encuentra las raíces del cuadrático.
  • Encuentra el residuo de dividir el polinomio x^5-x^4+x^3-x^2+x-1 entre el polinomio x-2.

Álgebra Superior II: Problemas de sistemas de congruencias y teorema chino del residuo

Un ejercicio de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio distinto de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio de resolver un sistema de 3 ecuaciones lineales:

Resolviendo un sistema de tres ecuaciones lineales

Álgebra Superior II: Teoremas de Fermat y de Wilson

Introducción

En las entradas anteriores hablamos de congruencias, del anillo de enteros módulo n y vimos algunos problemas. La gran ventaja de trabajar en \mathbb{Z}_n, o bien, de trabajar módulo n, es que para n pequeña hay una cantidad pequeña de elementos y entonces las operaciones se vuelven muy sencillas.

Problema. Determina cuál es el residuo obtenido de dividir 705\cdot 702+714\cdot 711 al dividirse entre 7.

Solución. Tenemos que 705, 702, 714 y 711 los podemos poner como un múltiplo de 7 más un residuo como sigue: 700+5, 700+2 y 714=714+0, 711=707+4. Así, 705\equiv 5\pmod 7, 702\equiv 2 \pmod 7, 714\equiv 0 \pmod 7 y 711\equiv 4 \pmod 7. Así, trabajando módulo 7 tenemos que:

    \begin{align*}705\cdot 702+714\cdot 711 \equiv 5\cdot 2 + 0\cdot 4 \equiv 10 + 0 \equiv 10 \equiv 3 \pmod 7\end{align*}


De esta forma, 705\cdot 702+714\cdot 711 deja residuo 3 al dividirse entre 7.

\square

Trabajando de esta forma, podemos encontrar el residuo al dividirse por n de expresiones que involucran sumas y productos. El objetivo de esta entrada es entender qué sucede cuando queremos encontrar el residuo de expresiones que tienen potencias y factoriales.

Pequeño teorema de Fermat

Intentemos entender qué sucede con las potencias de un número a en cierto módulo n.

Ejemplo. Imagina que tomamos al número 3 y queremos elevarlo a distintas potencias y entender el residuo que deja al dividirse entre 7. Tenemos, trabajando módulo 7:

    \begin{align*}3^0\equiv 1\\3^1\equiv 3\\3^2\equiv 9 \equiv 2\\3^3=27\equiv 21+6\equiv 6\end{align*}

Nota que podríamos seguir, poniendo 3^4=81. Pero podemos ahorrarnos trabajo pues 3^4\equiv 3\cdot 3^3 \equiv 3 \cdot 6 \equiv 18\equiv 4, en donde usamos que ya sabíamos que 3^3\equiv 6. Del mismo modo, podemos seguir substituyendo cada potencia en la siguiente para obtener

    \begin{align*}3^5\equiv 3\cdot 4\equiv 12\equiv 5\\3^6\equiv 3\cdot 5 = 15\equiv 1\\3^7\equiv 3\cdot 1 = 3\\3^8\equiv 3\cdot 3 = 9 \equiv 2\end{align*}

Podríamos seguir y seguir, pero ya no tiene mucho caso. A partir de aquí es fácil convencerse de que los residuos se ciclan: 1,3,2,6,4,5,1,3,2,6,4,5,1\ldots. Notemos que si la potencia es múltiplo de 6, entonces el residuo será 1, es decir, 3^{6k}\equiv 1 \pmod 7. Esto es fantástico, pues entonces si queremos determinar el residuo de dividir, digamos, 3^{605} entre 7, basta ver que módulo 7 tenemos

    \[3^{605}=3^{600}\cdot 3^5 \equiv 1\cdot 5 \equiv 5,\]

en donde estamos usando lo que mencionamos para k=100 y que ya hicimos 3^5 módulo 7.

A partir del ejemplo anterior, nos damos cuenta de que es importante saber cuándo a^m\equiv 1\pmod n, pues en ese momento las potencias «se empiezan a ciclar». El pequeño teorema de Fermat es un resultado que podemos aplicar cuando trabajamos módulo un número primo p. Dice que la potencia p-1 funciona para esto.

Teorema. Si p es un número primo y p no divide a a, entonces p divide a a^{p-1}-1 o, dicho en otras palabras a^{p-1}\equiv 1 \pmod p.

Demostración. Afirmamos que los números a, 2a, 3a, \ldots, (p-1)a dejan todos ellos residuos distintos al dividirse entre p y, además, que ninguno de esos residuos es 0. Probemos esto. Tomemos 0<i<j<p-1. En una entrada anterior vimos que [a]_p tiene inverso en Z_p. Sea [b]_p su inverso. Si [ia]_p=[ja]_p, entonces multiplicando por [b]_p de ambos lados tendríamos

    \[[i]_p=[i(ab)]_p=[j(ab)]_p=[j]_p.\]

Pero como i y j están entre 1 y p-1, esto implica que i=j. Ninguno es cero pues si [ia]_p=[0]_p, entonces al multiplicar por b tendríamos la contradicción [i]_p=[i(ab)]_p=[0b]_p=[0]_p. Esto muestra la afirmación.

Así, usando la afirmación en el segundo paso de la siguiente cadena módulo p, tenemos:

    \begin{align*}(p-1)! a^{p-1} &= (a)(2a)(3a)\cdots((p-1)a)\\&\equiv 1\cdot 2 \cdot \ldots \cdot (p-1)\\&= (p-1)!.\end{align*}

El número (p-1)! no es divisible entre p, pues es producto de puros números menores que p, de modo que \text{MCD}(p, (p-1)!)=1, así que tiene inverso módulo p, de modo que podemos cancelarlo de la congruencia anterior multiplicando en ambos lados por su inverso. De aquí obtenemos la igualdad que queremos:

    \[a^{p-1}\equiv 1 \pmod p.\]

\square

Ya que demostramos este teorema, podemos aprovecharlo para resolver problemas que parecen ser difíciles.

Problema. Demuestra que 13 divide a 25^{181}-181^{25}

Solución. Notemos primero que 13 es primo y que no divide ni a 25 ni a 181. Por el pequeño teorema de Fermat, tenemos módulo 13 que 25^{12}\equiv 1 y que 181^{12}\equiv 1. Así, módulo 13 tenemos que

    \[25^{181}\equiv 25^{15\cdot 12}\cdot 25 \equiv 25 \equiv 12,\]

y que

    \[181^{25}\equiv 181^{2\cdot 12}\cdot 181\equiv 181 \equiv 12.\]

De esta forma, 25^{181}-181^{25}\equiv 12-12\equiv 0\pmod {13}, es decir, 13 divide a 25^{181}-181^{25}

\square

Teorema de Wilson

En la demostración del teorema de Fermat aparece la expresión (p-1)!. ¿Qué residuo dejará al dividirse entre p? Hagamos una prueba.

Problema. Encuentra el residuo que se obtiene al dividir 10! entre 11.

Solución. Para no trabajar con números tan grandes, notemos que en

    \[10!=1\cdot 2\cdot 3\cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10\]

podemos cambiar a 6,7,8,9,10 por -5, -4, -3, -2, -1 al trabajar módulo 11, así que basta encontrar -(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2 módulo 11. Notemos que 3\cdot 4\equiv 12 \equiv 1 \pmod {11} y que 2\cdot 5 =10 \equiv -1 \pmod {11}. Así,

    \[10!\equiv -(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2 \equiv -(1\cdot 1 \cdot -1)^2 \equiv -1 \equiv 10 \pmod {11},\]

es decir, el residuo que deja 10! al dividirse entre 11 es 10.

\square

El teorema de Wilson ayuda a cuando queremos encontrar el residuo de un factorial al dividirse entre un número primo. Una de las ideas del ejercicio anterior fue buena: nos conviene agrupar a números del factorial en productos sencillos. Lo más conveniente es que agrupemos a cada número con su inverso multiplicativo, pues así obtendremos un 1. Eso lo podemos hacer si el inverso es diferente. La siguiente proposición nos ayuda a entender cuándo pasa esto.

Proposición. Sea p un número primo. Los únicos elementos en \mathbb{Z}_p que son inversos de sí mismos son [1]_p y [p-1]_p.

Demostración. Claramente [1]_p y [p-1]_p=[-1]_p son inversos multiplicativos de sí mismos, pues 1\cdot 1=1=(-1)\cdot(-1). Ahora, si tenemos a tal que a es inverso multiplicativo de sí mismo, tenemos que [a^2]_p\equiv [1]_p, que por definición quiere decir que p divide a a^2-1=(a+1)(a-1). Cuando un primo divide a un producto, tiene que dividir a uno de los factores. Entonces p divide a a+1 o a a-1, y obtenemos, respectivamente, que [a]_p=[-1]_p=[p-1]_p o que [a]_p=[1]_p, como queríamos.

\square

Estamos listos para enunciar y demostrar el teorema de Wilson.

Teorema. Si p es un número primo, entonces p divide a (p-1)!+1 o, dicho en otras palabras, (p-1)!\equiv -1 \pmod p.

Demostración. Si p=2, el resultado es inmediato. Supongamos que p\geq 3. En (p-1)! aparecen todos los números de 1 a p-1. Todos ellos son primos relativos con p, así que tienen inverso módulo p. Ese inverso también aparece en (p-1)!. Así, podemos agrupar esos números en (p-3)/2 parejas de inversos multiplicativos, en donde por la proposición anterior sólo nos va a sobrar el 1 y el -1. De esta forma,

    \[(p-1)!\equiv (1)(-1)(1\cdot 1\cdot \ldots\cdot 1) \equiv -1 \pmod p,\]

en donde en la expresión intermedia tenemos un 1, un -1 y (p-3)/2 unos, uno por cada pareja de inversos que se multiplicaron. Esto termina la prueba.

\square

Veamos una posible aplicación.

Problema. Determina el residuo que se obtiene al dividir 15!+16!+17! entre 17.

Solución. Notemos que 17 divide a 17!, así que 17!\equiv 0 \pmod {17}. Por el teorema de Wilson, 16!\equiv -1 \pmod {17}. Podemos multiplicar esa igualdad por -1 para obtener módulo 17 que

    \[15! = 15! (-1)(-1) \equiv 15! \cdot 16 \cdot (-1) \equiv 16! (-1)\equiv (-1)(-1)\equiv 1.\]

Así, 15!+16!+17!\equiv 1 + (-1) + 0 \equiv 0 \pmod {17}.

\square

Una solución alternativa es darse cuenta de que

    \[15!+16!+17!=15!(1+16)+17\cdot 16!=17\cdot (15!+16!)\]

y por lo tanto es múltiplo de 17. Aunque tengamos herramientas fuertes, ¡siempre hay que recordar los básicos!

Álgebra Superior II: Problemas de divisibilidad

A continuación les dejo los links que les preparé para hoy. Se ven en el orden que están. Si tienen dudas, pueden ponerlas en la sección de comentairos de aquí del blog.

Ejemplo de algoritmo de la división de Euclides
Condición necesaria para que 2^n+1 sea primo
a-b divide a a^n-b^n