Archivo de la etiqueta: factorización

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

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

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 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 $q(x)=0$ y $r(x)=0$ son polinomios que funcionan, pues $0=0\cdot g(x)+0$, para cualquier polinomio $g(x)$.

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).$$ Notemos que en $h(x)$ el coeficiente que acompaña a $x^n$ es $a_n-\frac{a_nb_m}{b_m}=0$, así que el grado de $h(x)$ 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.

$\triangle$

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 1. 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).$$

$\triangle$

Ejemplo 2. 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)$.

$\triangle$

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 no constantes en $\mathbb{R}[x]$.

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é.

$\triangle$

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 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).$$

$\triangle$

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$

Más adelante…

Los teoremas que hemos visto en esta entrada serán las principales herramientas algebraicas que tendremos en el estudio de los polinomios así como en la búsqueda de las raíces de los polinomios y en resolver la pregunta sobre su irreductibilidad.

El algoritmo de la división nos servirá (como nos sirvió en $\mathbb{Z}$ para poder precisar el algoritmo de Euclides y definir el máximo común divisor de dos polinomios.

Por ahora, en la siguiente entrada, nos encargaremos de practicar lo aprendido y resolver ejercicios sobre raíces y residuos de polinomios.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Muestra que el polinomio $x$ no tiene inverso multiplicativo.
  2. Demuestra la parte de unicidad del algoritmo de la división.
  3. 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$.
  4. 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.
  5. Encuentra el residuo de dividir el polinomio $x^5-x^4+x^3-x^2+x-1$ entre el polinomio $x-2$.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Seminario de Resolución de Problemas: Identidades algebraicas y binomio de Newton

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción a entradas de álgebra

Cuando en matemáticas hablamos de álgebra, se abarca una gran cantidad de ideas, que van desde el álgebra de secundaria, en la cual factorizamos, despejamos y usamos identidades algebraicas, hasta el álgebra abstracta, que estudia estructuras algebraicas más generales como grupos, anillos y campos. Todas estas ideas tienen amplias aplicaciones en la resolución de problemas. En esta entrada, y las que vendrán a continuación, veremos numerosos ejemplos de esto

Para empezar, hablaremos de álgebra en el sentido de secundaria y preparatoria. Veremos que estas ideas, aunque sencillas, son muy versátiles. Después hablaremos de polinomios y de dos resultados fundamentales en su teoría: el teorema de factorización única y el teorema de la identidad. Los polinomios abundan en las matemáticas, y un correcto entendimiento de ellos abre muchas puertas en la resolución de problemas. En una entrada final daremos algunas ideas de otras estructuras algebraicas como grupos, anillos y campos.

Más adelante en el curso hablaremos con detalle de otros dos temas relacionados con álgebra: desigualdades y álgebra lineal.

Como lo hemos hecho hasta ahora, la idea no es profundizar demasiado en el desarrollo de la teoría algebraica. Para eso, es más recomendable llevar buenos cursos de distintos tipos de álgebra a nivel superior. Aquí en el blog hay material de los cursos Álgebra Superior II y Álgebra Lineal I que imparto en la Facultad de Ciencias de la UNAM.

Identidades algebraicas

Comenzaremos hablando de identidades algebraicas. Una identidad algebraica es una igualdad que se satisface para ciertas variables, independientemente del valor que tomen. Algunos ejemplos son las igualdades que se aprenden a nivel secundaria y bachillerato:

\begin{gather*}
a^2-b^2=(a-b)(a+b),\\
a^2+2ab+b^2=(a+b)^2,\\
a^2+b^2+c^2+2ab+2bc+2ca=(a+b+c)^2,\\
a^n-b^n = (a-b)(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1}).
\end{gather*}

Varias de las identidades algebraicas nos permiten desarrollar o factorizar una expresión. Factorizarla es bastante útil en problemas de teoría de números, en donde es importante conocer qué números dividen a la expresión. Desarrollarla a veces nos permite trabajar con una suma de términos simétricos, que podemos estudiar con técnicas de polinomios o con desigualdades.

