Archivo de la etiqueta: primos relativos

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

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

Un ejercicio de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio distinto de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio de resolver un sistema de 3 ecuaciones lineales:

Resolviendo un sistema de tres ecuaciones lineales

Álgebra Superior II: Teorema chino del residuo

Introducción

En entradas anteriores platicamos de congruencias y de algunos teoremas que se pueden usar para trabajar con potencias y factoriales módulo un entero. También, aprendimos a resolver una ecuación lineal módulo n. El resultado principal fue el siguiente:

Teorema 1. Sean a,b enteros y n un entero positivo. La ecuación ax\equiv b\pmod n tiene solución si y sólo si M:=\text{MCD}(a,n) divide a b. Cuando sí hay solución, ésta se puede expresar de manera única en módulo n':=n/M.

Ya que sabemos resolver una ecuación lineal, el siguiente paso es aprender a resolver sistemas que involucren dos o más ecuaciones lineales. En esta entrada veremos primero cómo resolver un sistema de dos ecuaciones lineales.

Luego, veremos cómo resolver un sistema con más ecuaciones y demostraremos un resultado clásico: el teorema chino del residuo. Pero para eso necesitaremos el resultado para dos ecuaciones lineales. Vamos poco a poco.

Sistemas de dos ecuaciones lineales

Supongamos que queremos entender por completo el sistema de ecuaciones

    \begin{align*}ax&\equiv b \pmod m\\cx&\equiv d \pmod n,\end{align*}

es decir, determinar cuándo existe una x que satisfaga ambas ecuaciones y, si existe, determinar cómo se ven todas las soluciones. Por lo primero que nos tenemos que preocupar es por que cada una de las ecuaciones tenga solución: si alguna no tiene, entonces no hay solución para el sistema.

Así, lo primero que tiene que pasar es que \text{MCD}(a,m) divida a b y que \text{MCD}(c,n) divida a d. Cuando sí tienen solución, entonces podemos intercambiar a las ecuaciones por sus ecuaciones reducidas y obtener el sistema de ecuaciones lineales equivalente

    \begin{align*}a'x&\equiv b' \pmod {m'}\\c'x&\equiv d' \pmod {n'}.\end{align*}

La primera ecuación tiene una única solución módulo m' y la segunda una única solución módulo n', así que este sistema es equivalente al sistema

    \begin{align*}x&\equiv e \pmod {m'}\\x&\equiv f \pmod {n'},\end{align*}

en donde e y f son las soluciones a cada una de las ecuaciones lineales reducidas por separado. Ahora sí podemos combinar ambas ecuaciones. Lo único que nos falta es entender cuándo los sistemas de esta forma tienen solución.

Ejemplo. El sistema lineal de ecuaciones

    \begin{align*}x&\equiv 2 \pmod 6\\x&\equiv  4 \pmod {15}\end{align*}


no tiene solución.

Solución. La primera ecuación implica que 6\mid x-2. Como 3\mid 6, por transitividad tenemos 3\mid x-2, así que la primera ecuación implica que x deja residuo 2 al dividirse entre 3.

La segunda ecuación implica que 15\mid x-4. Como 3\mid 15, por transitividad 3\mid x-4, o bien x\equiv 4 \equiv 1 \pmod 3. Es decir, la segunda ecuación implica que x deja residuo 1 al dividirse entre 3. De esta forma, es imposible satisfacer simultáneamente ambas ecuaciones.

\square

En el ejemplo anterior, 3 es el máximo común divisor de 6 y 15 y por eso convino estudiar la divisibilidad entre 3. La siguiente proposición justo dice cuándo el sistema tiene solución en términos de cierta divisibilidad por el máximo común divisor de los módulos.

Proposición 4. Sean a y b enteros y m y n enteros positivos. El sistema lineal de ecuaciones en congruencias

    \begin{align*}x&\equiv a \pmod m\\x&\equiv b \pmod n\end{align*}

