Archivo de la etiqueta: primos

Álgebra Superior II: Teorema fundamental de la aritmética e infinidad de números primos

Por Ana Ofelia Negrete Fernández

4 respuestas

Introducción

En la entrada anterior comenzamos a hablar de los números primos. Lo que ahora veremos es que, en un sentido muy preciso, los números primos son los bloques con los cuales se construyen todos los demás enteros. El enunciado preciso estará dado por el teorema fundamental de la aritmética.

A grandes rasgos, el teorema fundamental de la aritmética afirma que todo entero se puede escribir como producto de primos, quizás algunos repetidos. Nos referimos a situaciones del tipo
\begin{align*}
8 &= 2 \cdot 2 \cdot 2 = 2^3,\\
13 &= 13^1,\\
152 &= 2^3\cdot 19, \enspace \text{etc.}
\end{align*}

Otro resultado que demostraremos en esta entrada es que hay una infinidad de primos. Euclides fue una de las primeras personas de quienes nos queda registro que lo notó. Veremos una demostración similar a la que él dió.

El teorema fundamental de la aritmética

El teorema fundamental de la aritmética dice que cualquier número entero es producto de números primos. Pero, más aún, nos dice que este producto es único, bajo ciertas condiciones que le ponemos a la representación. Para simplificar la presentación, estudiaremos primero lo que dice el enunciado para enteros positivos.

Teorema. Sea $n$ un entero positivo. Entonces, existe un único entero $k$ y únicos números primos $p_1\leq p_2 \leq p_3 \leq \ldots \leq p_k$ tales que $$n=p_1\cdot p_2\cdot \ldots \cdot p_k.$$

Por ejemplo, consideremos el número $1060$. Notemos que en efecto se puede escribir como producto de primos de la siguiente manera: $1060=2\cdot 2 \cdot 5 \cdot 53$. El teorema fundamental de la aritmética nos dice que esta es la única manera en la que podemos ponerlo como producto de primos. Si lo piensas un poco, no es totalmente obvio. ¿Qué impide que, por ejemplo, no pase que $1060$ tenga otra posible representación en donde el $5$ aparezca más veces, o el $2$ menos veces? Es lo que debemos estudiar.

Demostración de la existencia

Vamos a partir la demostración del teorema fundamental de la aritmética en dos partes. Primero veremos la existencia, y después la unicidad. Así, nos enfocaremos primero en ver que cualquier entero positivo tiene una factorización en números primos.

La demostración será por inducción fuerte. Si $n=1$, la factorización es la factorización vacía, en donde $k=0$, y como no estamos multiplicando nada obtenemos $1$. Si $n=2$, entonces la factorización es precisamente $2=2$, pues $2$ es un número primo. Supongamos que el resultado es cierto hasta antes de cierto número fijo $n$ y veamos qué pasa con $n$. Si $n$ es un número primo, entonces $n=n$ ya es una factorización como las que buscamos. Si $n$ no es un número primo, entonces lo podemos factorizar como $n=ab$, en donde $a$ y $b$ son enteros positivos distintos de $1$. Por ello, cada uno de $a$ y $b$ son menores que $n$ y por hipótesis inductiva tienen una factorización en primos, digamos
\begin{align*}
a&=q_1\cdot q_2 \cdot \ldots\cdot q_l\\
b&=r_1\cdot r_2 \cdot \ldots \cdot r_m.
\end{align*}

Así, renombrando $q_1,\ldots,q_l,r_1,\ldots,r_m$ como $p_1\leq \ldots \leq p_k$ (donde $k=l+m$) para que queden en orden no decreciente obtenemos la factorización $$n=p_1\cdot p_2\cdot \ldots \cdot p_k $$ buscada. Esto termina la prueba de la primera parte.

Demostración de la unicidad

Veamos ahora que las factorizaciones en primos son únicas. Una vez más, procedemos por inducción fuerte. El resultado claramente es cierto para $n=1$ y $n=2$. Supongamos que el resultado es cierto hasta antes de cierto entero $n$ dado y supongamos que tenemos dos factorizaciones para $n$:

\begin{align*}
n&=p_1\cdot p_2 \cdot \ldots\cdot p_k\\
n&=q_1\cdot q_2 \cdot \ldots \cdot q_l.
\end{align*}

Notemos que $p_k$ es un divisor de $n$, así que debe dividir a $q_1\cdot\ldots\cdot q_l$. Por una propiedad de divisibilidad que vimos en la entrada pasada, debe suceder que o bien $p_k$ divide a $q_l$, o bien que divide a $q_1\cdot \ldots \cdot q_{l-1}$. Si pasa lo segundo, debe dividir o bien a $q_{l-1}$, o bien a $q_1\cdot \ldots \cdot q_{l-2}$. Y así sucesivamente, de modo que $p_k$ debe dividir a alguno de los $q_i$. Pero como $p_k$ y $q_i$ son primos, debe suceder entonces que $p_k=q_i$. Tras cancelar este término en ambas expresiones de $n$, llegamos a que:

$$p_1\cdot p_2 \cdot \ldots\cdot p_{k-1}=q_1\cdot \ldots \cdot q_{i-1} \cdot q_i \cdot \ldots \cdot q_l,$$

pero esto es una igualdad de factorizaciones en primos para un número menor estricto a $n$. Por hipótesis inductiva, ambas factorizaciones deben de ser la misma. Así, ambas factorizaciones de $n$ son la misma, pues se obtienen a partir de estas multiplicando por el número $p_k=q_i$.

$\square$

Otra forma de escribir el teorema fundamental de la aritmética

Hay otra manera de escribir el teorema fundamental de la aritmética, en donde los primos iguales se agrupan en un mismo término, y se coloca la potencia correspondiente.

Teorema. Sea $n$ un entero positivo. Existe un único entero no negativo $k$, únicos primos $p_1\leq \ldots \leq p_k$ y únicos exponentes $\alpha_1,\ldots,\alpha_k$ tales que:

$$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot \ldots \cdot p_k^{\alpha_k}.$$

En realidad esta segunda versión del teorema se deduce de manera inmediata de la anterior.

Ejemplo. Consideremos el número $36$. El $2$ lo divide, así que $36=18\cdot 2$. Luego, el $3$ divide al $18$, de manera que $36=3\cdot 6\cdot 2$. Finalmente, notamos que $6=2\cdot 3$, de donde $36=3\cdot 2 \cdot 3 \cdot 2$. Para obtener la «forma estándar» de la factorización, agrupamos los primos iguales, les ponenmos el orden correspondiente y escribimos en orden creciente de primos. Así, la factorización de $36$ quedaría $36=2^2\cdot 3^2$.

$\triangle$

El conjunto de primos es infinito

En esta sección queremos demostrar otro resultado importante sobre el conjunto de los números primos.

Teorema. El conjunto de números primos es infinito.

Para dar la demostración, usaremos el método de demostración por contradicción, es decir, partiremos de que el conjunto de primos no es finito y, eventualmente se disparatará el asunto.

Este en efecto parece ser el método más conveniente. Sería difícil usar inducción dado que, si bien el conjunto de primos puede indexarse por $p_1, p_2, p_3, \ldots$, no es fácil determinar cuál es el primo que sigue en la lista. O bien, dado un entero $n$, no es fácil determinar si $n+1$ será o no un número primo. Resultaría igualmente difícil intentar la demostración por algún otro método directo.

La idea que usaremos es la siguiente. Si hay finitos primos, digamos $k$, significa que se puede crear una lista finita con ellos: $p_1, p_2, \ldots , p_k$. Veremos que siempre debe existir un primo distinto de los de la lista, lo que llevará a una contradicción con la hipótesis de que sólo existían $k$ primos.

Veamos primero unos casos particulares del argumento que usaremos. Supongamos que sólo existieran $2$ primos, el $2$ y el $3$. Consideremos el número $z = 2\cdot 3 + 1$. De acuerdo al teorema fundamental de la aritmética, este número o bien es primo, o bien debe tener un divisor primo $p$. No puede ser primo, pues dijimos que los únicos primos eran $2$ y $3$. No puede ser divisible entre $2$ pues deja residuo $1$ al hacer la división. Tampoco puede ser divisible entre $3$ pues también deja residuo $1$ al hacer la división. Así, debe haber otro primo que no sea $2$ y $3$ y que divida a este número. Esto contradice que sólo existieran $2$ primos.