Veamos algunos ejemplos.

Problema. Muestra que si $n$ es un entero, entonces $n^4-20n^2+4$ no es un número primo.

Sugerencia pre-solución. Intenta formular un problema equivalente al factorizar la expresión. Hay más de un camino por el que puedes proceder para factorizar, pero no todos te llevan a una solución. Intenta completar cuadrados de distintas formas y ve si encuentras un patrón.

Solución. Reescribimos la expresión como sigue:
\begin{align*}
n^4-20n^2+4&=n^4-4n^2+4-16n^2\\
&=(n^2-2)^2-(4n)^2\\
&=(n^2-4n-2)(n^2+4n-2).
\end{align*}

Para ver que la expresión no es un primo, basta con ver que ninguno de estos factores puede ser igual a $1$ o $-1$. Si $n^2-4n-2=1$ o $n^2+4n-2=1$, entonces $n^2=\pm 4n+3$. Trabajando módulo $4$, tendríamos $n^2\equiv 3 \pmod{4}$, lo cual es imposible.

Si $n^2-4n-2=-1$ o $n^2+4n-2=-1$, entonces sumando $6$ de ambos lados tenemos $$(n\pm 2)^2=n^2\pm 4n+4=5.$$ Esto es imposible pues $5$ no es el cuadrado de un entero. Así, $n^4-20n^2+4$ se puede factorizar en factores distintos de $1$ y $-1$ y por lo tanto no es primo.

$\square$

El siguiente problema fue parte de la 1a Olimpiada Mexicana de Teoría de Números. Veremos dos soluciones. Ambas usan ideas algebraicas, pero son distintas entre sí.

Problema. Sean $a,b,c,d$ enteros tales que

\begin{align*}
ab + bc + ca &= 1\\
ad + dc + ca &= 1\\
ab + bd + da &= 1.
\end{align*}

Determina todos los valores posibles que puede tomar $bc+cd+db$.

Sugerencia pre-solución 1. Hay varias formas de aprovechar la simetría del problema. Intenta manipular las ecuaciones para obtener información y recuerda que es importante usar que $a$, $b$, $c$ son enteros.

Solución 1. A partir de la primera y segunda ecuación, tenemos que $$ab+bc+ca=ad+dc+ca,$$

de donde $0=ad+dc-ab-bc=(a+c)(d-b)$. De aquí tenemos dos opciones: $a=-c$ o $b=d$. Si $a=-c$, de la segunda ecuación obtenemos $$1=ad+dc+ca=-c^2,$$ lo cual es imposible. Así, concluimos que $b=d$.

Por simetría, concluimos que $c=b$, así que $b=c=d$. Tras esto, las tres ecuaciones se reducen a una sola $$1=2ab+b^2=b(2a+b).$$ Las únicas factorizaciones de $1$ en enteros son $1=1\cdot 1$ o $1=(-1)(-1)$, de modo que $b=2a+b$, de donde $a=0$ y $b=\pm 1$. De cualquier forma, la expresión que buscamos es $bc+cd+db=3b^2=3$.

$\square$

Sugerencia pre-solución 2. Formula un problema equivalente sumando $a^2$ en ambos lados en cada una de las ecuaciones.

Solución 2. Sumando $a^2$ en ambos lados de la primer ecuación obtenemos $$a^2+1=a^2+ab+bc+ca=(a+b)(a+c).$$ Las otras dos ecuaciones dan expresiones simétricas. Multiplicando las tres, tenemos $$(a^2+1)(a^2+1)^2=(a+b)^2(b+c)^2(c+a)^2.$$

El lado derecho es el cuadrado de un entero, así que el izquierdo también debe serlo, de modo que $a^2+1$ debe ser el cuadrado de un entero. Pero los únicos cuadrados a distancia $1$ son $0$ y $1$, de donde $a^2+1=1$, y así $a=0$. Las ecuaciones se convierten entonces en $bc=dc=bd=1$, de donde la suma de las tres es $3$.