tiene solución si y sólo si M:=\text{MCD}(m,n) divide a a-b. En este caso, la solución se puede expresar de manera única módulo N:=\text{mcm}(m,n), el mínimo común múltiplo de m y n.

Demostración. Supongamos que x es solución. Por la primera ecuación, m\mid x-a y como M\mid m, entonces M\mid x-a. De manera análoga, M\mid x-b. Así, M\mid (x-b)-(x-a)=a-b, lo cual prueba una implicación de la proposición.

Por otro lado, si M divide a a-b, entonces existe una combinación lineal de m y n que da a-b, digamos ym+zn=a-b, que podemos reescribir como b+zn=a-ym. Tomemos x=b+zn=a-ym. Notemos que

    \begin{align*}x&=a-ym\equiv a\pmod m\\x&= b+zn \equiv b \pmod n,\end{align*}

de modo que x es solución para el sistema. Notemos que x+rN para cualquier r entero y N el mínimo común múltiplo de m y n también es solución pues N\equiv 0 \pmod m y N\equiv 0 \pmod n.

Veamos que la solución es única módulo N. Si tenemos x y y que son soluciones al sistema, entonces tenemos

    \begin{align*}x&\equiv a \equiv y\pmod m\\x&\equiv b \equiv y\pmod n,\end{align*}

lo cual implica m\mid x-y y n\mid x-y. Como N es el mínimo común múltiplo, N\mid x-y, de modo que x\equiv y \pmod N.

\square

Terminamos esta sección con un teorema que recopila todo lo que hemos mostrado para dos ecuaciones lineales.

Teorema 2. Consideremos el sistema de ecuaciones

    \begin{align*}ax&\equiv b \pmod m\\cx&\equiv d \pmod n.\end{align*}

Si \text{MCD}(a,m) no divide a b o \text{MCD}(c,n) no divide a d, entonces el sistema no tiene solución. Si tenemos ambas divisibilidades, entonces el sistema original es equivalente al sistema

    \begin{align*}x&\equiv e \pmod {m'}\\x&\equiv f \pmod {n'},\end{align*}

donde e y f son las soluciones únicas a las reducciones de la primer y segunda congruencia respectivamente. Si \text{MCD}(m',n') no divide a e-f, entonces el sistema original no tiene solución. Si sí, entonces el sistema original tiene una única solución módulo \text{mcm}(m',n').

Ejemplo. Determina las soluciones al siguiente sistema lineal de ecuaciones:

    \begin{align*}4x&\equiv 12 \pmod {24}\\10x&\equiv 5 \pmod {75}.\end{align*}

Solución. Para la primera ecuación, notamos que \text{MCD}(4,24)=4 sí divide a 12 así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de x\equiv 3\pmod 6.

Para la segunda ecuación, notamos que \text{MCD}(10,75)=5 sí divide a 5 así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de 2x\equiv 1\pmod {15}. La solución de esta ecuación es x\equiv 8 \pmod {15}. De este modo, el sistema original es equivalente al sistema:

    \begin{align*}x&\equiv 3 \pmod {6}\\x&\equiv 8 \pmod {15}.\end{align*}


Tenemos que \text{MCD}(6,15)=3. Pero 3 no divide a 3-8=-5. Entonces este sistema no tiene solución, y por lo tanto el original tampoco.

\square

Hagamos un ligero cambio en el sistema de ecuaciones.

Ejemplo. Determina las soluciones al siguiente sistema lineal de ecuaciones:

    \begin{align*}4x&\equiv 20 \pmod {24}\\10x&\equiv 5 \pmod {75}.\end{align*}

Solución. Para la primera ecuación, notamos que \text{MCD}(4,24)=4 sí divide a 20 así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de x\equiv 5\pmod 6.

Para la segunda ecuación, notamos que \text{MCD}(10,75)=5 sí divide a 5 así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de 2x\equiv 1\pmod {15}. La solución de esta ecuación es x\equiv 8 \pmod {15}. De este modo, el sistema original es equivalente al sistema:

    \begin{align*}x&\equiv 5 \pmod {6}\\x&\equiv 8 \pmod {15}.\end{align*}