Veamos otro ejemplo. Supongamos que hay únicamente 4 primos: $2,3,5,7$. Consideremos el número $2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211.$ Si dividimos este número entre $2$, nos da $211=105\cdot 2 +1$, así que $2\nmid 211$. Si lo dividimos entre $3$, nos da $211=70\cdot 3 + 1$, así que $3\nmid 211$. De manera similar, se puede ver que las divisiones entre $5$ y $7$ también dejan residuo $1$, así que $5 \nmid 211$ y $7\nmid 211$.

Por el teorema fundamental de la aritmética, debe haber algún primo que divida a $211$. Pero estamos suponiendo que los únicos primos que existen son $2,3,5,7$ y acabamos de ver que ninguno de estos funciona. ¡Esto es una contradicción! Lo mismo ocurrirá sin importar la cantidad de primos $p_1, p_2, \ldots , p_k$ inicial. El problema no es cuántos son exactamente, sino la suposición de que son una cantidad finita.

Demostración. Supongamos, para buscar una contradicción, que el conjunto de números primos es finito y que consiste de exactamente los $k$ números primos $p_1, p_2, \ldots , p_k$. Consideremos el número $$p_1\cdot p_2 \cdot \ldots \cdot p_k +1.$$

El anterior número no es divisible por ninguno de los primos $$p_1, p_2, \ldots , p_k,$$ pues precisamente al hacer la división el residuo que queda es igual a $1$.

Por el teorema fundamental de la aritmética, $$p_1\cdot p_2 \cdot \ldots \cdot p_k + 1$$ debe tener entonces un divisor primo $p$ diferente de $$p_1, p_2, \ldots , p_k. $$ Esto es una contradicción, pues supusimos que sólo existían los primos $p_1,\ldots,p_k$.

$\square$

Más adelante…

Con los dos teoremas de esta entrada hemos profundizando un poco más en por qué los números primos son interesantes e importantes. La exploración de los números primos en este curso no irá mucho más lejos, pues pronto comenzaremos a tratar otros temas de aritmética modular. Sin embargo, te dejamos algunos pocos párrafos más sobre los números primos.

Los números primos siguen siendo interesantes para los matemáticos hoy en día; primero por la irregularidad con que van apareciendo en la recta numérica y porque hay muchas cosas que aún no se sabe acerca de su raro comportamiento. Por ejemplo, se conjetura que hay infinitos «primos gemelos», es decir, se cree que siempre es posible encontrar dos primos $a$ y $b$ que estén distanciados en dos unidades; no importa qué tan alejados estén del cero. El $3$ y el $5$ son primos gemelos. También los son el $17$ y el $19$. Nadie sabe si esta conjetura es cierta o falsa.

Los números primos aparecen en patrones muy irregulares, pero sí es posible decir algunas cosas al respecto. Por ejemplo, después del $2$ todo número primo $p$, es de la forma $4n +1$ o de la forma $4n -1$ para alguna $n \in \mathbb{N}$. Un resultado lindo en teoría de números es que para aquéllos primos que pertenecen a la primera categoría, que son los de la forma $4n+1$, siempre existe su expresión como una suma de cuadrados: $p = 4n + 1 = m^2 + n^2$, $n, m \in \mathbb{Z}.$ Pero a los primos de la segunda categoría es imposible expresarlos como suma de cuadrados. Estos son dos de los muchos resultados que demostró Euler para números primos, y puedes ahondar en ello en un curso de teoría de números.

Los números primos también han encontrado aplicaciones en criptografía, pues es bien sabido que si se eligen dos primos $p_1$ y $p_2$ tales que al multiplicarlos se obtenga un número compuesto $z$ de más de 100 dígitos, y si luego se establece que $p_1$ y $p_2$ sean la «clave» de mi mensaje cifrado pero yo únicamente doy a conocer el número compuesto $z$ a otra persona, entonces a una computadora le resultaría imposible factorizar $z$ en un corto lapso de tiempo. ¡Le tomaría años! De ahí que la contraseña secreta sería indescifrable.

Ahora, lo que se conoce como el «teorema fundamental de la aritmética» también tiene varias extensiones interesantes en otras áreas de las matemáticas. De hecho, en algunas estructuras la unicidad deja de ser cierta. Si combinamos a los números enteros con los números complejos (que veremos después), tenemos algunos ejemplos como $$12 = (1 + \sqrt{-11})(1 – \sqrt{-11})$$ pero también $$12 = (2 + \sqrt{-8})(2 – \sqrt{-8}).$$

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. Encuentra la factorización en primos de cada uno de los siguientes números 100, 170, 2022, 5000 y 713.
  2. Encuentra el menor entero positivo $k$ que haga que $775k$ sea un número cuadrado perfecto, es decir, de la forma $n^2$ para algún entero $n$.
  3. Halla el número de divisores de $2360$ y calcula la suma de todos ellos.
  4. ¿Cuál es el número entero de $1$ a $100$ que tiene la mayor cantidad posible de divisores?
  5. Demuestra que un entero tiene una cantidad impar de divisores si y sólo si es un número cuadrado.

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»

Álgebra Superior II: Números primos y sus propiedades

Por Ana Ofelia Negrete Fernández

Deja un comentario

Introducción

En esta entrada hablaremos de los protagonistas de entre los números enteros: los números primos. Es difícil poder enunciar en palabras sencillas la importancia que tienen este tipo de números, así que haremos un recorrido que incluye lo siguiente. Comenzaremos dando la definición de qué es un número primo, y haremos algunas aclaraciones conceptuales. Luego, enunciaremos propiedades de divisibilidad que cumplen los números primos y que son muy únicas a ellos. Esto nos ayudará a entender un poco de las razones por las cuales son especiales.

Finalmente, dejaremos preparado el terreno para poder hablar de dos resultados fundamentales sobre los números primos en la próxima entrada: el teorema fundamental de la aritmética y la infinidad del conjunto de números primos. El primer resultado nos permitirá pensar a los números primos como los átomos de los números enteros, ya que a partir de multiplicarlos se obtendrá cualquier entero, sea éste primo o compuesto.

Definición de números primos

La definición con la que trabajaremos es la siguiente.

Definición. Un entero número entero $p$ es primo si y sólo si es positivo y tiene exactamente cuatro divisores: $1, \enspace -1, \enspace z \enspace \text{y } -z \text{.}$

De la definición hay algunos números que inmediatamente debemos descartar por no ser números primos. Por ejemplo, el $1$ no es un número primo pues tiene como divisores únicamente al $-1$ y al $1$, que son dos divisores, y no exactamente cuatro, como pide la definición. Del mismo modo, $-1$ tampoco es número primo pues tiene sólo dos divisores también y, para rematar, es negativo, lo cual no se vale.

Del mismo modo, concluimos que el $0$ no es número primo. Su problema es que tiene demasiados divisores. Cualquier número entero divide al $0$, así que tiene mucho más que cuatro divisores. Veamos nuestro primer ejemplo de un número que sí es primo.

Proposición. El entero $2$ es primo.

Demostración. Lo primero por notar es que $2$ es positivo. Supongamos que $x \in \mathbb{Z}$ divide a $2$. Por cómo se comparan en tamaños un número con un divisor, obtenemos que $|d|\leq 2$. Esto nos deja $5$ posibilidades para $d$: $-2,-1,0,1,2$. El $0$ nunca es divisor y se puede ver que cada uno de los otros cuatro números sí lo son. Así, el $2$ tiene exactamente cuatro divisores, que son $1$, $2$, $-1$ y $-2$. Concluimos entonces que $2$ es un número primo.

$\square$

Si bien el $-2$ también tiene exactamente esos mismos $4$ divisores, a $-2$ no le llamamos número primo porque es negativo. Recuerda que por definición sólo los números positivos pueden ser primos.

En la duda, si no sabemos si un número es primo, siempre podemos regresar a la definición.

Proposición. El entero $57$ no es primo.

Demostración. Notamos que $1$, $3$, $19$ y $57$ son todos ellos divisores de $57$, así como sus negativos. Por ello, el número $57$ tiene ocho divisores, y por lo tanto no es primo.

$\square$

Otras formas de pensar a los números primos

La definición de primos que dimos está en términos de la cantidad de divisores en total que se deben tener. Sin embargo, hay por lo menos otras dos formas de escribir esto mismo.