$\square$

Demostraciones del binomio de Newton

La siguiente es una de las identidades algebraicas más importantes.

Teorema (binomio de Newton). Para $a$ y $b$ números reales y $n$ un entero no negativo, se tiene que
\begin{align*}
(a+b)^n=\sum_{j=0}^n \binom{n}{j}a^{n-j}b^j
\end{align*}

El término de la derecha es $$a^n+\binom{n}{1}a^{n-1}b+\ldots+\binom{n}{n-1}ab^{n-1} + b^n.$$

Veamos algunas demostraciones del teorema de binomio de Newton, que usan ideas un poco distintas. La primera usa ideas combinatorias. La segunda, ideas más algebraicas. La tercera es menos general, pero usa ideas geométricas.

Demostración combinatoria

Demostración 1. Pensemos al lado izquierdo como el producto $$(a+b)(a+b)\ldots(a+b)(a+b).$$ ¿Cómo se obtienen factores al desarrollar esta expresión? En cada uno de los $n$ paréntesis hay que elegir o un $a$, o un $b$. Así, cada sumando es producto de $n$ letras.

Si elegimos $j$ veces $b$, entonces elegimos $n-j$ veces $a$. ¿De cuántas formas podemos elegir $j$ veces $b$? Tantas como subconjuntos de tamaño $j$ de un conjunto de $n$ elementos, es decir, $\binom{n}{j}$.Así, el término $a^{n-j}b^j$ aparece $\binom{n}{j}$ veces.

Para terminar, notemos que $j$ puede ir desde $0$ (no elegir ningún $b$), hasta $n$ (no elegir ningún $a$).

$\square$

La demostración anterior es combinatoria, pues está usando argumentos de conteo. Está contando de dos formas distintas los términos que aparecen en el producto desarrollado. Además, está usando la interpretación combinatoria de los coeficientes binomiales.

Demostración algebraica

Demostración 2. Si $b=0$, entonces en ambos lados tenemos $a^n$, ya que el único sumando en el que no aparece $b$ es el primero. Tenemos algo análogo si $a=0$. De otra forma, podemos asumir que $a$ y $b$ no son cero y dividir ambos lados de la igualdad que queremos entre $b^n$. Definiendo $x=a/b$, tenemos que mostrar que:

$$(x+1)^n= \sum_{j=0}^n \binom{n}{j}x^{n-j}.$$

Esta igualdad es claramente cierta para $n=0$, pues en ambos lados obtenemos $1$, y para $n=1$, pues en ambos lados obtenemos $x+1$. Procediendo por inducción (explicamos cada paso con un poco de detalles más abajo):

\begin{align*}
(x+1)^{n+1}&=(x+1)(x+1)^n\\
& = (x+1)\sum_{j=0}^n \binom{n}{j} x^{n-j}\\
&=\sum_{j=0}^n \binom{n}{j} x^{n-j+1}+\sum_{j=0}^n \binom{n}{j}x^{n-j}\\
& = \sum_{j=0}^{n+1} \binom{n}{j-1} x^{n-j}+\sum_{j=0}^{n+1} \binom{n}{j}x^{n-j}\\
&=\sum_{j=0}^{n+1}\left(\binom{n}{j-1}+\binom{n}{j}\right) x^{n-j}\\
&=\sum_{j=0}^{n+1}\binom{n+1}{j} x^{n-j}.
\end{align*}

