Archivo de la etiqueta: euclides

Seminario de Resolución de Problemas: Factorización de polinomios

Introducción

En la entradas anteriores se trataron algunos temas de identidades algebraicas y se profundizó en el binomio de Newton y la identidad de Gauss. En esta y la siguiente entrada hablaremos de polinomios. Por ahora, comenzaremos recordando las nociones básicas de la aritmética de polinomios y hablando un poco de la factorización de polinomios. Más adelante hablaremos del poderoso teorema de la identidad.

Recordatorio de polinomios

Tenemos que un polinomio de grado n, donde n es un número entero no negativo, es una expresión algebraica de la forma

    \begin{equation*}a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0.\end{equation*}

Dicha expresión también podemos denotarla como

    \begin{equation*}P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0,\end{equation*}

en donde a_n es distinto de 0.

Los elementos \right\{a_n, a_{n-1}, ... , a_0\left\} se conocen como coeficientes. Si a_n=1, decimos que el polinomio es mónico.

Nota: El polinomio cuyos coeficientes son todos ceros, se le conoce como el polinomio cero y no tiene grado.

Si dos polinomios son idénticos coeficiente por coeficiente, decimos que dichos polinomios son iguales. Esta noción será de utilidad más adelante en la entrada del teorema de la identidad.

Si todos los coeficientes de un polinomio son enteros, decimos que es un polinomio sobre los enteros. Si los coeficientes son números reales, entonces es un polinomio sobre los reales. De manera similar definimos a los polinomios sobre los racionales, los complejos o incluso sobre \mathbb{Z}_n. Aunque parezca irrelevante, conocer las características de los coeficientes de un polinomio, nos da mucha información sobre su constitución. Hay resultados que, por ejemplo, se valen para los polinomios sobre los complejos, pero no para los polinomios sobre los reales.

Otra cosa que es de nuestro interés son las operaciones en los polinomios, y es que al igual que los números enteros, podemos sumar, multiplicar y dividir polinomios.

Algoritmo de la división para polinomios

Para los polinomios, al igual que en los números enteros, existe un algoritmo de la división. Este nos ayudará posteriormente para cuando queramos hacer factorización en polinomios.

Teorema. Sean los polinomios P(x) y Q(x) definidos sobre un campo \mathbb{K} con Q(x) distinto de cero. Entonces existen dos únicos polinomios C(x) y R(x) tales que

    \begin{equation*}P(x)=C(x)Q(x)+R(x),\end{equation*}

donde C(x) y R(x) son el coeficiente y el residuo respectivamente, resultado de dividir P(x) entre Q(x), y se tiene que R(x) es el polinomio 0 o bien tiene grado menor o igual al grado de C(x).

Ejemplo. Dados los polinomios P(x)=x^2-3x-28 y Q(x)=x-5, tenemos que C(x)=x+2 y R(x)=-18.

En efecto,

    \begin{equation*}x^2-3x-28=(x+2)(x-5)-18.\end{equation*}

\square

Algoritmo de Euclides para polinomios

Al igual que en los enteros, el algoritmo de la división es de ayuda para determinar el máximo común divisor entre dos polinomios: simplemente seguimos los pasos del algoritmo de Euclides. Es por ello que tenemos el siguiente resultado.

Teorema. Si tenemos dos polinomios P(x) y Q(x) sobre un campo \mathbb{K}, tenemos que existen polinomios S(x) y T(x) tales que

    \begin{equation*}\MCD{P, Q}= PS+QT.\end{equation*}

Aquí \MCD{P, Q} es el máximo común divisor de P(x) y Q(x).

Otra forma de ver o de entender el máximo común divisor entre dos polinomios es como el producto de todos aquellos factores que tienen en común.

Problema: Encuentra polinomios F(x) y G(x) tales que

    \begin{equation*}(x^8-1)F(x)+(x^5-1)G(x)=x-1.\end{equation}

Sugerencia pre-solución. Recuerda cómo encontrar el máximo común divisor de dos enteros usando el algoritmo de Euclides. Además, usa una factorización para cancelar el factor x-1 de la derecha.

Solución. Definamos

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

Notemos que la ecuación es equivalente a

    \begin{equation*}A(x)F(x)+B(x)G(x)=1.\end{equation}

Tendría que suceder entonces que A(x) y B(x) sean primos relativos.

Aplicando el algoritmo de la división repetidamente, tenemos lo siguiente:

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