Proposición. Son equivalentes las siguientes tres afirmaciones para un número entero $p$:

  • El número $p$ es primo de acuerdo a nuestra definición de tener exactamente $4$ divisores.
  • El número $p$ es positivo y tiene exactamente $2$ divisores positivos.
  • El número $p$ es positivo y en cualquier forma de escribir $p=ab$ con $a$ y $b$ enteros positivos, sucede forzosamente que $a=1$ ó $b=1$.

Demostración. Los primeros dos puntos son equivalentes entre sí pues si $d$ es un divisor de $p$, entonces $-d$ también. Así, por cada divisor positivo hay uno negativo y viceversa. De hecho, los dos divisores positivos son, explícitamente, $1$ y $p$.

Si $p$ es primo con respecto a esta segunda definición, entonces el tercer inciso es claro, pues escribir $p=ab$ justo nos dice que $a|p$, de donde $a=1$ ó $a=p$, pues son sus únicos dos posibles divisores. Si $a=1$, tenemos lo que queremos. Y si $a=p$, entonces para que se de $p=ab$, debemos tener $b=1$, como queremos.

Finalmente, a partir del tercer inciso también se puede demostrar el segundo. Supongamos que $p$ cumple con el tercer inciso y supongamos que $d$ es divisor. ESto nos permite escribir $p=dr$ con $r$ algún entero. Por el tercer inciso, debemos tener $d=1$, o bien $r=1$, y entonces $d=p$, tal como nos pide el segundo inciso.

$\square$

Quizás no se ve tanto la ventaja entre distinguir entre las primeras dos versiones de la proposición anterior. De hecho, se parecen mucho. Sin embargo, sí vale la pena pensar en la tercera como algo diferente: nos dice que hay sólamente dos maneras de escribir a un primo como producto de números positivos. Esto nos ayuda, por ejemplo, a darnos cuenta rápidamente que un número no es primo aunque no tengamos todos sus divisores.

Ejemplo. El número $105$ no es primo pues se puede escribir como $5\cdot 21$. En esta expresión ninguno de los dos números es igual a $1$. Así, concluimos que $105$ no es primo.

$\square$

Propiedades de divisibilidad de los números primos

En el caso de los números primos, los máximos comunes divisores son asunto de todo o nada. Esto está escrito más formalmente en la siguiente definición.

Proposición. Sea $p$ un número primo y $a$ un entero. Si $p$ divide a $a$, tenemos $(a,p)=p$. Y si no, tenemos $(a,p)=1$.

Demostración. Sabemos que $(a,p)|p$ y que $(a,p)$ no es negativo. Así, $(a,p)$ debe ser uno de los dos divisores de $p$: $1$ ó $p$. Si $p$ divide a $a$, entonces $(a,p)=p$ pues $p$ es divisor común tanto de $p$ como de $a$. Pero si $p$ no divide a $a$, entonces a $(a,p)$ no le queda más que ser igual a $1$.

$\square$

La proposición anterior nos lleva a un lema de divisibilidad que nos resultará útil cuando enunciemos y probemos el teorema fundamental de la aritmética.

Proposición. Sea $p$ un número primo y $a,b$ números enteros. Si $p|ab$, entonces $p|a$ ó $p|b$.

Demostración. Si $p|a$, entonces ya terminamos. Si no, por la proposición anterior tenemos que $(p,a)=1$. Pero entonces por una propiedad anterior de divisibilidad con primos relativos obtenemos que $p|b$, como queríamos.

$\square$

Para la proposición anterior resultó crucial que $p$ fuera un número primo. Por ejemplo, tenemos que $9|180=15\cdot 12$, pero no es cierto ni que $9|15$, ni que $9|12$.

Más adelante…

En la siguiente entrada veremos dos teoremas importantes relacionados con los números primos: el teorema fundamental de la aritmética y el teorema de que existe una infinidad de primos.

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. Encuentra todos los números primos de $1$ a $20$.
  2. Sea $n$ un número entero que no sea un número primo, ni el negativo de un número primo. Demuestra $n$ que se puede expresar de la forma $ab$ con $a$ y $b$ enteros (positivos o negativos) de por lo menos ocho formas distintas.
  3. Sea $p>2$ un número tal que ninguno de los números $2,\ldots,\left\lfloor \sqrt{p}\right \rfloor$ lo divide. Muestra que $p$ es un número primo.
  4. Sea $n$ un número entero y $p$ un primo. Muestra que si $p|n^2$, entonces $p|n$. De hecho, muestra que en general, para un entero $k\geq 1$ se cumple que $p|n^k$ si y sólo si $p|n$.
  5. Sea $p$ un número primo. ¿Cuántos divisores tiene el número $p^{10}$? ¿Cuántos son positivos y cuántos negativos?

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»

Álgebra Superior II: Irreducibilidad y factorización en polinomios reales

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

Los números enteros tiene un teorema de factorización en primos: el teorema fundamental de la aritmética. Los polinomios en $\mathbb{R}[x]$ también. En esta entrada hablaremos de la irreducibilidad y factorización en polinomios reales. Lo primero lo haremos para decir «quiénes son los primos» en $\mathbb{R}[x]$. Para lo segundo usaremos el teorema del factor, que demostramos con anterioridad.

Resulta que el teorema de factorización en polinomios reales depende de un resultado importante de polinomios en $\mathbb{C}[x]$, es decir, los de coeficientes complejos. Esto es algo que sucede con frecuencia: a veces para resolver un problema en los números reales, hay que dar un paso hacia los complejos y luego regresar. Por esa razón, para esta entrada es importante que tengas en mente varias propiedades en los complejos, sobre todo cómo se realizan las operaciones y cuales son las propiedades de la conjugación compleja. Esto nos dará la oportunidad de enunciar (sin demostración) el teorema fundamental del álgebra.

Como recordatorio, un polinomio es irreducible en $\mathbb{R}[x]$ si no es un polinomio constante y no se puede escribir como producto de dos polinomios no constantes en $\mathbb{R}[x]$. Además, el teorema del factor nos dice que si $a$ es raíz de un polinomio $p(x)$, entonces $x-a$ divide a $p(x)$. Diremos que un polinomio es lineal si es de grado $1$ y cuadrático si es de grado $2$.

El teorema fundamental del álgebra

Así como construimos a $\mathbb{R}[x]$, se puede hacer algo análogo para construir a $\mathbb{C}[x]$, los polinomios de coeficientes complejos. Puedes practicar todo lo que hemos visto haciendo la construcción formal. Por el momento, para fines prácticos, puedes pensarlos como expresiones de la forma $$a_0+a_1 x + \ldots + a_n x^n$$ con $a_i$ complejos, digamos, $$(1+i)+2i x -3x^3+(5+2i)x^4.$$

Los polinomios en $\mathbb{C}[x]$ cumplen todo lo que hemos dicho de $\mathbb{R}[x]$: se vale el lema de Bézout, el algoritmo de Euclides, el teorema del factor, el teorema del residuo, etc. Una copia de $\mathbb{R}[x]$, con su estructura algebraica, «vive» dentro de $\mathbb{C}[x]$, es decir, todo polinomio con coeficientes reales se puede pensar como uno con coeficientes complejos.

Sin embargo, los polinomios en $\mathbb{R}[x]$ y en $\mathbb{C}[x]$ son muy diferentes en términos de raíces. Esto se nota, pir ejemplo, en el hecho de que el polinomio $x^2+1$ no tiene raíces en $\mathbb{R}$, pero sí en $\mathbb{C}$, donde la raíz es $i$. Resulta que esta $i$ hace toda la diferencia. Al agregarla no solamente hacemos que $x^2+1$ tenga una raíz, sino que ya todo polinomio tiene raíz. Esto está enunciado formalmente por el teorema fundamental del álgebra.

Teorema (teorema fundamental del álgebra). Todo polinomio no constante en $\mathbb{C}[x]$ tiene al menos una raíz en $\mathbb{C}$.

No vamos a demostrar este teorema durante el curso. Hay desde demostraciones elementales (como la que aparece en el bello libro Proofs from the book), hasta algunas muy cortas, pero que usan teoría un poco más avanzada (como las que se hacen en cursos de análisis complejo). Sin embargo, lo usaremos aquí para obtener algunas de sus consecuencias y, al final de esta entrada, demostrar los teoremas de irreducibilidad y factorización en polinomios reales.

Teorema de factorización en $\mathbb{C}[x]$