Tenemos que \text{MCD}(6,15)=3 y que 3 sí divide a 5-8=-3, de modo que sí hay solución. Para encontrarla, expresamos a -3 como combinación lineal de 6 y 15:

    \[5-8= -3 = (-3)\cdot 6 + 1\cdot 15.\]

De aquí, x=8+15=23 es una solución, y por lo tanto el conjunto de soluciones queda descrito módulo \text{mcm}(6,15)=30 de manera única como

    \[x\equiv 23 \pmod {30}\]

.

\square

El teorema chino del residuo

Varias de las ideas que usamos para un sistema de dos ecuaciones lineales las podemos reciclar para cuando queremos encontrar una x que satisfaga simultáneamente el sistema de ecuaciones lineales en congruencias

    \begin{align*}a_1x&\equiv b_1\pmod {m_1}\\ a_2x&\equiv b_2\pmod {m_2}\\&\vdots\\ a_nx&\equiv b_n\pmod {m_n}\end{align*}

Si este sistema tiene solución, entonces claramente:

  • Cada una de las ecuaciones debe tener solución y,
  • cada par de ellas debe tener solución.

Lo impresionante del siguiente teorema es que estas dos condiciones son las únicas que tenemos que verificar para que el sistema tenga solución. Y afortunadamente ya estudiamos cuándo dos ecuaciones lineales en congruencias tienen una solución simultánea.

Si cada una de las ecuaciones del sistema tiene solución, entonces es única, así que podemos remplazar cada ecuación por su solución y obtener un sistema de ecuaciones en donde todos los coeficientes de x son 1 (como le hicimos en el caso de dos ecuaciones). El siguiente resultado estudia estos sistemas.

Teorema 3. Sea n\geq 2 un entero, b_i enteros para i\in \{1,\ldots,n\} y m_i enteros positivos para i\in \{1,\ldots,n\}. El sistema de ecuaciones en congruencias

    \begin{align*}x&\equiv b_1\pmod {m_1}\\ x&\equiv b_2\pmod {m_2}\\&\vdots\\ x&\equiv b_n\pmod {m_n}\end{align*}


tiene solución si y sólo si para cada par de índices i y j en \{1,2,\ldots,n\} se tiene que la ecuación i y la ecuación j tienen solución, es decir, si y sólo si \text{MCD}(m_i,m_j)\mid b_i-b_j. En este caso, la solución es única módulo \text{mcd}(m_1,\ldots,m_n).

Demostración. Si el sistema completo tiene solución, entonces claramente cualquier par de ecuaciones tiene solución. Para demostrar la afirmación inversa, procederemos por inducción. Para n=2 la afirmación es directa, pues justo la hipótesis es que ese par de ecuaciones tiene solución.

Supongamos entonces el resultado cierto para cuando tenemos n ecuaciones y consideremos un sistema con n+1 ecuaciones

    \begin{align*}x&\equiv b_1\pmod {m_1}\\ x&\equiv b_2\pmod {m_2}\\&\vdots\\ x&\equiv b_n\pmod {m_n}\\ x&\equiv b_{n+1}\pmod {m_{n+1}}.\end{align*}

Supongamos que cualquier par de ellas tienen solución. Tenemos que mostrar que todo el sistema tiene solución y que es única módulo \text{mcm}(m_1,\ldots,m_{n+1}). Como cualquier par tienen solución, entonces cualquier par de las primeras n tienen solución. Por hipótesis inductiva, entonces podemos reemplazar a las primeras ecuaciones por una ecuación módulo N=\text{mcm}(m_1,\ldots,m_{n}), que es única por la unicidad en la hipótesis inductiva. En otras palabras, existe un entero c tal que el sistema de ecuaciones original es equivalente al sistema de ecuaciones

    \begin{align*}x&\equiv c \pmod N\\x&\equiv b_{n+1} \pmod {m_{n+1}}\end{align*}

Mostraremos ahora que este sistema tiene solución. Para esto, basta mostrar que \text{MCD}(N,m_{n+1}) divide a c-b_{n+1}.