El primer paso es claro. En el segundo usamos hipótesis inductiva. Luego, hacemos la multiplicación por $x+1$. El siguiente paso puede ser un poco confuso, pues parece que «agregamos términos», pero en la segunda suma sólo agregamos $\binom{n}{n+1}x^{-1}=0$. En la primer suma hicimos un shift o desfase: los términos que estaban antes para $j$ de $0$ a $n$, ahora están para $j$ de $1$ a $n+1$. Además, agregamos el término $\binom{n}{-1}x^{n}=0$. En el siguiente paso usamos la identidad de Pascal: $$\binom{n}{j-1}+\binom{n}{j}=\binom{n+1}{j},$$ que se puede demostrar combinatoriamente, o directamente de manera algebraica a partir de la fórmula para coeficientes binomiales.

Con esto termina la demostración por inducción.

$\square$

Esta segunda demostración es mucho más algebraica, es decir, usa ideas de cómo se manipulan las expresiones con variables. El primer paso, en el que reducimos el problema a cuando un término es $1$, se llama homogenización. En realidad no era estrictamente necesario hacerlo, pero simplifica la notación. En las sumas hicimos un shift, que es otra técnica que se usa al estudiar sumas y series.

Demostración geométrica

Daremos una última demostración del teorema del binomio de Newton, pero sólo para el caso $n=2$. Lo que tenemos que demostrar es simplemente la identidad $$(a+b)^2=a^2+2ab+b^2.$$ Para este caso, hay una bonita «demostración sin palabras»:

Binomio al cuadrado mostrado geométricamente
Demostración visual del binomio al cuadrado

Esta demostración es geométrica, pues estamos interpretando a la igualdad como una igualdad de áreas. Estamos usando una fórmula de área para cuadrados y rectángulos. Además, estamos usando que el área de una figura es aditiva, es decir, que es igual a la suma de áreas de figuras en las que queda subdividida.

Puedes elegir tu demostración favorita del binomio de Newton. Sin embargo, en resolución de problemas es importante saber proceder con varios acercamientos. Hay problemas en los que el acercamiento combinatorio, el algebraico o el geométrico es ventajoso, y por ello es mejor tener buena práctica en todos ellos.

Una aplicación del binomio de Newton en teoría de números

En entradas anteriores ya hemos usado el teorema del binomio de Newton en repetidas ocasiones, por ejemplo, en la entrada de aritmética de números complejos. Veamos un ejemplo más.

Problema. Sean $a$ y $b$ enteros primos relativos. Muestra que para todo entero positivo $n$, se tiene que $a^n$ y $b^n$ son primos relativos.

Sugerencia pre-problema. Hay varias formas de dar una solución de esto. Una es analizando a los enteros primo por primo. Sin embargo, existe una solución usando binomio de Newton y la caracterización en términos de combinaciones lineales enteras para primos relativos.

Solución. Como $a$ y $b$ son primos relativos, existe una combinación lineal entera de ellos que da $1$, digamos $$ax+by=1.$$ Elevando esta igualdad a la $2n-1$ tenemos $$1=1^{2n-1}=(ax+by)^{2n-1}.$$ Abriendo el último término con binomio de Newton queda
$$\sum_{j=0}^{n-1} \binom{2n-1}{j} a^{2n-1-j}b^j + \sum_{j=n}^{2n-1} \binom{2n-1}{j} a^{2n-1-j}b^j,$$ y factorizando $a^n$ del primer sumando y $b^n$ del segundo,
$$a^n \sum_{j=0}^{n-1} \binom{2n-1}{j} a^{n-1-j}b^j + b^n \sum_{j=n}^{2n-1} \binom{2n-1}{j} a^{2n-1-j}b^{j-n}.$$

Lo que queda a la derecha es una combinación lineal entera de $a^n$ y $b^n$ igual a $1$, y por lo tanto son primos relativos.

$\square$

Más problemas

En la siguiente entrada hablaremos de la identidad de Gauss para suma de cuadrados y de la identidad para $x^3+y^3+z^3-3xyz$, las cuales se usan frecuentemente en resolución de problemas. Además, puedes encontrar más problemas de identidades algebraicas en la Sección 4.1 del libro Problem Solving through Problems de Loren Larson.