En la entrada anterior ya demostramos que los polinomios lineales son irreducibles. Veremos ahora que en $\mathbb{C}[x]$ no hay ningún otro polinomio irreducible.

Proposición. Los únicos polinomios irreducibles en $\mathbb{C}[x]$ son los de grado $1$.

Demostración. Tomemos cualquier polinomio $p(x)$ en $\mathbb{C}[x]$ de grado al menos $2$. Por el teorema fundamental del álgebra, $p(x)$ tiene al menos una raíz $z$ en $\mathbb{C}$. Por el teorema del factor, $$x-z \mid p(x),$$ así que podemos escribir $p(x)=(x-z)q(x)$ con $q(x)$ en $\mathbb{C}[x]$ de grado $\deg(p(x))-1\geq 1$.

De esta forma, pudimos factorizar al polinomio $p(x)$ en dos factores no constantes, y por lo tanto no es irreducible.

$\square$

Con esto podemos mostrar que en $\mathbb{C}[x]$ todo polinomio es factorizable como producto de términos lineales.

Teorema (de factorización única en $\mathbb{C}[x]$). Todo polinomio $p(x)$ en $\mathbb{C}[x]$ distinto del polinomio cero se puede factorizar de manera única como $$p(x)=a(x-z_1)(x-z_2)\cdots(x-z_n)$$ en donde $a$ es un complejo no cero, $n$ es el grado de $p(x)$ y $z_1,\ldots,z_n$ son complejos que son raíces de $p(x)$.

Demostración. Mostraremos la existencia de la factorización. La parte de la unicidad es sencilla, y su demostración queda como tarea moral. Procedemos por inducción en el grado de $p(x)$. Si $p(x)$ es de grado cero, entonces es de la forma $p(x)=a$ con $a$ un complejo, y ya está en la forma que queremos.

Tomemos ahora un entero $n\geq 1$. Supongamos que el resultado es cierto para los polinomios de grado $n-1$ y consideremos un polinomio $p(x)$ de grado $n$. Por el teorema fundamental del álgebra, $p(x)$ tiene al menos una raíz, digamos $z_n$. Usando el teorema del factor, existe un polinomio $q(x)$, que debe de ser de grado $n-1$, tal que $$p(x)=q(x)(x-z_n).$$ Aplicando la hipótesis inductiva a $q(x)$, podemos factorizarlo de la forma $$q(x)=a(x-z_1)(x-z_2)\cdots(x-z_{n-1}),$$ con $z_1,\ldots,z_{n-1}$ raíces de $q(x)$ (y por lo tanto también raíces de $p(x)$). De esta forma, $$p(x)=(x-z_1)(x-z_2)\cdots(x-z_{n-1})(x-z_n)$$ es una factorización que cumple lo que queremos. Esto termina la hipótesis inductiva, y por lo tanto la parte de existencia de la demostración.

$\square$

Ejemplo. Consideremos al polinomio $$p(x)=x^4+5x^2+4$$ en $\mathbb{R}[x]$. Este polinomio no tiene raíces reales, pues sus evaluaciones siempre son positivas. Sin embargo, lo podemos pensar como un polinomio en $\mathbb{C}[x]$. Por el teorema fundamental del álgebra, este polinomio debe tener una raíz en $\mathbb{C}$.

Afortunadamente, podemos encontrarla por inspección. Una de estas raíces es $i$, pues $$i^4+5i^2+4=1-5+4=0.$$ Por el teorema del factor, $x-i$ divide a $p(x)$. Al realizar la división, obtenemos $$p(x)=(x-i)(x^3+ix^2+4x+4i).$$ De aquí, por inspección, obtenemos que $-i$ es una raíz de $x^3+ix^2+4x+4i$, y realizando la división entre $x+i$, tenemos que $$p(x)=(x-i)(x+i)(x^2+4).$$

El polinomio $x^2+4$ claramente tiene como raíces a $2i$ y $-2i$. A partir de todo esto concluimos que $$p(x)=(x-i)(x+i)(x-2i)(x+2i)$$ es la factorización de $p(x)$ en polinomios lineales en $\mathbb{C}[x]$.

$\square$

En el ejemplo anterior podemos agrupar los factores $(x-i)$ y $(x+i)$ para obtener el polinomio $x^2+1$. De aquí obtenemos la factorización alternativa $$p(x)=(x^2+1)(x^2+2).$$ Esta factorización tiene puros coeficientes reales. Aquí hay que hacer una observación importante: esta no es una factorización en irreducibles en $\mathbb{C}[x]$, pero sí es una factorización en irreducibles en $\mathbb{R}[x]$. Retomaremos varias de estas ideas más en general en las siguientes secciones.

Raíces complejas de polinomios en $\mathbb{R}[x]$

En el ejemplo de la sección anterior sucedió que $i$ era una raíz de $p(x)$, y que $-i$ también. Cuando tenemos un polinomio de coeficientes reales y $z$ es un complejo que es raíz, entonces su conjugado también.

Proposición. Tomemos $p(x)$ un polinomio en $\mathbb{R}[x]$ y $z$ un número en $\mathbb{C}$. Si $p(z)=0$, entonces $p(\overline{z})=0$.

Demostración. Si $p(x)$ es el polinomio cero, la afirmación es cierta. En otro caso, sea $n$ el grado de $p(x)$ y escribamos a $p(x)$ como $$p(x)=a_0+a_1x+\ldots+a_nx^n,$$ donde $a_i$ son números en $\mathbb{R}$ para $i=0,\ldots,n$. Por lo que sabemos de la conjugación compleja, $\overline{a_i}=a_i$, y además abre sumas y productos. Así,
\begin{align*}
\overline{p(z)}&=\overline{a_0+a_1z+\ldots+a_nz^n}\\
&=\overline{a_0}+\overline{a_1z}+\ldots +\overline{a_nz^n}\\
&=\overline{a_0} + \overline{a_1}\, \overline{z} + \ldots +\overline{a_n}\, \overline{z}^n\\
&=a_0 + a_1 \overline{z} + \ldots + a_n \overline{z}^n\\
&=p(\overline{z}).
\end{align*}

Como $p(z)=0$, concluimos que $$p(\overline{z})=\overline{p(z)}=\overline{0}=0.$$

$\square$

El resultado anterior no es cierto en general para polinomios con coeficientes en $\mathbb{C}[x]$. Esto debe ser muy claro pues, por ejemplo, $i$ es raíz de $x-i$, pero $-i$ no.

Proposición. Tomemos $p(x)$ un polinomio en $\mathbb{R}[x]$ y una raíz $z$ de $p(x)$ en $\mathbb{C}\setminus \mathbb{R}$. Entonces el polinomio $$q(x)=x^2-(z+\overline{z})x+z\overline{z}$$ es un polinomio en $\mathbb{R}[x]$ que divide a $p(x)$ en $\mathbb{R}[x]$.

Demostración. Observa que $q(x)=(x-z)(x-\overline{z})$. Recordemos que
\begin{align*}
z+\overline{z}&=2\Rea{(z)} \\
z\overline{z}&=\norm{z}^2 .
\end{align*}

Esto muestra que los coeficientes de $q(x)$ son reales. Usemos el algoritmo de la división en $\mathbb{R}[x]$ para escribir $$p(x)=q(x)h(x)+r(x),$$ con $r(x)$ el polinomio cero, o de grado a lo más $1$.

Evaluando en $z$ y en $\overline{z}$, se obtiene que $r(z)=r(\overline{z})=0$. Como $z$ no es real, entonces $z$ y $\overline{z}$ son distintos. De este modo, $r(x)$ es el polinomio cero. Así, $p(x)=q(x)h(x)$ es una factorización de $p(x)$ en $\mathbb{R}[x]$ que usa a $q(x)$.

$\square$

Nuevamente, hay que tener cuidado con las hipótesis del resultado anterior. Es muy importante que usemos que $z$ es una raíz compleja y no real de un polinomio con coeficientes reales. En la tarea moral puedes encontrar un contraejemplo si no se satisfacen las hipótesis.

Ejemplo. Consideremos el polinomio $$p(x)=2x^3-16x^2+44x-40.$$ Una de sus raíces complejas es $3+i$, como puedes verificar. Como es un polinomio con coeficientes reales, el conjugado $3-i$ también es una raíz. Tal como lo menciona la proposición anterior, el polinomio
\begin{align*}
q(x):&=(x-(3+i))(x-(3-i))\\
&=x^2-(3+i+3-i)x+(3+i)(3-i)\\
&=x^2-6x+10
\end{align*}