Como c es solución del sistema para las primeras n ecuaciones, tenemos que c\equiv b_i\pmod {m_i} para toda i=1,\ldots, n, es decir, m_i\mid c-b_i. Por transitividad, \text{MCD}(m_{n+1},m_i)\mid c-b_i.

Como cualquier par de ecuaciones de las originales tenía solución, tenemos que \text{MCD}(m_{n+1},m_i)\mid b_i-b_{n+1}. De esta forma,

    \[\text{MCD}(m_{n+1},m_i)\mid -(c-b_i)-(b_i-b_{n+1})=b_{n+1}-c.\]

Con esto mostramos que cada \text{MCD}(m_{n+1},m_i) divide a b_{n+1}-c, de modo que el mínimo común múltiplo de estos números también divide a b_{n+1}-c. Pero el mínimo común múltiplo de estos números precisamente \text{MCD}(N,m_{n+1}).

En otras palabras, el sistema

    \begin{align*}x&\equiv c \pmod N\\x&\equiv b_{n+1} \pmod {m_{n+1}},\end{align*}

que es esquivalente al original, tiene una solución, y esta es única módulo

    \[\text{mcm}(N,m_{n+1})=\text{mcm}(m_1,\ldots,m_n,m_{n+1}).\]

Esto es justo lo que queríamos para dar el paso inductivo.

\square

Como corolario, obtenemos el teorema chino del residuo, que habla acerca de soluciones a sistemas de ecuaciones en los cuales los módulos que tomamos son primos relativos entre sí.

Teorema 4 (teorema chino del residuo). Sea n\geq 2 un entero, b_i enteros para i\in\{1,2,\ldots,n\} y m_i enteros positivos para i\in\{1,\ldots,n\}. Supongamos además que cada par m_i, m_j de enteros (i\neq j) son primos relativos. Entonces el sistema lineal de congruencias

    \begin{align*}x&\equiv b_1\pmod {m_1}\\ x&\equiv b_2\pmod {m_2}\\&\vdots\\ x&\equiv b_n\pmod {m_n}\end{align*}


tiene una y sólo una solución módulo m_1m_2\ldots m_n.

Demostración. Como cada pareja de módulos son primos relativos, tenemos que \text{MCD}(m_i,m_j)=1 y entonces claramente cada par de ecuaciones tiene solución. Por el Teorema 3, el sistema tiene solución y esta es única módulo el mínimo común múltiplo de m_1,\ldots,m_n, que como son primos relativos dos a dos, es m_1m_2\ldots m_n.

\square

La demostración del Teorema 3 también nos da un procedimiento para resolver de manera práctica los sistemas de ecuaciones lineales en congruencias:

  • Si los coeficientes de x del sistema no son 1, entonces primero resolvemos todas las ecuaciones con coeficiente distinto de 1 para transformarla en una del estilo de las del Teorema 3. Si alguna no se puede, entonces el sistema no tiene solución.
  • Una vez que el sistema está en la forma del Teorema 3, verificamos si cada par de ecuaciones tienen solución calculando los máximos comunes divisores de dos en dos y viendo que dividen a las restas respectivas. Si alguno de estos pares falla, entonces el sistema no tiene solución.
  • Si todos los pares cumplen la hipótesis, entonces resolvemos las primeras dos ecuaciones para remplazarlas por otra módulo su mínimo común múltiplo. Luego, usamos esa que obtuvimos y la tercera para remplazarlas por otra. Seguimos así hasta que sólo nos queden dos ecuaciones. La solución a esas será la solución al sistema original.

Ejemplo. Resolvamos el siguiente sistema de congruencias:

    \begin{align*} x&\equiv 11 \pmod{5}\\ x&\equiv 5 \pmod{7}\\x&\equiv 7 \pmod{11}\end{align*}