Seminario de Resolución de Problemas: Primos y factorización única

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En entradas anteriores hablamos de divisibilidad y de aritmética modular. Ahora platicaremos de las bloques que nos ayudan a construir a todos los enteros de manera multiplicativa: los números primos. Lo que dice el teorema fundamental de la aritmética es que todo número es producto de primos «de manera única». Tanto la teoría de números primos, como este teorema, son de gran ayuda en la resolución de problemas.

Como en entradas anteriores, el enfoque no es demostrar los resultados principales de la teoría. Esto se hace en un curso de Álgebra Superior II o en uno de Teoría de Números. La idea de la entrada es ver aplicaciones de estos resultados en situaciones concretas.

Números primos

Un entero es primo si tiene exactamente dos divisores positivos. El $1$ no es primo pues su único divisor es él mismo. Pero $2$, $17$ y $31$ sí son primos. De aquí y el algoritmo de la división, si $p$ es primo y $a$ es un entero, entonces $p\mid a$ o $\MCD{p,a}=1$.

Proposición 1. Si $p$ es un número primo que divide al producto de enteros $ab$, entonces $p\mid a$ ó $p\mid b$.

Demostración. Si $p$ no divide a $a$, entonces $\MDC(p,a)=1$, así que existe una combinación lineal entera $pn+am=1$. Multiplicando esta combinación por $b$, tenemos que $pbn+abm=b$. Como $p$ divide a $pbn$ y a $ab$, entonces divide a $b$.

$\square$

Problema. Muestra que si $p$ es un primo que divide a $123456^{654321}$, entonces $p$ divide a $123456$.

Sugerencia pre-solución. Aquí $123456$ y $654321$ no tienen nada de especial. Generaliza el problema y procede por inducción en el exponente.

Solución. Sea $a$ un entero, $n$ un entero positivo y $p$ un primo. Vamos a mostrar por inducción en $n$ que si $p\mid a^n$, entonces $p\mid a$. Para $n=1$ la conclusión es inmediata. Supongamos el resultado cierto para $n$. Si $p\mid a^{n+1}$, por la Proposición 1 tenemos que $p\mid a$ (en cuyo caso terminamos), o que $p\mid a^n$ (en cuyo caso terminamos por hipótesis inductiva). El problema se resuelve tomando $a=123456$ y $n=6543321$.

$\square$

Extendiendo la idea del problema anterior, se puede demostrar la siguiente proposición.

Proposición 2. Si $p$ es primo, $a$ un entero y $n$ un entero positivo tales que $p\mid a^n$, entonces $p^n\mid a^n$.

Teorema fundamental de la aritmética

Todo número es producto de primos de manera única. Más específicamente

Teorema (teorema fundamental de la aritmética). Sean $a$ un entero positivo. Entonces existe un único $n$, únicos primos $p_1<\ldots<p_n$ y exponentes $\alpha_1,\ldots,\alpha_n$ tales que $$a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}.$$

La idea de la demostración es factorizar y factorizar. Si $n$ está expresado como producto de primos, ya está. Si no, hay uno de sus factores que no es primo y entonces se puede factorizar en dos números menores. Para probar la unicidad se usa la Proposición 1.

Veamos algunas aplicaciones del teorema fundamental de la aritmética.

Problema. Muestra que $\sqrt[3]{7}$ es un número irracional.

Sugerencia pre-solución. Procede por contradicción suponiendo que es racional para igualarlo a una fracción y eleva al cubo.

Solución. Si no fuera irracional, lo podríamos expresar como una fracción, digamos $\sqrt[3]{7}=\frac{a}{b}$ con $a$ y $b$ enteros. De aquí, $7b^3=a^3$. En la factorización en primos de $a^3$ y $b^3$ tenemos una cantidad múltiplo de $3$ de factores $7$. Así, en el lado derecho tenemos una cantidad mútiplo de $3$ de factores $7$ (por la Proposición 2), pero en el lado izquierdo no. Esto es una contradicción a la unicidad de la factorización en primos.