es un polinomio de coeficientes reales. Además, divide a $p(x)$ en $\mathbb{R}[x]$ pues haciendo la división polinomial, tenemos que $$2x^3-16x^2+44x-40=(2x-4)(x^2-6x+10).$$

$\square$

Irreducibilidad y factorización en polinomios reales

Con todo lo que hemos hecho hasta ahora, estamos listos para probar los resultados que queremos en $\mathbb{R}[x]$. Observa que los enunciados de las secciones anteriores involucran a $\mathbb{C}$, pero los de esta sección ya no. Sin embargo, para hacer las demostraciones tenemos que dar un «brinco momentáneo a los complejos».

Recuerda que para un polinomio cuadrático $q(x)=ax^2+bx+c$ su discriminante es $b^2-4ac$.

Teorema (irreducibilidad en polinomios reales). Los únicos polinomios irreducibles en $\mathbb{R}[x]$ son los lineales y los cuadráticos de discriminante negativo.

Demostración. Ya mostramos antes que los polinomios lineales son irreducibles. Si $q(x)=ax^2+bx+c$ es un polinomio cuadrático y $r$ es una raíz real, tenemos que
\begin{align*}
ar^2+br+c&=0\\
r^2+\frac{b}{a}r+\frac{c}{a}&=0\\
r^2+\frac{b}{a}r+\frac{b^2}{4a^2}-\frac{b^2}{4a^2}+\frac{c}{a}&=0\\
\left(r+\frac{b}{2a}\right)^2&=\frac{b^2-4ac}{4a^2}.
\end{align*}

De esta igualdad, obtenemos que $\frac{b^2-4ac}{4a^2}\geq 0$ y por lo tanto que $b^2-4ac \geq 0$. Dicho de otra forma, si $b^2-4ac<0$, entonces $q(x)$ no tiene raíces reales. De esta misma equivalencia de igualdades se puede ver que si $b^2-4ac\geq 0$, entonces $q(x)$ sí tiene por lo menos una raíz real.

Supongamos que $q(x)$ es un polinomio cuadrático con discriminante negativo. Si existiera una factorización en $\mathbb{R}[x]$ de la forma $q(x)=a(x)b(x)$, con ninguno de ellos constante, entonces ambos deben tener grado $1$. Podemos suponer que $a$ es mónico. Pero entonces $a(x)=x-r$ para $r$ un real, y por el teorema del factor tendríamos que $r$ sería raíz de $q(x)$, una contradicción a la discusión anterior. Esto muestra que $q(x)$ es irreducible.

Falta ver que no hay ningún otro polinomio irreducible en $\mathbb{R}[x]$. Cuando $p(x)$ es cuadrático de discriminante no negativo, entonces por la fórmula cuadrática tiene al menos una raíz real $r$ y por lo tanto $x-r$ divide a $p(x)$, mostrando que no es irreducible.

Si $p(x)$ es de grado mayor o igual a $3$ y tiene una raíz real $r$, sucede lo mismo. En otro caso, es de grado mayor o igual a $3$ y no tiene raíces reales. Pero de cualquier forma tiene al menos una raíz compleja $z$. Usando la proposición de la sección anterior, tenemos que $x^2-(z+\overline{z})x+z\overline{z}$ es un polinomio de coeficientes reales que divide a $p(x)$ en $\mathbb{R}[x]$, lo cual muestra que no es irreducible.

Concluimos entonces que los únicos polinomios irreducibles en $\mathbb{R}[x]$ son los lineales y los cuadráticos de discriminante negativo.

$\square$

Ahora sí podemos enunciar el resultado estelar de esta entrada.

Teorema (factorización en polinomios reales). Todo polinomio $p(x)$ en $\mathbb{R}[x]$ distinto del polinomio cero se puede factorizar de manera única como $$a(x-r_1)\cdots(x-r_m)(x^2-b_1x+c_1)\cdots (x^2-b_{n}x+c_{n}),$$ en donde:

  • $a$ es un real distinto de cero,
  • $m$ y $n$ son enteros tales que $m+2n$ es igual al grado de $p(x)$,
  • para cada $i$ en $\{1,\ldots,m\}$ se tiene que $r_i$ es raíz real de $p(x)$ y
  • para cada $j$ en $ \{1,\ldots,n\}$ se tiene que $b_j,c_j$ son reales tales que $b_j^2-4c_j<0$.

Demostración. Mostraremos la existencia de la factorización. La parte de la unicidad es sencilla, y su demostración queda como tarea moral. Si $p(x)$ es irreducible, entonces al factorizar su coeficiente principal $a$ obtenemos la factorización deseada. Si $p(x)$ no es irreducible, procedemos por inducción fuerte sobre el grado $d$ de $p(x)$. El menor grado que debe tener es $2$ para no ser irreducible.

Si $d=2$ y es no irreducible, el resultado es cierto pues se puede factorizar como dos factores lineales y luego factorizar al término $a$ los coeficientes principales de cada factor para que queden mónicos.

Sea $d\geq 3$ y supongamos el resultado cierto para todo polinomio de grado menor a $d$. Tomemos un polinomio $p(x)$ de grado $d$. Por el teorema de irreducibilidad de polinomios reales, $p(x)$ no es irreducible, así que se puede factorizar como $p(x)=r(x)s(x)$ con $r(x)$ y $s(x)$ no constantes, y por lo tanto de grado menor al de $p(x)$. Por hipótesis inductiva, tienen una factorización como la del teorema. La factorización de $p(x)$ se obtiene multiplicando ambas. Esto termina la inducción.

$\square$

Veamos cómo podemos usar todas estas ideas en un problema en concreto de factorización en polinomios reales.

Problema. Factoriza al polinomio $x^{12}-1$ en polinomios irreducibles en $\mathbb{R}[x]$.

Solución. Usando identidades de factorización, podemos avanzar bastante:
\begin{align*}
x^{12}-1&=(x^6-1)(x^6+1)\\
&=(x^3-1)(x^3+1)(x^6+1)\\
&=(x-1)(x^2+x+1)(x+1)(x^2-x+1)(x^2+1)(x^4-x^2+1).
\end{align*}

Hasta aquí, $x+1$ y $x-1$ son factores lineales. Además, $x^2+x+1$, $x^2-x+1$ y $x^2+1$ son factores cuadráticos irreducibles pues sus discriminantes son, respectivamente, $-3,-3,-4$.

Aún queda un factor $x^4-x^2+1$ que por ser de grado $4$ no es irreducible. Sumando y restando $2x^2$, y luego factorizando la diferencia de cuadrados, tenemos:
\begin{align*}
x^4-x^2+1 &= x^4+2x^2+1-3x^2\\
&=(x^2+1)^2-3x^2\\
&=(x^2+1-\sqrt{3}x)(x^2+1+\sqrt{3}x).
\end{align*}

Cada uno de estos factores cuadráticos tiene discriminante $-1$, y por lo tanto es irreducible. Concluimos entonces que la factorización en irreducibles de $x^{12}-1$ en $\mathbb{R}[x]$ es
\begin{align*}
(x-1)(x&+1)(x^2+1)(x^2+x+1)\\
&(x^2-x+1)(x^2+\sqrt{3}x+1)(x^2-\sqrt{3}x+1).
\end{align*}

$\square$

Más adelante…

El teorema fundamental del álgebra y sus consecuencias en $\mathbb{R}$ son los resultados algebraicos más importantes que obtendremos en el estudio de polinomios, ya que nos permite caracterizar, al menos en teoría a todos los polinomios a partir de sus raíces.

En las siguientes entradas ocuparemos las herramientas que hemos desarrollado hasta ahora, sin embargo cambiaremos el enfoque de estudio, usaremos también herramientas de los cursos de cálculo para poder dar un análisis más detallado del comportamiento de los polinomios, y que nos servirán para que en muchos casos podamos encontrar las raíces de un polinomio, o cuando menos tener una idea de cómo son.