Solución. Los números 5, 7 y 11 son primos relativos por parejas, de modo que la solución existe y es única módulo 5\cdot 7 \cdot 11= 385. Para encontrarla, primero resolvemos las primeras dos ecuaciones. Estas corresponden al sistema

    \begin{align*} x&\equiv 11\equiv 1 \pmod{5}\\ x&\equiv 5 \pmod{7}\end{align*}

Para encontrar la solución, ponemos a 1-5=-4 como combinación lineal de 5 y 7, que tras explorar un poco, se puede hacer así: 1-5=-4=2\cdot 5 + (-2)\cdot 7. De este modo, la solución es x\equiv 5-14 \equiv -9 \equiv 26 \pmod{35} (este es un buen momento para substituir en las dos ecuaciones originales y ver que todo vaya bien).

Así, el sistema original es equivalente al sistema

    \begin{align*} x&\equiv 26 \pmod{35}\\ x&\equiv 7 \pmod{11}\end{align*}

Ahora lo que tenemos que hacer es expresar a 26-7=19 como combinación lineal de 35 y 11. Es difícil encontrar una combinación “al tanteo”, así que aquí es mejor usar el algoritmo de la división de Euclides:

    \begin{align*}35&=3\cdot 11 + 2\\11&=2\cdot 5 + 1\end{align*}

De aquí,

    \[1=11-2\cdot 5=11-(35-3\cdot 11)\cdot 5 = (-5)\cdot 35 +  16\cdot 11,\]

por lo que

    \[19=(-5\cdot 19)\cdot 35 + (19\cdot 16)\cdot 11=(-95)\cdot 35 + (304)\cdot 11.\]

Así, la solución al sistema está dada por x=7+304\cdot 11=3351\equiv 271 \pmod {385}.

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

  • Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 2 sí son soluciones de la ecuación original.
  • Cuando un sistema de dos ecuaciones en módulos m y n sí tiene solución, ¿cuántas soluciones módulo mn tiene?
  • Usando (\ldots) para máximo común divisor y [\ldots] para mínimo común múltiplo, demuestra que para cualesquiera enteros m_1,m_2,\ldots,m_n se tiene que

        \[([m_1,\ldots,m_n],m_{n+1})=[(m_1,m_{n+1}),\ldots,(m_n,m_{n+1})].\]

  • Verifica que las soluciones del último ejemplo en efecto satisfacen el sistema de ecuaciones inicial.
  • Problema. Demuestra que para cualquier entero n\geq 1 existen n enteros consecutivos tal que la factorización en primos de cada uno de ellos usa al menos dos primos diferentes.

Álgebra Superior II: Ejercicios de los teoremas de Fermat y de Wilson

Primero, un ejercicio más de congruencias:

Un ejercicio de congruencias

Un ejercicio utilizando el teorema de Fermat:

Ejercicio utilizando el teorema de Fermat

Ejercicio sencillo utilizando el Teorema de Wilson:

17!=1 (mod 19)

Otro ejercicio utilizando el Teorema de Wilson:

Si p primo, (p-1)! = -1 (mod p)

Álgebra Superior II: Ecuaciones en congruencias

Introducción

En entradas anteriores platicamos de congruencias y de algunos teoremas que se pueden usar para trabajar con potencias y factoriales módulo un entero. Ya que tenemos un buen manejo de la aritmética en congruencias, podemos comenzar a hacernos preguntas acerca de las ecuaciones que pueden se plantear y resolver en estos términos.

Ejemplo. ¿Cuáles son las soluciones enteras a la ecuación x\equiv 3 \pmod 6?

Solución. Un número x satisface la ecuación si y sólo si 6 divide a x-3, lo cual sucede si y sólo si x es de la forma x=6r+3, donde r es un número entero. Así, el conjunto de soluciones es de la forma

    \[6\mathbb{Z}+3:= \{6r+3: r\in \mathbb{Z}\}.\]

Dicho de otra forma, el conjunto de soluciones es la clase de equivalencia del 3 módulo 6, es decir, [3]_6.

\square

