Archivo de la etiqueta: primos

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

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 hacen las operaciones y 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 desde 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.

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}&=\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

Tarea moral

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

  • 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 y 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).

Seminario de Resolución de Problemas: Coeficientes binomiales

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

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:

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

Un ejercicio de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio distinto de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio de resolver un sistema de 3 ecuaciones lineales:

Resolviendo un sistema de tres ecuaciones lineales

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

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.