Tarea moral

  • Haz la construcción formal de $\mathbb{C}[x]$ a partir de sucesiones de complejos. Muestra que se pueden expresar en la notación de $x$ y sus potencias. Prueba los teoremas que hemos visto hasta ahora. Todo debe ser análogo al caso real, por lo que te servirá mucho para repasar los conceptos vistos hasta ahora.
  • Muestra la unicidad de la factorización en $\mathbb{C}[x]$ y en $\mathbb{R}[x]$.
  • Sea $z$ un complejo no real. Muestra que que $x-z$ y $x-\overline{z}$ son polinomios primos relativos en $\mathbb{C}[x]$.
  • Hay que tener cuidado en las hipótesis de los teoremas de esta entrada. Muestra que $3$ es una raíz del polinomio $x^3-6x^2+11x-6$, pero que $x^2-6x+9$ no divide a este polinomio.
  • Argumenta por qué en el teorema de factorización en polinomios reales sucede que $m+2n$ es el grado de $p(x)$.

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: Coeficientes binomiales

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

Los coeficientes binomiales aparecen en muchos problemas de matemáticas, y por ello es útil conocerlos bien y saber sus propiedades básicas. En esta entrada hablaremos de varios aspectos de los coeficientes binomiales: algebraicos, combinatorios y de teoría de números. Aunque resolvamos un problema con una técnica en particular, te recomendamos intentar usar las distintas herramientas en otros problemas, para conocer sus alcances y limitaciones.

Antes de empezar, ponemos una figura con un hecho curioso acerca de los coeficientes binomiales:

Coeficientes binomiales, Pascal y Fibonacci
«Las sumas de las diagonales del triángulo de Pascal dan los números de Fibonacci»

Definición algebraica de coeficientes binomiales

Como recordatorio, para $n\geq 0$ un entero, definimos $n!$ recursivamente como $0!=1$ y $n!=n(n-1)!$. En otras palabras, para $n\geq 1$ tenemos $$n!=1\cdot 2\cdot \ldots \cdot n.$$

Definimos para $n\geq 0$ un entero y $k$ un entero en $\{0,\ldots,n\}$al coeficiente binomial $n$ en $k$ como $$\binom{n}{k}:=\frac{n!}{k!(n-k)!}.$$ Si $n$ es un entero negativo o $k$ es un entero fuera del rango $\{0,\ldots,n\}$ es conveniente definir $\binom{n}{k}=0$.

A partir de la definición, es claro que $\binom{n}{n}=\binom{n}{0}=1$ para todo entero positivo $n$. Lo que no es inmediato a partir de la definición es que $\binom{n}{k}$ siempre sea un entero. Veremos eso en la siguiente sección.

Mientras tanto, veamos algunas propiedades de los coeficientes binomiales que se pueden verificar sin mostrar que $\binom{n}{k}$ es entero.

Propiedad (simetría). $\binom{n}{k}=\binom{n}{n-k}.$

Propiedad (fórmula de Pascal). $\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}.$

Propiedad (propiedad de entrada-salida). $\binom{n+1}{k+1}=\frac{n+1}{k+1}\binom{n}{k}.$

El siguiente problema se puede resolver usando estas identidades.

Propiedad (suma cambiando arriba). Muestra que para $n$ y $k$ enteros positivos se tiene que $$\sum_{j=0}^k \binom{n+j}{n} = \binom{n+k+1}{n+1}.$$

Sugerencia pre-solución. Primero, formula un problema equivalente usando la propiedad de simetría. Luego, procede por inducción y usa otra de las propiedades de coeficientes binomiales mencionada arriba.

Solución. Usando la propiedad de simetría de coeficientes binomiales, el problema es equivalente a demostrar que $$\sum_{j=0}^k \binom{n+j}{j} = \binom{n+k+1}{k}.$$ Fijemos un entero $n\geq 0$ y hagamos inducción sobre $k$. Para $k=0$, la identidad es cierta pues $$\binom{n}{0}=1=\binom{n+1}{0}.$$

Para $k=1$, tenemos que mostrar que $\binom{n}{0}+\binom{n+1}{1}=\binom{n+2}{1}$. El primer término se puede escribir como $\binom{n+1}{0}$, pues ambos son $1$. Así, lo que hay que mostrar es $$\binom{n+1}{0}+\binom{n+1}{1}=\binom{n+2}{1},$$ que es cierto por la fórmula de Pascal.

Suponiendo el resultado cierto para una $k$ dada, mostraremos que es cierto para $k+1$. Esto se sigue de la siguiente cadena de igualdades, en donde en la segunda igualdad usamos la hipótesis inductiva, y en la tercera la fórmula de Pascal:

\begin{align*}
\sum_{j=0}^{k+1} \binom{n+j}{j} &= \sum_{j=0}^{k} \binom{n+j}{j}+\binom{n+k+1}{k+1}\\
&=\binom{n+k+1}{k}+\binom{n+k+1}{k+1}\\
&=\binom{n+k+2}{k+1}.
\end{align*}

Esto termina la inducción.

$\square$

Existen otras formas de demostrar identidades con coeficientes binomiales, y de hecho una misma identidad se puede mostrar de varias formas. Veamos más técnicas.

Aspectos combinatorios de los coeficientes binomiales

El coeficiente binomial $\binom{n}{k}$ cuenta la cantidad de subconjuntos de tamaño $k$ de un conjunto de tamaño $n$. Argumentar esto es relativamente fácil, usando un argumento de doble conteo. Supongamos que dicha cantidad de subconjuntos es igual a $A$.

Respondamos la pregunta, ¿cuántos vectores de $k$ entradas existen, tales que las entradas son distintas y vienen de un conjunto de $n$ elementos? La pregunta es un poco distinta, pues como tenemos vectores, aquí sí importa el orden de los elementos. Supongamos que la respuesta es $B$.

Una forma de responder la pregunta es la siguiente. Primero, elegimos cuál subconjunto de tamaño $k$ conformará las entradas. Esto se puede hacer de $A$ formas (que aunque no sepamos cuánto vale, lo podemos usar). Luego, hay que ordenar las $k$ entradas elegidas, que se puede hacer de $k!$ maneras. Así, esto muestra que $B=k! A$.

Otra forma de responder la pregunta es la siguiente. Elegimos el primer elemento, que se puede hacer de $n$ formas. Luego el segundo, de entre los $n-1$ restantes, que se puede hacer de $n-1$ formas. Siguiendo de esta manera, el último de los $k$ hay que elegirlo entre $n-k+1$ restantes. Así, esta otra forma de contar dice que $$B=n\cdot(n-1)\cdot\ldots\cdot (n-k+1)=\frac{n!}{(n-k)!}.$$

Como ambas formas de contar son válidas, tenemos que $k!A=B=\frac{n!}{(n-k)!}$, de donde $A=\frac{n!}{k!(n-k)!}=\binom{n}{k}$.

Hay problemas que de lejos parecen preguntar algo de álgebra, pero que pueden ser interpretados en términos combinatorios para dar una solución.

Problema. Para $n$ un entero positivo, muestra que $$\sum_{k=1}^n k \binom{n}{k} = n 2^{n-1}.$$

Sugerencia pre-solución. Construye un problema de conteo cuya respuesta se pueda poner tanto en términos del lado izquierdo, como en términos del lado derecho.

Solución. Preguntémonos, ¿de cuántas formas se puede elegir un subconjunto de un conjunto de $n$ elementos en el que uno de sus elementos está pintado de azul?

Por un lado, primero se puede elegir qué elemento va a ser el azul. Hay $n$ formas de hacer esta elección, y ésta forza a que el elemento en azul esté en el subconjunto. Luego, de los $n-1$ elementos restantes hay que elegir un subconjunto para completar la elección, lo cual se puede hacer de $2^{n-1}$ formas posibles. Así, una forma de contar da $n2^{n-1}$.

Por otro lado, primero se puede decidir de qué tamaño $k$ va a ser el subconjunto. Como hay un elemento especial, el tamaño $k$ va de $1$ a $n$. Ya elegido $k$, hay $\binom{n}{k}$ formas de elegir cuál será el subconjunto. Ya elegido el subconjunto, hay $k$ formas de elegir cuál será el elemento pintado de azul. Así, otra posible respuesta, también correcta, es $\sum_{k=1}^n k \binom {n}{k}$.

Como estamos contando lo mismo con ambas expresiones, concluimos la igualdad del problema.

$\square$

A este método de resolver problemas se le conoce como contar de dos formas distintas y funciona no sólo con coeficientes binomiales, sino también con cualquier otra expresión algebraica que tenga términos que se puedan interpretar de manera combinatoria. Hay otro ejemplo en el blog, en donde vemos cómo aparecen los números de Fibonacci en el triángulo de Pascal. En esa entrada también hablamos de cómo aparecen los coeficientes binomiales en el triángulo de Pascal.