Cuando tengamos ecuaciones más complicadas, usualmente lo que haremos es dejar expresada la solución en términos de congruencias, es decir, como uno o varios elementos de \mathbb{Z}_n. Si se quiere encontrar a todos los enteros (en \mathbb{Z}) que sean solución, basta recordar este ejemplo para expresar a las soluciones en \mathbb{Z}_n como conjuntos de soluciones en \mathbb{Z}.

Ejemplo. ¿Cuáles son las soluciones enteras a la ecuación 2x+1\equiv 0 \pmod 7?

Solución. Trabajemos módulo 7. Restando 1 de ambos lados obtenemos

    \[2x\equiv -1\equiv 6 \pmod 7.\]

Multiplicando por 4 de ambos lados tenemos que

    \[8x\equiv 24\equiv 3\pmod 7.\]

Como 8x\equiv x \pmod 7, tenemos que x\equiv 3 \pmod 7 es la solución.

\square

En el ejemplo anterior encontramos las soluciones módulo 7. Si queremos encontrar las soluciones en enteros, basta expresar esta congruencia en términos de enteros: las soluciones en \mathbb{Z} son los números de la forma 7r+3 con r entero.

Ecuaciones lineales en congruencias

Una ecuación lineal en congruencias es de la forma

    \[ax\equiv b\pmod n.\]

Vamos a estudiar esta ecuación, viendo cuándo tiene solución y cuántas soluciones módulo n tiene. Hay un caso fácil de estudiar, que es cuando a y n son primos relativos.

Proposición 1. Sean a,b enteros y n un entero positivo tales que \text{MCD}(a,n)=1. Entonces la ecuación

    \[ax\equiv b \pmod n\]

tiene una única solución x módulo n.

Demostración. Como a y n son primos relativos, a tiene un inverso multiplicativo módulo n, digamos a^{-1}. Afirmamos que x=a^{-1}b es solución. En efecto, a(a^{-1}b)\equiv 1\cdot b\equiv b \pmod n.

Ahora, afirmamos que la solución es única. Supongamos que x y y son solución. Tendríamos entonces que

    \[ax\equiv b \equiv ay \pmod n.\]

Multiplicando ambos extremos de esta ecuación por a^{-1}, tenemos que

    \[x\equiv a^{-1}ax\equiv a^{-1}a y \equiv y \pmod n.\]

\square

Sin embargo, como ya vimos antes, no siempre pasa que todo elemento tenga inverso multiplicativo. Necesitamos un análisis más detallado.

Notemos que x es solución de ax\equiv b\pmod n si y sólo si n divide a ax-b, lo cual sucede si y sólo si existe un entero y tal que ax-b=ny. Reordenando, tenemos que ax-ny=b. En otras palabras, la ecuación en congruencias tiene solución si y sólo si podemos expresar a b como combinación lineal entera de a y n, lo cual sucede si y sólo si

    \[b\in a\mathbb{Z} + n \mathbb{Z}=\text{MCD}(a,n)\mathbb{Z},\]

es decir, si y sólo si b es múltiplo del máximo común divisor de a y n. Resumimos esta primer parte del análisis en la siguiente proposición.

Proposición 2. Sean a,b enteros y n un entero positivo. La ecuación ax\equiv b\pmod n tiene solución si y sólo si \text{MCD}(a,n) divide a b.

Ahora, queremos entender cuántas soluciones diferentes hay módulo n.

Ejemplo. Encuentra todas las soluciones a la ecuación 4x\equiv 1 \pmod 8 y a la ecuación 4x\equiv 0 \pmod 8.

Solución. Tenemos que \text{MCD}(4,8)=4 y que 4 no divide a 1, así que la primer ecuación no tiene solución. Tenemos que 4 sí divide a 0, así que la segunda ecuación sí tiene solución. Veamos cuántas tiene.

Notemos que al multiplicar por 4 cada uno de los elementos 0,2,4,6 obtenemos respectivamente 0,8,16,24, que son todos múltiplos de 8, así que estos elementos de \mathbb{Z}_8 son solución. Al multiplicar 4 por 1,3,5,7 obtenemos 4,12,20,28, que módulo 8 son 4,4,4,4, así que ninguno de estos números son solución. Así, las soluciones son x\equiv 0,2,4,6\pmod 8.