$\square$

Es posible que en un problema tengamos que usar el teorema fundamental de la aritmética repetidas veces.

Problema. Determina todos los enteros positivos $n$ para los cuales $2^8+2^{11}+2^n$ es un número entero al cuadrado.

Sugerencia pre-solución. Trabaja hacia atrás y usa notación adecuada. Intenta encontrar una diferencia de cuadrados.

Solución. Vamos a comenzar suponiendo $m^2=2^8+2^{11}+2^n$. De aquí, \begin{align*}
2^n&=m^2-2^8(1+2^3)\\
&=m^2-(3\cdot 2^4)^2\\
& =(m+48)(m-48).
\end{align*}

Por la unicidad del teorema fundamental de la aritmética, cada uno de los números $m+48$ y $m-48$ tienen que ser potencias de $2$, digamos $m+48=2^a$ y $m-48=2^b$ con $a>b$ y $a+b=n$. Además tenemos que $$2^b(2^{a-b}-1)=96=2^5\cdot 3.$$

Como $2^{a-b}-1$ es impar, de nuevo por la unicidad de la factorización en primos debemos tener que $2^{a-b}-1=3$, y por lo tanto que $2^b=2^5$. De aquí, $b=5$ y $a-b=2$, y así $a=7$. Por lo tanto, el único candidato es $n=5+7=12$.

Ya que trabajamos hacia atrás, hay que argumentar o bien que los pasos que hicimos son reversibles, o bien que $n$ en efecto es solución. Hacemos esto último notando que $2^8+2^{11}+2^{12}=2^8(1+2^3+2^4)=2^8\cdot 5^2$ que en efecto es un número cuadrado.

$\square$

Fórmulas que usan el teorema fundamental de la aritmética

Sean $a$ y $b$ números enteros positivos y $P={p_1,\ldots,p_n}$ el conjunto de números primos que dividen a alguno de $a$ o $b$. Por el teorema fundamental de la aritmética, existen exponentes $\alpha_1,\ldots,\alpha_n$ y $\beta_1,\ldots,\beta_n$, tal vez algunos de ellos cero, tales que \begin{align*}
a&=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots\cdot p_n^{\alpha_n}\\ b&=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_n^{\beta_n}. \end{align*}

Por ejemplo, si $a=21, b=28$, entonces $P={2,3,7}$, $a=2^0 3^1 7^1$ y $b=2^2 3^0 7^1$.

Proposición 3. Se tiene que $a$ divide a $b$ si y sólo si para todo primo $p_i$ se tiene que $\alpha_i\leq \beta_i$.

Problema. ¿Cuántos múltiplos de $108$ hay que sean divisores de $648$?

Sugerencia pre-solución. Factoriza en primos a $108$ y a $648$ y usa la Proposición 3.

Solución. Tenemos que $108=2^23^3$ y que $648=2^3\cdot 3^4$. Por la Proposición 3, un número que funcione debe ser de la forma $2^a3^b$ con $2\leq a \leq 3$ y con $3\leq b \leq 4$. Así, $a$ tiene $2$ posibilidades y $b$ también, de modo que hay $2\cdot 2=4$ números que cumplen.

$\square$

Una consecuencia inmediata de la Proposición 3 anterior es la fórmula para el número de divisores de un entero en términos de los exponentes de su factorización en primos.

Proposición 4. El entero $a$ tiene $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)$ divisores positivos.

Problema. Determina cuántos enteros hay entre $1$ y $10000$ que tienen $49$ divisores positivos.

Sugerencia pre-solución. Usa la fórmula de la Proposición 4 para trabajar hacia atrás y ver qué forma debe tener un entero que cumple lo que se quiere. Divide en casos para que el producto se $49$.

Solución. Tomemos $a$ un entero y $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$ su factorización en primos. Por la Proposición 4, necesitamos que $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)=49$.

A la izquierda tenemos puros números mayores o iguales que $2$. El número $49$ tiene como únicos divisores a $1$, $7$ y $49$. De esta forma, sólo hay dos casos posibles:

  • El número $a$ tiene sólo un divisor primo y $a=p_1^{48}$.
  • El número $a$ tiene dos divisores primos y $a=p_1^6p_2^6$.

El primer caso es imposible, pues $p_1$ sería por lo menos $2$ y $$2^{48}>2^{20}=(1024)^2>(1000)^2>10000.$$ Para el segundo caso, recordemos que $p_2>p_1$ en la factorización en primos. Si $p_2\geq 5$, entonces como $p_1\geq 2$, tendríamos $$a\geq (2\cdot 5)^6 = 1000000>10000,$$ así que esto no es posible.

La única otra posibilidad es $p_2=3$ y por lo tanto $p_1=2$. En este caso obtenemos al número $a=(2\cdot 3)^6=6^6=46656$, que sí cae en el intervalo deseado. Así, sólo hay un número como el que se pide.

$\square$

La factorización en primos también sirve para encontrar máximos comunes divisores y mínimos comunes múltiplos.

Proposición 4.  Se pueden calcular $\MCD{a,b}$ y $\mcm{a,b}$ como sigue:
\begin{align*}
\text{MCD}(a,b)&=p_1^{\min(\alpha_1,\beta_1)}\cdot p_2^{\min(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\min(\alpha_n,\beta_n)}\\
\text{mcm}(a,b)&=p_1^{\max(\alpha_1,\beta_1)}\cdot p_2^{\max(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\max(\alpha_n,\beta_n)}.
\end{align*}

Volvamos a ver un problema que ya habíamos resuelto con anterioridad.

Problema. Demuestra que $\MCD{a,b}\mcm{a,b}=ab$.

Sugerencia pre-solución. Usa la Proposición 4. Puedes argumentar algunos pasos por simetría.

Solución. Expresemos a $a$ y $b$ en su factorización en primos como lo discutimos arriba. Al multiplicar $\MCD{a,b}$ y $\mcm{a,b}$, el exponente de $p_i$ es $\min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i)=\alpha_i+\beta_i$. Este es el mismo exponente de $p_i$ en $ab$. Así, ambos números tienen la misma factorización en primos y por lo tanto son iguales.

$\square$

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.3 del libro Problem Solving through Problems de Loren Larson.

Si $p$ es primo, entonces todo entero $n$ que no sea múltiplo de $p$ tiene inverso módulo $n$. Esto se usa en los teoremas de Fermat y Wilson. También hay una entrada con ejercicios de estos teoremas resueltos en video.

Aprovechar la simetría

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

HeuristicasLa simetría, además de ser una propiedad que hace que las cosas se vean bonitas, también es una buena técnica de resolución de problemas. Hay varias formas en las que se puede aprovechar la simetría en un problema. Una es para reducir esfuerzo: ¿para qué repetir un argumento si es el mismo? ¿para qué desarrollar todos los términos si la ecuación es simétrica?

En  otras ocasiones la simetría nos permite sospechar que los casos especiales tienen que ser simétricos. A veces no hay razón para que sea de otra forma. Finalmente, la simetría también está presente en una gran variedad de la información del problema, y hay que inventarla o descubrirla para simplificar cuentas, notación y conjeturas.

Ir a los videos…

Cómo dar una factorización mágica.

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

[latexpage]

Hace poco salió el siguiente problema en la Olimpiada de Matemáticas del Distrito Federal y en el examen de los estados que mandamos para que elijan algunos problemas para sus selectivos.

El Problema

Problema: Sean $a,b,c,d$ reales positivos con $a^2+b^2+c^2+d^2=4$. Muestra que:

$a^5+b^5+c^5+d^5\geq a+b+c+d$.

Este es el momento en el que tienes que intentar el problema si quieres. Seguir leyendo