Coeficientes binomiales y binomio de Newton

La interpretación combinatoria de los coeficientes binomiales nos da una demostración para la fórmula del binomio de Newton, que ya vimos en una entrada anterior. Aquí enunciamos la fómula como recordatorio.

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*}

Si en el binomio de Newton ponemos $a=b=1$, obtenemos $$\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=(1+1)^n=2^n.$$ Otra forma de probar esta identidad es simplemente notar que tanto la suma de la izquierda como el término de la derecha cuentan la cantidad de subconjuntos de un conjunto de $n$ elementos: la de la izquierda los cuenta por tamaño, y el de la derecha decidiendo para cada elemento si está o no.

Si ponemos $a=1$, $b=-1$, obtenemos que $$\binom{n}{0}-\binom{n}{1}+\ldots+(-1)^n\binom{n}{n} = 0,$$ o bien $$\binom{n}{0}+\binom{n}{2}+\ldots = \binom{n}{1}+\binom{n}{3}+\ldots.$$

Se obtienen otras identidades de coeficientes binomiales interesantes si se usan raíces $n$-ésimas de la unidad, como ya vimos en la entrada de aritmética compleja.

Hay otras formas de usar el binomio de Newton para probar identidades de coeficientes binomiales.

Problema. Muestra que $$\binom{n}{0}^2+\binom{n}{1}^2+\ldots+\binom{n}{n}^2=\binom{2n}{n}.$$

Sugerencia pre-solución. Considera el polinomio $(1+x)^{2n}$.

Solución. Consideremos el polinomio $(1+x)^{2n}$ y determinemos el coeficiente de su término $x^n$.

Usando el binomio de Newton directamente, tenemos que $$(1+x)^{2n}=\sum_{j=0}^{2n} \binom{2n}{j}x^j,$$ de modo que el coeficiente de $x^n$ es $\binom{2n}{n}$.

Por otro lado, podemos escribir $(1+x)^{2n}=(1+x)^n(1+x)^n$. Usando el binomio de Newton, tenemos $$(1+x)^n=\sum_{j=0}^n \binom{n}{j} x^j.$$ Al multiplicar esta expresión consigo misma, los términos que quedan de grado $n$ son cuando, para cada $j$, elegimos en un paréntesis al término que tiene $x^j$ (que tiene coeficiente $\binom{n}{j}$) y en el otro al que tiene a $x^{n-j}$ (que tiene coeficiente $\binom{n}{n-j}$).

De esta forma, el coeficiente del término de grado $n$ es $$\sum_{j=0}^n \binom{n}{j} \binom{n}{n-j}.$$ Usando la identidad de simetría, podemos cambiar $\binom{n}{n-j}$ por $\binom{n}{j}$, para obtener $$\sum_{j=0}^n \binom{n}{j}^2.$$ Igualando ambas formas de encontrar el coeficiente, obtenemos la identidad deseada.

$\square$

Hay otras técnicas que usan herramientas de integrales o derivadas. Vimos un ejemplo de esto en una entrada anterior.

Coeficientes binomiales y teoría de números

El hecho de que los coeficientes binomiales son la respuesta a un problema de conteo, implica que son enteros no negativos. Alternativamente, esto se puede demostrar por inducción usando la identidad de Pascal.

Este hecho nos puede ayudar a resolver problemas de teoría de números. Veamos un ejemplo clásico.

Problema. Muestra que el producto de $n$ enteros consecutivos siempre es divisible entre $n!$.

Sugerencia pre-solución. Haz una división en casos para ver si se incluye al cero, si son sólo negativos o sólo positivos. Reduce el caso de negativos a positivos y usa notación adecuada para escribir al producto de dichos enteros usando un coeficiente binomial.

Solución. Si alguno de los enteros es $0$, entonces el producto es $0$, que es divisible entre cualquier número. Si son $n$ enteros negativos, entonces podemos cambiar el signo a todos y su producto diferirá, quizás, en un factor $-1$ que no afecta la divisibilidad, y habremos obtenido un problema con $n$ enteros positivos consecutivos. De esta manera, podemos enfocarnos en el caso de $n$ enteros positivos consecutivos.

Llamemos al primero $k+1$, para $k\geq 0$. Los demás son entonces $k+2,\ldots,k+n$. Su producto es
\begin{align*}
(k+1)(k+2)\ldots(k+n)&=\frac{k!}{k!}(k+1)(k+2)\ldots(k+n)\\
&=\frac{(n+k)!}{k!}\\
&=n!\binom{n+k}{k}.
\end{align*}

Como $\binom{n+k}{k}$ es un entero, tenemos que el lado derecho es un múltiplo de $n!$, como queríamos.

$\square$

Otro tipo de técnicas hablan de la divisibilidad de un coeficiente binomial. Por ejemplo si tenemos un primo $p$, sabemos que todos los siguiente coeficientes binomiales son enteros $$\binom{p}{1}, \binom{p}{2},\ldots,\binom{p}{p}.$$ Por su expresión en términos de factoriales, todos tienen a $p$ en el numerador, pero no tienen ningún divisor de $p$ distinto de $1$ en el denominador, pues $p$ es primo. Así, todos ellos son enteros divisibles entre $p$. Eso puede ayudar en problemas como el siguiente.

Problema. Muestra que si $p$ es un número primo, entonces $p^2$ divide a $\binom{2p}{p} -2$.

Sugerencia pre-solución. Formula un problema equivalente usando un resultado anterior.

Solución. Por un problema anterior, $$\binom{2p}{p}=\binom{p}{0}^2+\binom{p}{1}^2+\ldots+\binom{p}{p}^2.$$

Por la discusión previa, para $j=1,\ldots,p-1$ tenemos que $p\mid \binom{p}{j}$, así que $p^2\mid \binom{p}{j}^2$. De esta forma, trabajando módulo $2p$ tenemos \begin{align*}
\binom{2p}{p}&\equiv \binom{p}{0}^2+\binom{p}{p}^2 \\
&\equiv 1+1\equiv 2 \pmod{p^2}.
\end{align*}

Esto es justo lo que queríamos mostrar.

$\square$

Más problemas

Puedes encontrar más problemas de coeficientes binomiales en la sección 5.1 del libro Problem Solving through Problems de Loren Larson.

Teorema de navidad de Fermat: primos suma de dos cuadrados

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Comentario de Leo: Esta es una escrita en conjunto con por Alexandher Vergara, estudiante en ESFM. En ella hablamos del teorema de navidad de Fermat, una idea de la prueba y de las consecuencias. Si quieres contribuir con algún tema de matemáticas, puedes contactarme por correo electrónico, o dejando un comentario aquí en el blog.

Introducción

En entradas anteriores hemos visto temas de teoría de números, como divisibilidad y teoría de congruencias. También hablamos acerca de números primos y del teorema fundamental de la aritmética. A continuación probaremos una parte del famoso «teorema de navidad de Fermat», el cual dice cuáles primos impares son la suma de dos cuadrados.

Teorema (teorema de Navidad de Fermat). Un número primo $p>2$ es la suma del cuadrado de dos enteros si y sólo si $p\equiv 1 \pmod 4$.

Enunciado del teorema de Navidad de Fermat

El teorema recibe este nombre pues Fermat escribió una carta con muchos detalles acerca del resultado para Mersenne, cuya fecha fue el 25 de diciembre de 1640.

Este resultado nos lleva un paso más adelante en teoría de números. Por un lado, tiene «el mismo sabor» que el teorema de los cuatro cuadrados de Lagrange.

Teorema (teorema de los cuatro cuadrados de Lagrange). Todo entero no negativo puede ser escrito como suma de los cuadrados de cuatro números enteros.

Por otro lado, el teorema de Navidad de Fermat también nos ayuda a demostrar un caso particular del teorema de Dirichlet para primos sobre progresiones aritméticas.

Teorema 1. Hay infinitos números primos de la forma $4k+1$ e infinitos números de la forma $4k+3$.

El teorema de Dirichlet es una generalización de este resultado.

Teorema (teorema de Dirichlet). Si $a$ y $b$ son primos relativos, entonces existe una infinidad de primos $p$ tales que $p\equiv a \pmod b$.