\square

Una forma alternativa de expresar la solución del problema anterior es darse cuenta de que las soluciones en enteros son los números pares, o bien los enteros n tales que n\equiv 0\pmod 2. En general, cuando la solución existe, podemos encontrar un módulo en la que la podemos describir de manera única. Este es el contenido de las siguientes dos proposiciones.

Proposición 3. Sean a,b enteros y n un entero positivo tales que M=\text{MCD}(a,n) divide a b. Sean a'=a/M, b'=b/M y n'=n/M (con a', b', n' enteros). El entero x es solución a la ecuación en congruencias ax\equiv b \pmod n si y sólo si es solución a la ecuación en congruencias a'x\equiv b'\pmod {n'}.

Demostración. Tenemos que x es solución a ax\equiv b \pmod n si y sólo si existe una combinación lineal entera ax-ny=b. Al dividir entre M\neq 0, esto sucede si y sólo si a'x-n'y=b', lo cual sucede si y sólo si x es solución a la ecuación en congruencias a'x\equiv b'\pmod {n'}.

\square

Estamos listos para enunciar el resultado principal de esta sección. Viene de la combinación de las ideas anteriores.

Teorema 1. Sean a,b enteros y n un entero positivo. La ecuación ax\equiv b\pmod n tiene solución si y sólo si M:=\text{MCD}(a,n) divide a b. Cuando sí hay solución, ésta se puede expresar de manera única en módulo n':=n/M.

Demostración. La primer parte es la Proposición 2. Una vez que sabemos que la ecuación tiene solución, por la Proposición 3 podemos encontrar la ecuación equivalente a'x\equiv b'\pmod {n'}, en donde a'=a/M y b'=b/M. En esta ecuación, a' y n' son primos relativos (ver Tarea moral abajo). Por la Proposición 1, tiene una solución única módulo n'.

\square

Como empezamos con una ecuación módulo n, quizás queremos saber cuántas soluciones tiene módulo n, y no módulo n'. De manera inmediata, obtenemos el siguiente resultado.

Corolario. Con la notación del teorema anterior, cuando la ecuación tiene solución, entonces tiene M soluciones módulo n.

Ejercicio. Resuelve la ecuación lineal en congruencias

    \[12x\equiv 18 \pmod {30}.\]

Intenta resolver este ejercicio antes de ver la solución. Puedes comenzar calculando el máximo común divisor de 12 y 30.

Solución. El máximo común divisor de 12 y 30 es 6, que sí divide a 18. Entonces sí hay soluciones, y habrá 6 soluciones módulo 30. Para encontrar la ecuación reducida equivalente, dividimos entre 6 para obtener

    \[2x\equiv 3 \pmod 5.\]

El inverso de 2 módulo 5 es 3. Multiplicando en ambos lados por 3 obtenemos la solución

    \[x\equiv 9 \equiv 4 \pmod 5.\]

Para recuperar las soluciones módulo 30, a cada una de estas soluciones le sumamos 30/6=5 repetidamente para obtener las soluciones x\equiv 4, 9, 14, 19, 24, 29 \pmod {30}.

\square

En la siguiente entrada veremos cómo resolver sistemas de ecuaciones lineales en los que tenemos más de una congruencia.

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.

  • Sea a un entero y n un entero positivo. Sea M=\text{MCD}(a,n) y sean a'=a/M y n'=n/M. Muestra que \text{MCD}(a',n')=1.
  • Demuestra el corolario al Teorema 1.
  • Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 1 sí son soluciones de la ecuación original.
  • Diseña una ecuación lineal módulo 60 que tenga exactamente 15 soluciones módulo 60.
  • Para prepararte para la siguiente entrada, intenta resolver por completo el sistema de congruencias

    \begin{align*}x&\equiv -1 \pmod{77}\\x&\equiv -1 \pmod{55}\\\end{align*}