Esto muestra que A(x) y B(x) son primos relativos, así que la combinación lineal que buscamos debe existir. Para encontrarla de manera explícita, invertimos los pasos. Trabajando hacia atrás, tenemos que

    \begin{equation*}\begin{split}1 & =(x^2+x+1)-x(x+1)\\& =(x^2+x+1)-x(B(x)-x^2(x^2+x+1))\\& =(x^2+x+1)(x^3+1)-xB(x)\\& =(x^3+1)(A(x)-x^3(B(x))-xB(x)\\& =(x^3+1)A(x)-x^3(x^3+1)B(x)-xB(x)\\& =(x^3+1)A(x)+(-x^6-x^3-x)B(x)\end{split}\end{equation*}

Así que podemos tomar a F(x)=x^3+1 y G(x)=-x^6-x^3-x.

\square

El teorema del factor

Sea P(x) un polinomio sobre un dominio entero D. Decimos que un elemento a de D es raíz del polinomio P(x) si P(a)=0. Si aplicamos el algoritmo de la división en los polinomios P(x) y x-a obtenemos el siguiente teorema, que es fundamental en la factorización de polinomios.

Teorema El elemento a es raíz de P(x) si y solo si (x-a) es factor de P(x).

Veamos cómo aplicar este teorema en un ejemplo concreto.

Problema. Dado \omega=\cos\left(\frac{2\pi}{n}\right)+i\sin\left(\frac{2\pi}{n}\right), prueba que

    \begin{equation*}x^{n-1}+\ldots+x+1=(x-\omega)(x-\omega^2)\cdot\ldots\cdot(x-\omega^{n-1}).\end{equation*}

Sugerencia pre-solución. Recuerda los resultados básicos de aritmética de los números complejos.

Solución. Por De Moivre tenemos que si

    \begin{equation*}\omega=\cos\left(\frac{2\pi}{n}\right)+i\sin\left(\frac{2\pi}{n}\right)=e^{\frac{2\pi i}{n}}\end{equation*}

entonces \{1, \omega, \omega^2,...,\omega^{n-1}\} son raíces de x^n-1=0. Además, como e^{\pi i}=-1, tenemos que \omega^n=1.

Así, tenemos que \omega^{n+1}=\omega y de manera general \omega^{n+k}=\omega^k.

Por otro lado,

    \begin{equation*}x^n-1=(x-1)(x^{n-1}+\ldots+x+1)\end{equation*}

Y como \{1, \omega, \omega^2,\ldots,\omega^{n-1}\} son raíces de x^n-1, tenemos entonces que \{\omega, \omega^2,\ldots,\omega^{n-1}\} deben de ser las raíces de

    \[x^{n-1}+\ldots+x+1.\]

Aplicando repetidamente el teorema del factor, tenemos que

    \begin{equation*}x^{n-1}+\ldots+x+1=(x-\omega)(x-\omega^2)\cdot\ldots\cdot(x-\omega^{n-1}).\end{equation*}

\square

Un problema para números algebraicos

Un número real es algebraico si es raíz de un polinomio sobre los números enteros.

Problema. Prueba que \sqrt{2}+\sqrt{3} es un número algebraico.

Sugerencia pre-solución. Realiza operaciones de suma, resta y producto con \sqrt{2}+\sqrt{3} y con enteros. Ve si puedes encontrar un patrón de cómo se comportan.

Solución. Tenemos que encontrar un polinomio P(x) sobre los número enteros de tal forma que P(\sqrt{2}+\sqrt{3})=0.

Si consideramos x=\sqrt{2}+\sqrt{3}, entonces x^2=5+2\sqrt{6}

Para P(x)=x^2-5, tenemos que P(\sqrt{2}+\sqrt{3})=2\sqrt{6}

Así,

    \begin{equation*} (P(\sqrt{2}+\sqrt{3}))^2=(2\sqrt{6})^2=144.\end{equation*}

Ahora, si consideramos el polinomio

    \begin{equation*}Q(x)=(P(x))^2-144.\end{equation*}

Tenemos que

    \begin{equation*}Q(\sqrt{2}+\sqrt{3})=(P(\sqrt{2}+\sqrt{3}))^2-144=0.\end{equation*}

Por lo tanto como el polinomio Q(x)=x^4-10x^2-119 es un polinomio sobre los enteros, y como Q(\sqrt{2}+\sqrt{3})=0 concluimos que \sqrt{2}+\sqrt{3} es un número algebraico.

\square

Más problemas

Puedes encontrar más problemas de aritmética y factorización de polinomios en la Sección 4.2 del libro Problem Solving through Problems de Loren Larson.

Seminario de Resolución de Problemas: Máximo común divisor

Con esta entrada comenzamos a tratar los temas de números enteros y su aritmética. Varios de los temas que se ven aquí se estudian a profundidad en un curso de Álgebra Superior, así que varios de los resultados los enunciaremos sin demostración. Lo que nos interesa es cómo se pueden utilizar los resultados principales de la teoría de números enteros para la resolución de problemas matemáticos.

Divisibilidad y máximo común divisor

Trabajaremos todo el tiempo con números enteros, a menos que digamos lo contrario.

Decimos que a divide a b si b es un mútiplo de a, es decir, si existe un r tal que b=ra. Lo escribimos en símbolos como a\mid b. También decimos que a es divisor de b.

Proposición 1. La relación de divisibilidad es reflexiva y transitiva, pero no es simétrica. Si a\mid b y b\mid a, entonces |a|=|b|, es decir a=b o a=-b.

Si tenemos varios números a_1,\ldots,a_n, el máximo común divisor es el mayor número que divide a todos. El mínimo común múltiplo es el menor entero positivo que es múltiplo de todos. Los denotamos respectivamente por \MCD{a_1,\ldots,a_n} y \mcm{a_1,\ldots,a_n}.

Proposición 2. Si n divide a a y a b, entonces divide a cualquier combinación lineal entera ra+sb de ellos. En particular, si n divide a dos términos de la igualdad a+b=c, entonces divide al tercero.

Notemos que a+(b-a)=b. Por la Proposición 2, un divisor de a y b será divisor de b-a, y uno de b-a y de a será divisor de b. De aquí sale que \MCD{a,b}=\MCD{a,b-a}

Problema. Determina todas las funciones f:\mathbb{Z}^+\times \mathbb{Z}^+ \to \mathbb{Z}^+ tales que cumplen las siguientes tres propiedades simultáneamente:

  1. f(a,a)=a para todo entero positivo a.
  2. f(a,b)=f(b,a) para todo par de enteros positivos a y b.
  3. f(a,b)=f(a,a+b) para todo par de enteros positivos a y b.

Sugerencia pre-solución. Haz casos particulares que puedas obtener a partir de esas propiedades para conjeturar el valor de f(a,b) para todos a y b enteros positivos. Intenta probar tu conjetura por inducción fuerte.

Solución. Vamos a mostrar que f(a,b)=\MCD{a,b} para todo par de enteros positivos a y b. Vamos a probarlo por inducción sobre la suma a+b. Como a y b son enteros positivos, la menor suma que pueden tener es 2 y en este caso a+b=2 implica a=b=1. Por la hipótesis 1, tenemos f(1,1)=1, que coincide con \MCD{1,1}.

Supongamos que el resultado es cierto cuando a+b=k para todo entero k=1,\ldots,n y tomemos a y b enteros de suma n+1. Si a=b, entonces

    \[f(a,b)=f(a,a)=a=\MCD{a,a}=\MCD{a,b},\]

como queremos. Si a\neq b, por la simetría que nos da la hipótesis 2 podemos suponer b>a. Por la hipótesis 3,

    \[f(a,b)=f(a,a+(b-a))=f(a,b-a).\]

En la expresión de la derecha, tenemos que sus entradas suman a+(b-a)=b<a+b=n+1, de modo que podemos aplicar la hipótesis inductiva para obtener que f(a,b-a)=\MCD{a,b-a}. Por la discusión antes de este problema, \MCD{a,b-a}=\MCD{a,b}. Así, concluimos que f(a,b)=\MCD{a,b}, como queríamos.

\square

El máximo común divisor y el mínimo común múltiplo de un número son especiales. No sólo son el divisor más grande y el múltiplo más chico, sino que además si hay otro divisor de todos los números (o múltiplo de todos los números), además se cumplen ciertas divisibilidades.

Proposición 3. Si tenemos otro número d que sea divisor de a_1,\ldots,a_n, entonces

    \[d\mid \MCD{a_1,\ldots,a_n}.\]

Si tenemos otro número M que sea múltiplo de a_1,\ldots,a_n, entonces

    \[\mcm{a_1,\ldots,a_n}\mid M.\]

Problema. Sean a y b enteros positivos. Muestra que

    \[\MCD{a,b}\mcm{a,b}=ab.\]

Sugerencia pre-solución: Intenta resolver el problema antes de ver la solución. Para ello, necesitarás la Proposición 1 y la Proposición 3.

Solución. Para simplificar la notación, tomamos D=\MCD{a,b} y m=\mcm{a,b}.

Como D divide a a y b, existen enteros r y s tales que a=rD y b=sD. Notemos que rsD=as=br, así que rsD es un múltiplo de a y b, y por la Proposición 3, tenemos que m\mid rsD. Multiplicando por D esta divisibilidad, tenemos que Dm\mid rsD^2=ab.

Como ab es múltiplo de a y de b, por la Proposición 3 es múltiplo de m, digamos ab=km. Notemos que de aquí, tenemos a=k(m/b) con m/b entero y b=k(m/a) con m/a entero, de modo que k divide a a y a b. Como D es máximo común divisor, por la Proposición 3 tenemos que k\mid D. Multiplicando por m esta divisibilidad, tenemos que km\mid DM, es decir, ab\mid Dm.

Con esto logramos conseguir que ab\mid Dm y Dm\mid ab. Por la Proposición 1, tenemos que |ab|=|Dm|, pero como a, b, D, m son positivos, entonces ab=Dm.

\square

Algoritmo de la división y algoritmo de Euclides

Tomemos a y b enteros. Si intentamos expresar a a como múltiplo de b, puede que no lo logremos. Pero podemos acercarnos lo más posible y dejar un residuo «pequeño». Esto es lo que dice el algoritmo de la división.

Teorema 1 (Algoritmo de la división). Para enteros a y b\neq 0, existen únicos enteros q y r tales que 0\leq r < |b| y a=bq+r.

Consideremos la igualdad a=bq+r en el algoritmo de la división y apliquemos la Proposición 2. Si d divide a a y b, entonces divide a r. Si d divide a r y a b, entonces divide a a. Así, \MCD{a,b}=\MCD{b,r}, en donde b y r ahora son números más chicos que a y b. De este modo, podemos hacer varias veces el algoritmo de la división para obtener igualdades

    \begin{align*}a&=bq_1+r_1\\b&=r_1 q_2 + r_2\\r_1&= r_2q_3 + r_3\\&\vdots\\r_{n-2}&= r_{n-1}q_n + r_n\\r_{n-1}&= r_nq_{n+1} + 0\\ \end{align*}

de las que obtenemos

    \[\MCD{a,b}=\MCD{b,r_1}=\ldots=\MCD{r_n,0}=r_n.\]


En las igualdades llegamos a un residuo 0 pues b>r_1>r_2>r_3>\ldots\geq 0 es una sucesión estrictamente decreciente de enteros no negativos.

En particular, obtenemos

    \[\MCD{a,b}=r_n.\]

A esto se le conoce como el algoritmo de Euclides, que enunciamos en otras palabras a continuación.

Teorema 2 (Algoritmo de Euclides). Podemos obtener el máximo común divisor de a y b aplicando el algoritmo de la división a a y b, a b y el residuo obtenido y luego repetidamente a los residuos que se van obteniendo. El último residuo no cero es \MCD{a,b}.

Hay todavía una conclusión adicional muy importante que podemos obtener a partir del algoritmo de Euclides.

Problema. Sean a\geq b enteros. Sean q_i y los r_i los números obtenidos en el algoritmo de Euclides. Definimos recursivamente una sucesión de n+1 vectores en \mathbb{R}^3 como sigue:

    \begin{align*}v_1&=(a,1,0)\\v_2&=(b,0,2)\\v_{i+2}&=v_{i}-q_iv_{i+1}\quad \text{para $i=1,\ldots,n-1$}\end{align*}

Sean r_{-1}=a y r_{0}=b. Muestra que para i=1,2,3,\ldots,n+1 se tiene que v_i=(x_i,y_i,z_i), en donde:

  • x_i=r_{i-2}
  • x_i=ay_i+bz_i

Sugerencia pre-solución. Intenta resolver el problema haciendo inducción sobre el índice. Los casos i=1,2 son inmediatos.

Solución. Procedemos por inducción fuerte en el subíndice i. Para i=1,2, el resultado es cierto pues x_1=a=r_{-1}, x_2=b=r_0, a=1\cdot a + 0 \cdot b y b=0 \cdot a + 1\cdot b. Supongamos el resultado cierto para los índices 1,2,\ldots, k para algún 2\leq k\leq n. Tomemos el índice k+1.

Estudiemos primero la entrada x_{k+1}. Por definición de la recursión e hipótesis inductiva

    \begin{align*}x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\&=r_{k-3}-q_{k-1}r_{k-2}\\&=r_{k-1},\end{align*}

que es lo que queríamos mostrar para la entrada x_{k+1}. Para la segunda parte, de nuevo usando la recursión e hipótesis inductiva, tenemos que

    \begin{align*}x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\&=ay_{k-1}+bz_{k-1} - q_{k-1} (ay_{k}+bz_{k})\\&=a(y_{k-1}-q_{k-1}y_k) + b(z_{k-1}-q_{k-1}z_k)\\&=ay_{k+1}+bz_{k+1}.\end{align*}

Con esto terminamos la inducción.

\square

El problema anterior nos dice que, en particular, r_n=ay_n+bx_n. Esta conclusión es muy importante y la enunciamos como teorema.

Teorema 3. El máximo común divisor de enteros a y b se puede escribir como combinación lineal entera de a y b, es decir, existen enteros m y n tales que \MCD{a,b}=am+bn.

Veamos un ejemplo concreto de cómo podemos usar el problema para encontrar la combinación lineal que da el máximo común.

Problema. Expresa al máximo común divisor de 754 y 221 como combinación lineal entera de estos números.

Solución. Hacemos la siguiente tabla, en donde ponemos a los vectores del problema como vectores columna (en los renglones 2,3,4). En el primer rengón vamos apuntando las q_i.

3223
7542219139130
101-25-17
01-37-1758

Explicamos un poco más de donde sale la tabla. Las primeras dos columnas son los vectores v_1 y v_2 del problema, que son (754,1,0) y (221,0,1). Para la tercer columna, nos preguntamos ¿cuántas veces cabe 221 en 754? La respuesta es 3, así que ponemos un 3 arriba (para acordarnos) y hacemos la resta de la primera columna menos tres veces la segunda. Eso va en la tercer columna.

Para la cuarta columna, nos preguntamos ¿cuántas veces cabe 91 en 221? La respuesta es 2, así que lo apuntamos arriba, y la cuarta columna es la segunda, menos dos veces la tercera. Continuamos así hasta que obtengamos un 0. La columna anterior nos dice que 13 es el máximo común divisor, y que la combinación lineal es

    \[13=754\cdot 5 + 221 \cdot 58\]

.

\square

Aquí hay otros dos problemas con aplicaciones de las ideas que vimos en esta entrada.

Problema. Muestra que para todo entero n se tiene que la fracción \frac{41-6n}{9n-61} es irreducible para todo entero.

Sugerencia pre-solución. Intenta resolver el problema. Lo que quieres mostrar es que 41-6n y 9n-61 nunca tienen divisores en común.

Solución. Notemos que 41-6n y 9n-61 tienen una combinación lineal que da 1. En efecto,

    \[3\cdot (41-6n) + 2\cdot (9n-61) = 123-18n+18n-122=1.\]

Cualquier entero d que divida a 41-6n y a 9n-61 tiene entonces que dividir a 1, lo cual muestra que \MCD{41-6n,9n-61}=1, y por lo tanto la fracción siempre es irreducible.

\square

Problema. Se tiene un número irracional \alpha para el cual \alpha^{91} y \alpha^{119} son números racionales. Muestra que \alpha^{14} es un número racional.

Sugerencia pre-solución. Encuentra el máximo común divisor de 91 y 119. Recuerda que las potencias de racionales son racionales, y productos de racionales también.

Solución. Como 91=7\cdot 13 y 119=7\cdot 13, tenemos que \MCD{91,119}=7. De esta forma, existen enteros m y n tales que 7=91m+119n, de donde 14=91 \cdot (2m)+119 \cdot(2n).

Sabemos que \alpha^{91} es racional, así que (\alpha^{91})^{2m} también. Análogamente, (\alpha^{119})^{2n} es racional. De esta forma, el número

    \[\alpha^{14}=(\alpha^{91})^{2m}\cdot (\alpha^{119})^{2n}\]

también lo es.

\square

Más ejemplos

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

El Teorema 3 es fundamental para cuando se quieren determinar inversos multiplicativos trabajando módulo n.

Álgebra Superior II: Problemas de divisibilidad

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

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

Álgebra Superior II: Congruencias y el anillo de enteros módulo n

Esta es una serie de entradas de blog para dar seguimiento a los estudiantes de mi curso de Álgebra Superior II durante la época de cuarentena debida al coronavirus.

Introducción

En clases pasadas hemos platicado del algoritmo de la división, del máximo común divisor, el mínimo común múltiplo, de primos, el teorema fundamental de la aritmética, la infinidad del conjunto de primos y del algoritmo de Euclides para encontrar el máximo común divisor.

En esta entrada platicaremos acerca del anillo de los enteros módulo n. La idea de esta entrada es:

  • Dar la intuición a través de un ejemplo concreto
  • Dar la definición formal de a\equiv b \pmod n
  • Definir a \mathbb{Z}_n, el anillo de enteros módulo n, dando sus elementos y sus operaciones de suma y resta.
  • Dar ejemplos adicionales de operaciones concretas.
  • Hablar de cuáles son los elementos de \mathbb{Z}_n que tienen inversos multiplicativos y cuándo \mathbb{Z}_n es un campo.

A grandes rasgos, el anillo de los enteros módulo n consiste en ver a los enteros «como si sólo nos importara el residuo que dejan al dividirse entre n«.

Ejemplo introductorio

Hablemos de las horas que tiene un día. Un día tiene 24 horas y las podemos llamar del 0 al 24 para no tener que hacer distinción entre AM y PM. Por ejemplo, las 4PM serían las 16. Las 10AM simplemente las 10. La hora 24 vamos a pensarla más bien como la hora 0 del siguiente día.

Si son las 8 (de la mañana, pero ya no hace falta aclarar), entonces tres horas después serán las 11. Si son las 10, entonces cuatro horas después serán las 14. Pero si son las 22 y pasan 7 horas, entonces van a ser las 29, pero conviene pensar a esa hora como las 5 (del día siguiente), pues así es más claro qué hora entre 0 y 23 es. Finalmente si son las 17 y pasan 24 horas, entonces la hora que obtenemos es la 17+24=41, pero justo como pasan 24 horas, siguen siendo las 17: aunque el día cambió, la hora no.

De esta discusión recuperamos lo siguiente:

  • En «el mundo de las horas», la hora 29 es la misma que la hora 5. En símbolos, esto lo ponemos como 29\equiv 5 \pmod {24}.
  • Podemos «sumar en el mundo de las horas». Ahí, 10+4 es 14, pero 22+7 es 5. Vamos a escribir 10+4\equiv 14 \pmod {24} y 22+7\equiv 5 \pmod {24}.
  • En «el mundo de las horas», si sumamos 24 horas no pasa nada.

Definición del anillo \mathbb{Z}_n

En el ejemplo de motivación trabajamos con horas, que «se ciclan cada 24». Pero aquí el 24 no tiene nada de especial y de hecho lo podemos hacer con cualquier número n. Comencemos definiendo qué quiere decir que dos enteros sean iguales «en el mundo de n«.

Definición. Sea n un entero positivo. Sean a y b enteros. Vamos a decir que a es congruente con b módulo n si n divide a a-b. En símbolos:

    \[a\equiv b \pmod n \quad \iff \quad n\mid b-a.\]

Proposición. Para todo entero positivo n la relación en \mathbb{Z} de «ser congruente módulo n » es una relación de equivalencia.

Demostración. Tenemos que probar que dicha relación es reflexiva, simétrica y transitiva.

Para ver que la relación es reflexiva, tomemos a en \mathbb{Z}. Tenemos que n divide a 0=a-a, pues n\cdot 0 =0 (dicho de otra forma, 0 está en n\mathbb{Z}). Así, a\equiv a \pmod n.

Veamos ahora que la relación es simétrica. Si a\equiv b \pmod n, entonces n divide a a-b, pero entonces también divide a su inverso aditivo b-a (aquí estamos usando que n\mathbb{Z} es ideal, y que los ideales son cerrados bajo inversos aditivos), de modo que b\equiv a \pmod n.

Finalmente, veamos que la relación es transitiva. Para ello, a partir de enteros a, b y c tales que a\equiv b \pmod n y b\equiv c \pmod n tenemos que mostrar que a\equiv c \pmod n. Por definición, las primeras dos congruencias quieren decir que n divide a a-b y a b-c. Pero sabemos que si un entero divide a dos enteros, entonces divide a su suma. Así, n\mid (a-b)+(b-c)=a-c, que por definición quiere decir que a\equiv c \pmod n.

\square

Ya que «ser congruente módulo n» es una relación de equivalencia, entonces podemos dividir a todo \mathbb{Z} en las clases de equivalencia de esta relación, y escribir como [a]_n a la clase de equivalencia que tiene al entero a. La siguiente proposición muestra que para cada clase de equivalencia siempre podemos encontrar un representante chiquito.

Proposición. Sea n un entero positivo. Se tiene que a\equiv b \pmod n si y sólo si a y b dejan el mismo residuo al dividirse entre n en el algorimo de la división. En particular, para cada a siempre existe un entero r en \{0,1,\ldots,n-1\} tal que a\equiv r \pmod n.

Demostración. Usemos el algoritmo de la división para escribir a=qn+r y b=pn+s con r y s los residuos de la división, que el algoritmo de la división garantiza que están en \{0,1,\ldots,n-1\}.

Si r=s, entonces a-b=(q-p)n, así que n\mid a-b y así a\equiv b \pmod n. Si a\equiv b \pmod n, entonces

    \[n\mid a-b= (q-p)n+(r-s).\]

Como n\mid (q-p)n, entonces n\mid r-s. Sin embargo, usando que r y s están en \{0,1,\ldots,n-1\}, tenemos que r-s es un número entre -(n-1) y n-1, de modo que la única posibilidad es r-s=0, es decir, r=s. Esto prueba la primer parte de la proposición.

Como a y r dejan el mismo residuo r al dividirse entre n, entonces a\equiv r \pmod n.

\square

Ejemplo. Fijemos n=7. Tenemos que las siguientes clases de equivalencia son la misma: [13]_7, [20]_7, [-1]_7. Esto es ya que, por ejemplo, 7 divide a 20-13=14 y 7 divide a 20-(-1)=21. De hecho, todas estas clases son iguales a la clase [6]_7, pues tanto -1, 6, 13 como 20 son números que al dividirse entre 7 dejan residuo 6.

Estamos listos para presentar a los elementos del anillo de enteros módulo n.

Definición. Para n un entero positivo, definimos a Z_n como el conjunto de clases de equivalencia de la relación «ser congruente módulo n«. Por la proposición anterior, tenemos entonces que

    \[Z_n=\{[0]_n, [1]_n, \ldots, [n-1]_n\}\]

Nota que Z_n tiene exactamente n elementos, uno por cada uno de los posibles residuos de dividir un número entre n. Nota también que \mathbb{Z}_n no es lo mismo que el ideal n\mathbb{Z}, y que hay que ser cuidadosos con la notación. De hecho, el ideal n\mathbb{Z} es uno de los elementos de \mathbb{Z}_n.

Ejemplo. Z_4=\{[0]_4,[1]_4, [2]_4,[3]_4\} tiene 4 elementos. El elemento [3]_4 consiste de todos los enteros que dejan residuo 3 al dividirse entre 4, es decir, [\ldots,-5,-1,3,7,\ldots].

Definición. Sea n un entero positivo y [a]_n y [b]_n clases de equivalencia de la relación «ser congruentes módulo n«. Definimos las siguientes operaciones de suma y producto:

  • [a]_n + [b]_n = [a+b]_n, y
  • [a]_n [b]_n = [ab]_n.

Estas operaciones es decir, esta suma y producto «están bien definidas» y no dependen de los representantes elegidos, como muestra la siguiente proposición:

Proposición. Sea n un entero positivo. Si a\equiv a' \pmod n y b\equiv b' \pmod n, entonces a+b \equiv a'+b' \pmod n y ab\equiv a'b' \pmod n.

Demostración. De la primer congruencia tenemos n\mid a-a' y de la segunda n\mid b-b'. Como n divide a estos dos números, divide a su suma, y reacomodando tenemos que n\mid (a+b) - (a'+b'), que es equivalente a a+b\equiv a'+b' \pmod n, una de las congruencias que queríamos.

Para el producto, de n\mid a-a' podemos obtener

    \[n\mid (a-a')b=ab-a'b\]

y de n\mid b-b' podemos obtener

    \[n\mid a'(b-b')=a'b-a'b'.\]

Así,

    \[n\mid (ab-a'b)+(a'b-a'b')=ab-a'b'.\]

De aqui, ab\equiv a'b' \pmod n, la otra congruencia que queríamos.

\square

El anillo de enteros módulo n es precisamente \mathbb{Z}_n equipado con las operaciones de suma y producto que acabamos de definir.

Ejemplos de operaciones en \mathbb{Z}_n

Estos son algunos ejemplos básicos de operaciones en \mathbb{Z}_7 y en \mathbb{Z}_{11}:

  • [8]_7+[4]_7=[12]_7=[5]_7
  • [4]_{11}[8]_{11}=[32]_{11}=[21]_{11}=[10]_{11}

En una siguiente entrada, preparada por Clau, verán más ejemplos de operaciones en \mathbb{Z}_n.

Inversos multiplicativos en \mathbb{Z}_n

El cero del anillo de enteros módulo n es [0]_n, pues para cualquier entero a se tiene que [a]_n+[0]_n=[a+0]_n=[a]_n. Como [0]_n consiste precisamente de los múltiplos de n, tenemos entonces que [a]_n+[kn]_n=[a]_n.

La multiplicación en este anillo tiene como identidad a [1]_n, de lo cual te puedes convencer con una cuenta similar.

La suma de este anillo tiene inversos aditivos pues para cualquier entero a se tiene que la clase de a y la de -a cumplen

    \[[a]_n+[-a]_n=[a+(-a)]_n=[0]_n.\]

Sin embargo, no es cierto que para cualquier clase [a]_n esta tenga un inverso multiplicativo. A los números que sí tienen un inverso multiplicativo se les conoce como unidades del anillo.

Problema: Muestra que [4]_{12} no tiene inverso multiplicativo en \mathbb{Z}_{12}

Intenta resolver este problema antes de ver la solución.

Solución. Procedamos por contradicción. Si [a]_{12} fuera el inverso multiplicativo de [4]_{12}, tendríamos que [1]_{12}=[4a]_{12} y por lo tanto que 4a\equiv 1 \pmod {12}, es decir, que 12\mid 4a-1. Como 4\mid 12 y 4\mid 4a, tendríamos entonces que 4\mid (4a-1)-4a = -1. Esto es una contradicción.

La siguiente proposición dice exactamente quienes son los elementos en \mathbb{Z}_n que tienen inversos multiplicativos en \mathbb{Z}_n.

Teorema. Sea n un entero positivo. La clase [a]_n de \mathbb{Z}_n tiene inverso multiplicativo si y sólo si a y n son primos relativos.

Demostración. Recordemos que por definición a y n son primos relativos si su máximo común divisor MCD(a,n) es igual a 1. Recordemos también que MCD(a,n) puede escribirse como combinación lineal entera de a y n.

Si a y n son primos relativos, entonces existen p y q enteros tales que 1=ap+nq. Así,

    \[[ap]_n=[ap+nq]_n=[1]_n,\]

de modo que la clase [a]_n tiene como inverso multiplicativo a la clase [p]_n.

Si a y n no son primos relativos y suponemos que [a]_n tiene inverso multiplicativo, entonces llegaremos a una contradicción similar a la del problema anterior. Verifica los detalles.

\square

Recuerda que un campo es un anillo conmutativo en el cual todo elemento distinto de cero tiene un inverso multiplicativo. Terminamos esta sesión con un resultado que nos dice cuándo \mathbb{Z}_n es un campo.

Proposición. Sea n un entero. El conjunto \mathbb{Z}_n con las operaciones de suma y producto que definimos es un campo si y sólo si n es un número primo.

Demostración. Como ya sabemos que es un anillo conmutativo, basta con determinar cuándo sucede que todos los elementos distintos de cero tienen un inverso multiplicativo. Estos elementos son son [1]_n, \ldots, [n-1]_n. Por la proposición anterior, estos tienen inversos si y sólo si cada uno de los números 1,2,\ldots,n-1 es primos relativos con n.

Si n es primo, entonces todos esos números son primos relativos con n pues el único factor en común que tienen con n es 1. Si n no es primo, entonces tiene un divisor d que satisface 1<d<n, y por lo tanto n y d no son primos relativos, así que [d]_n no tiene inverso multiplicativo.

De esta forma, \mathbb{Z}_n es un campo si y sólo si n es primo.

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

  • Argumenta por qué «el mundo de los minutos» también es un ejemplo de enteros módulo n.
  • Muestra que n\mathbb{Z} es uno de los elementos de \mathbb{Z}_n.
  • Muestra que las operaciones de suma y producto en \mathbb{Z}_n en efecto satisfacen la definición de anillo conmutativo. Sugerencia: aprovecha que \mathbb{Z} es un anillo conmutativo con sus operaciones de suma y producto.
  • Muestra que [1]_n es identidad para el producto en \mathbb{Z}_n.
  • Completa la prueba del teorema de inversos multiplicativos.

Busca una contradicción

HeuristicasTerminamos esta serie de técnicas de resolución de problemas con una de las técnicas más finas y más usadas en las matemáticas: las pruebas por contradicción.

La idea es la siguiente. Por un momento suponemos que lo que queremos demostrar es falso. Después trabajaremos haciendo todo lo demás correctamente. La idea es llegar a una contradicción con las hipótesis del problema, o bien a algo que sabemos que es imposible. De esta forma, sabemos que debe haber un error en la demostración de eso imposible. Y como lo único que hicimos mal fue suponer que lo original era falso, debemos tener que en realidad es verdadero.

En estos videos veremos varios ejemplos de este argumento para acostumbrarnos. Es súper útil pensar en estos argumentos casi automáticamente.

Ir a los videos…