Las demostraciones de los teoremas de Lagrange y de Dirichlet requieren de varios argumentos para los cuales aún no hemos desarrollado teoría suficiente. La idea de esta entrada de blog es demostrar el teorema de Navidad de Fermat y usarlo para demostrar el Teorema 1.

El teorema de Navidad de Fermat

En la demostración del teorema de navidad de Fermat usaremos el siguiente resultado.

Teorema 2. Si $p$ es un número primo y la ecuación $a^2+1 \equiv 0 \pmod p$ tiene solución para algún $a$, entonces $p$ se puede representar como una suma de dos cuadrados.

Por el momento, no nos enfocaremos en demostrar este resultado auxiliar. Existen muchas pruebas en la literatura, por ejemplo, una por J.H. Grace usando latices de enteros (The four square theorem).

Demostración del teorema de Navidad de Fermat. Supongamos primero que $p=x^2+y^2$ para enteros no negativos $x,y$. El hecho de que $p \equiv 1 \pmod 4$ se desprende de dos propiedades del anillo $\mathbb{Z}_4$. Notemos primero que cualquier entero impar es congruente con $1 \pmod 4$ o con $3\pmod 4$. Además, cualquier cuadrado es congruente con $0 \pmod 4$ o $1\pmod 4$, pues si $x$ es congruente con $0,1,2,3 \pmod 4$ entonces $x^2$ es congruente con $0,1,0,1 \pmod 4$, respectivamente. Como $p=x^2+y^2$, sabemos entonces que $$p\equiv x^2+y^2=0,1 \text{ \’o } 2 \pmod 4.$$ Pero $p$ es un primo mayor que $2$, entonces $p$ es impar. Así, $p\equiv 1 \pmod 4$.

Observación. En esta parte de la prueba en realidad es un poco más general, pues muestra que si $n$ es un entero impar que se puede representar como suma de dos cuadrados, entonces $n\equiv 1 \pmod 4$.

Supongamos ahora que $p\equiv 1 \pmod 4$. Lo primero que haremos es mostrar que $a^2+1\equiv 0 \pmod p$ tiene solución para alguna $a$, y después usaremos el Teorema 2 para obtener que $p$ es suma de dos cuadrados.

Primero, examinaremos los factores en $$(p-1)!=1\cdot 2 \cdot \ldots \cdot \frac{p-1}{2} \cdot \frac{p+1}{2}\cdot \ldots \cdot (p-2) \cdot (p-1).$$ A los últimos $(p-1)/2$ factores los pensamos como sigue: $p-1\equiv -1 \pmod p$, $p-2\equiv -2\pmod p$, …, $\frac{p+1}{2}\equiv -\frac{p-1}{2} \pmod p$. El factorial se convierte entonces en
\begin{align*}
(p-1)!&\equiv 1\cdot \ldots \cdot \left(\frac{p-1}{2}\right) \cdot \left(-\frac{p-1}{2}\right) \cdot \ldots \cdot (-1)\\
&\equiv (-1)^{(p-1)/2} \left(1\cdot \ldots \cdot \frac{p-1}{2}\right)^2 \pmod p.
\end{align*}

Definiendo $a= 1\cdot \ldots \cdot \frac{p-1}{2}$, lo anterior se puede escribir como $$(p-1)!\equiv (-1)^{(p-1)/2} a^2 \pmod p.$$

Por el teorema de Wilson, $(p-1)!\equiv -1 \pmod p$. Como $p\equiv 1 \pmod 4$, tenemos $p=4k+1$ para algún entero $k$. Entonces, $(p-1)/2=2k$, que es par, de modo que $(-1)^{(p-1)/2}=1$. De esta forma, tenemos que $$-1\equiv a^2 \pmod p.$$ Sumando $1$ de ambos lados, tenemos que $a^2+1\equiv 0 \pmod p$. Aplicando el Teorema 2, concluimos que $p$ es suma de dos cuadrados.

$\square$

Infinidad de primos de las formas $4k+1$ y $4k+3$

Todos los primos mayores que $2$ son impares, así que son o bien de la forma $4k+1$, o bien de la forma $4k+3$. Sabemos además que hay una infinidad de números primos. ¿Será cierto que hay una infinidad de ellos de la forma $4k+1$ y una infinidad de ellos de la forma $4k+3$?

Por el principio de las casillas, tiene que suceder por lo menos alguna de estas dos opciones. Si hubiera una cantidad finita de la forma $4k+1$ y de la forma $4k+3$, entonces por el párrafo anterior habría sólo una cantidad finita de primos, lo cual es una contradicción.

Lo que dice el Teorema 1 es más fuerte. Lo volvemos a poner aquí por conveniencia para el lector.

Teorema 1. Hay infinitos números primos de la forma $4k+1$ e infinitos números de la forma $4k+3$.

Es decir, el Teorema 1 afirma que para cada uno de los tipos hay una infinidad de primos. Veamos que en efecto esto sucede.

La primera parte del Teorema 1 no necesita que usemos el teorema de Navidad de Fermat.

Proposición 1. Hay una infinidad de primos de la forma $4k+3$.

Demostración. Supongamos que existiera únicamente una cantidad finita $n$ de primos de la forma $4k+3$ y supongamos que ellos son $p_1<\ldots<p_n$, en donde $p_1=3$. Consideremos el número $N=4p_2p_3\ldots p_n +3$ (ojo: no estamos incluyendo al $3$ en la multiplicación). Este número no puede ser primo pues es mayor que $p_n$ y $N\equiv 3\pmod 4$. De esta forma, debe tener al menos un divisor primo.

Tenemos que $N$ es impar, así que $2$ no divide a $N$. Si todos los divisores primos de $N$ fueran $1\pmod 4$, entonces $N$ sería $1\pmod 4$, pero esto no es cierto. De este modo, algún divisor primo $p$ de $N$ debe satisfacer $p\equiv 3 \pmod 4$. Notemos que $p$ no puede ser $3$, pues si $3\mid N$, tendríamos $3\mid 4p_1 \ldots p_n$, pero esto es imposible pues el número de la derecha no tiene ningún factor $3$. Con esto concluimos que $p=p_i$ para algún entero $i=2,\ldots,n$. Sin embargo, si $p_i\mid N$, entonces $p_i\mid N-(p_2\ldots p_n)=3$. Esto también es imposible pues $p_i\neq 3$. Así, es inevitable llegar a una contradicción, por lo que hay una infinidad de primos de la forma $4k+3$.

$\square$

La demostración anterior no funciona directamente para los primos de la forma $4k+1$, pues si hubiera una cantidad finita $n$ de ellos $p_1<\ldots < p_n$ y consideramos al número $4p_1\ldots p_n+1$, este número es congruente con $1\pmod 4$, pero nada garantiza que sus factores primos deban ser de la forma $1\pmod 4$ pues, por ejemplo, $3\equiv 3\pmod 4$, $7\equiv 3\pmod 4$, pero $3\cdot 7 \equiv 21 \equiv 1\pmod 4$. Tenemos que hacer algo distinto.

Proposición 2. Hay una infinidad de primos de la forma $4k+1$.

Demostración. Supongamos que existe una cantidad finita $n$ de primos de la forma $4k+1$ y que son $p_1<\ldots<p_n$. Consideremos al número $N=4(p_1p_2\ldots p_n)^2 +1$. Este número es de la forma $4k+1$. Por esta razón, es imposible que $N$ sea primo, pues es mayor que todo $p_i$.

Sea $p$ un divisor primo de $N$. Como $N$ es impar, $p\neq 2$. Como $p$ divide a $N$, tenemos que $(2p_1\ldots p_n)^2+1\equiv 0 \pmod p$, de modo que $x^2+1\equiv 0 \pmod p$ tiene solución y por el Teorema 2, $p$ se puede escribir como suma de dos cuadrados. Por el teorema de Navidad de Fermat, $p\equiv 1\pmod 4$. De esta forma, $p=p_i$ para alguna $i$. Pero entonces, $p$ divide a $N$ y a $4(p_1\ldots p_n)^2$, de modo que divide a su resta, que es $1$. Esto es imposible. Esta contradicción muestra que hay una cantidad infinita de primos de la forma $4k+1$.

$\square$

El Teorema 1 se sigue de las proposiciones 1 y 2.

¿Dónde seguir?

Aquí en el blog hay otras entradas en donde hablamos acerca de teoría de números. Puedes revisar las siguientes: