Archivo de la etiqueta: teoría de números

Seminario de Resolución de Problemas: Grupos, anillos y campos

Introducción

En estas entradas hemos visto cómo distintas herramientas de álgebra nos pueden ayudar en la resolución de problemas. En las primeras dos entradas, hablamos de identidades algebraicas básicas y un par de avanzadas. Luego, hablamos de factorización en polinomios y del teorema de la identidad. Ahora platicaremos de cómo estructuras un poco más abstractas nos pueden ayudar. De manera particular, nos enfocaremos en aplicaciones de teoría de grupos a la resolución de problemas. Sin embargo, hacia el final de la entrada también hablaremos un poco acerca de anillos, dominios enteros y campos.

Teoría de grupos básica

Una de las nociones de álgebra abstracta más básicas, y a la vez más flexibles, es la de grupo. La teoría de grupos es muy rica y se estudia a profundidad en un curso de álgebra abstracta o álgebra moderna. Aquí veremos únicamente un poco de esta teoría y algunas aplicaciones a resolución de problemas. Comenzamos con la definición.

Definición. Un grupo es un conjunto no vacío G con una operación binaria \cdot que cumple lo siguiente:

  • Asociatividad: Para cualesquiera elementos x,y,z en G tenemos que x\cdot (y\cdot z) = (x\cdot y) \cdot z.
  • Neutro: Existe un elemento e en G tal que x\cdot e = x = e\cdot x para todo elemento x.
  • Inversos: Para cada elemento x en G, existe un elemento y en G tal que x\cdot y = e = y\cdot x.

Usualmente se simplifica la notación de la siguiente manera. Por un lado, en vez de poner el símbolo de producto, simplemente se ponen elementos consecutivos, por ejemplo a\cdot b = ab. Además, por la asociatividad, muchas veces no se ponen los paréntesis, de modo que expresiones como (a\cdot b)\cdot c se escriben simplemente como abc, a menos que los paréntesis ayuden a entender un argumento.

Hay que tener cuidado con invertir el orden de factores. En grupos, no necesariamente sucede que la operación es conmutativa, es decir, que ab=ba para todo par de elementos a y b. Si ab=ba decimos que a y b conmutan y si todo par de elementos de G conmutan, decimos que G es conmutativo. Un elemento siempre conmuta consigo mismo. Para n un entero positivo definimos a^n como el producto formado por n veces el elemento a.

A partir de la definición se puede ver que el neutro es único, pues si hubiera dos neutros e y e' tendríamos e=e\cdot e'=e', en donde primero usamos que e' es neutro y después que e lo es. Para a en G, definimos a^0 como e.

En grupos se vale “cancelar”. Por ejemplo, si ab=ac, entonces podemos multiplicar esta igualdad a la izquierda por un inverso d de a y obtendríamos

    \[b=eb=dab=dac=ec=c.\]

Del mismo modo, la igualdad ba=ca implica b=c.

En particular, si d y d' son inversos de a, tenemos da=e=d'a, de donde d=d'. Esto muestra que los inversos también son únicos, así que al inverso de a le llamamos a^{-1}. Observa que e^{-1}=e. Nota que si a y b son elementos de G, entonces

    \[ab(b^{-1}a^{-1})=aea^{-1}=aa^{-1}=e,\]

de modo que el inverso de un producto ab es el producto b^{-1}a^{-1}. Para n un entero positivo, definimos a^{-n} como el inverso de a^n, que por lo anterior, es precisamente (a^{-1})^n. De hecho, ya definido a^n para todo entero, se puede verificar que se satisfacen las leyes usuales de los exponentes.

Problema. Sean a y b dos elementos en un grupo G con neutro e tales que aba=ba^2b, a^3=e y b^{2021}=e. Muestra que b=e.

Sugerencia pre-solución. Observa que si a y b conmutaran, entonces el resultado se deduce fácilmente de la primer igualdad. Así, intenta modificar el problema a demostrar que a y b conmutan. Para ello tienes que hacer un paso intermedio que necesita inducción.

Solución. Lo primero que veremos es que a y b^2 conmutan. Poniendo una identidad entre ambas b en el producto ab^2, tenemos que

    \[ab^2=abaa^{-1}b=ba^2ba^{-1}b.\]

De a^3=e, tenemos a^{-1}=a^2, así que siguiendo con la cadena de igualdades,

    \begin{align*}ba^2ba^{-1}b&=ba^2ba^2b\\&=ba^2aba\\&=bba=b^2a.\end{align*}

Así, ab^2=b^2a.

Ahora veremos que a y b conmutan. Para ello, como a y b^2 conmutan, tenemos que a y b^{2k} conmutan para cualquier entero k. Esto se puede probar por inducción. El caso k=1 es lo que ya probamos. Si es válido para cierta k, se sigue que

    \[ab^{2k+2}=b^{2k}ab^2=b^{2k+2}a.\]

Por hipótesis, b^{2020}=b, así que el resultado anterior nos dice que a y b conmutan.

Por esta razón, la primer hipótesis aba=ba^2b se puede reescribir como a^2b=a^2b^2, que por cancelación izquierda da e=b, como queríamos mostrar.

\square

Subgrupos y órdenes

Dentro de un grupo pueden vivir grupos más pequeños.

Definición. Un subgrupo de un grupo G es un subconjunto H de G que es un grupo con las operaciones de G restringidas a H.

Para que H sea subgrupo, basta con que no sea vacío y que sea cerrado bajo la operación de grupos y la operación “sacar inverso”.

Por ejemplo, se puede ver que \matbb{Z}_{12}, los enteros módulo 12 con la suma, forman un grupo. De aquí, H_1=\{0,3,6,9\} es un subgrupo y H_2=\{0,4,8\} es otro.

Proposición. Si a es un elemento de un grupo G, entonces o bien

    \[1,a, a^2, a^3,\ldots\]

son todos elementos distintos de G, o bien existe un entero positivo n tal que a^n=1 y 1,a,\ldots,a^{n-1} son todos distintos. En este segundo caso, \{1,a,\ldots,a^{n-1}\} es un subgrupo de G.

Sugerencia pre-demostración. Divide en casos. Luego, usa el principio de cancelación o las leyes de exponentes para grupos.

Demostración. Si todos los elementos son distintos, entonces no hay nada que hacer. De otra forma, existen i<j tales que a^j=a^i, de donde por la ley de cancelación tenemos que a^{j-i}=e y j-i\geq 1. Así, el conjunto de enteros positivos m tales que a^m=e es no vacío, de modo que por el principio de buen orden tiene un mínimo, digamos n.

Afirmamos que

    \[1,a,a^2,\ldots,a^{n-1}\]

son todos distintos. En efecto, de no ser así, como en el argumento de arriba existirían 0\leq i < j \leq {n-1} tales que a^{j-i}=e, pero j-i\leq n-1 sería una contradicción a la elección de n como elemento mínimo.

Probemos ahora que A=\{1,a,\ldots,a^{n-1}\} es subgrupo de G. Si tenemos a^k y a^l en A, su producto es a^{k+l}. Por el algoritmo de la división, k+l=qn+r, con r\in \{0,\ldots,n-1\}, de modo que

    \[a^ka^l=a^{qn+r}=(a^n)^qa^r=e^qa^r=a^r,\]

así que A es cerrado bajo productos. Además, si 1\leq k\leq n-1, entonces 1\leq n-k \leq n-1 y a^ka^{n-k}=a^n=e. Así, A es cerrado bajo inversos. Esto muestra que A es subgrupo de G.

\square

En teoría de grupos, la palabra “orden” se usa de dos maneras. Por un lado si G es un grupo, su orden \text{ord}(G) es la cantidad de elementos que tiene. Por otro, dado un elemento a, el orden \text{ord}(a) de a es el menor entero positivo n tal que a^n=e, si es que existe.

Definimos al subgrupo generado por a como

    \[\langle a\rangle:=\{a^n:n\in \mathbb{Z}\}.\]

La proposición anterior dice que si \langle a \rangle es finito, entonces es un subgrupo de G de orden \text{ord}(\langle a \rangle) = \text{ord}(a). A los grupos de la forma \langle a \rangle se les llama cíclicos.

Teorema de Lagrange

Cuando estamos trabajando con grupos finitos, el orden de un subgrupo debe cumplir una condición de divisibilidad.

Teorema (de Lagrange). Sea G un grupo finito y H un subgrupo de G. Entonces \text{ord}(H) divide a \text{ord}(G).

No daremos la demostración de este teorema, pero veremos algunos corolarios que sirven en la resolución de problemas.

Proposición. Sea G un grupo finito.

  • Si \text{ord}(G) es un primo p, entonces G es cíclico.
  • El orden de cualquier elemento a de G divide al orden de G, y por lo tanto a^{\text{ord}(G)}=1.
  • Si a es un elemento de G de orden n y a^m=e, entonces n divide a m.

Demostración. Para la primer parte, si tomamos un elemento a de G que no sea e, ya vimos que \langle a \rangle es un subgrupo cíclico de G. Por el teorema de Lagrange, su orden debe dividir al primo p. Pero el orden de \langle a \rangle es al menos 2, así que el orden de \langle a \rangle debe ser p y por lo tanto \langle a \rangle=G.

Como vimos arriba, el orden de a es el orden de \langle a \rangle, que divide a G. Así,

    \begin{align*}a^{\text{ord}(G)}&=(a^{\text{ord}{a}})^{\text{ord}(G)/ \text{ord}(a)}\\&=e^{\text{ord}(G)/ \text{ord}(a)}\\&=e.\end{align*}

Con esto queda probado el segundo punto.

Para el último punto, usamos el algoritmo de la división para escribir m=qn+r, con r entre 0 y n-1. Tenemos que

    \[e=a^m=a^{qn+r}=a^r.\]

Por lo visto en la sección anterior, necesariamente r=0, así que n divide a m.

\square

Veamos cómo se pueden aplicar algunas de las ideas anteriores a un problema de teoría de grupos concreto.

Problema. En un grupo G, tenemos elementos a y b tales que a^7=1 y aba^{-1}=b^2. Determina qué posibles valores puede tener el orden de b.

Sugerencia pre-solución. Conjetura una fórmula para b^{2n} buscando un patrón. Establécela por inducción.

Solución. El orden de a debe dividir a 7, así que es o 1 o 7. Si es 1, entonces a=e, por lo que por la hipótesis tenemos b=b^2. De aquí b=e, así que el orden de b es 1. La otra opción es que el orden de a sea 7.

Afirmamos que para todo entero n se tiene que a^nba^{-n}=b^{2^n}. Esto se prueba inductivamente. Es cierto para n=1 por hipótesis. Si se cumple para cierta n y elevamos la igualdad al cuadrado, tenemos que

    \begin{align*}b^{2^{n+1}}&=(b^{2n})^2\\&=a^nba^{-n}a^nba^{-n}\\&=a^nb^2a^{-n}\\&=a^{n+1}ba^{-(n+1)},\end{align*}

lo cual termina la inducción.

En particular, para n=7 tenemos que a^7=a^{-7}=e, por lo que b=b^{2^7}, y por lo tanto b^{127}=e. Como 127 es primo, el orden de b puede ser 1 ó 127.

\square

En realidad, en el problema anterior falta mostrar que en efecto existe un grupo que satisfaga las hipótesis, y para el cual el orden de b sea exactamente 127. Esto no lo verificaremos aquí.

Teoría de grupos en teoría de números

Lo que hemos platicado de teoría de grupos se vale para grupos en general. Cuando aplicamos estos resultados a grupos particulares, tenemos nuevas técnicas para resolver problemas. Uno de los casos que aparecen más frecuentemente es aplicar teoría de grupos en problemas de teoría de números.

Si tomamos un entero n, los enteros entre 1 y n-1 que son primos relativos con n forman un grupo con la operación de producto módulo n. Si llamamos \varphi(n) a la cantidad de primos relativos con n entre 1 y n-1, el teorema de Lagrange da el siguiente corolario.

Teorema (de Euler). Para todo entero positivo n y a un entero primo relativo con n, se tiene que

    \[a^\varphi(n)\equiv 1\pmod n.\]

Como corolario al teorema de Euler, tenemos el pequeño teorema de Fermat, que hemos discutido previamente aquí en el blog.

Teorema (pequeño teorema de Fermat). Para p un primo y a un entero que no sea múltiplo de p, se tiene que

    \[a^{p-1}\equiv 1 \pmod p.\]

Así, cuando p es primo y a no es múltiplo de p, se tiene que el orden de a divide a p-1. Veamos un ejemplo en donde esta idea forma parte fundamental de la solución.

Problema. Muestra que para ningún entero n>1 se tiene que n divide a 2^n-1.

Sugerencia pre-solución. Procede por contradicción, suponiendo que sí existe. Considera un primo p que divida a n y que además sea extremo en algún sentido. Trabaja módulo p.

Solución. Supongamos que existe un entero n>1 tal que n divide a 2^n-1. Sea p el primo más pequeño que divide a n. Tomemos a el orden de 2 en el grupo multiplicativo \mathbb{Z}_p.

Por un lado, como p divide a n y n divide a 2^n-1, se tiene que p divide a 2^n-1 y por lo tanto

    \[2^n\equiv 1 \pmod p.\]

De esta forma, a divide a n.

Por otro lado, por el pequeño teorema de Fermat, tenemos que

    \[2^{p-1}\equiv 1 \pmod p,\]

así que a divide a p-1 y por lo tanto a\leq p-1.

Si a\neq 1, entonces a tiene un divisor primo que divide a n y es menor que a\leq p-1, lo cual es imposible pues elegimos a p como el menor divisor primo de n. De esta forma, a=1. Pero esto da la contradicción 2\equiv 1 \pmod p.

\square

Anillos, dominios enteros y campos

Cuando se están resolviendo problemas, es importante tener en mente que existen otras estructuras algebraicas. Definiremos sólo las más comunes y veremos un problema ejemplo.

Definición. Un anillo es un conjunto R con dos operaciones binarias suma y producto tales que:

  • R con la suma es un grupo conmutativo.
  • El producto en R es asociativo, es decir (ab)c=a(bc) para a,b,c en R.
  • Se cumple la ley distributiva, es decir a(b+c)=ab+ac y (b+c)a=ba+ca para a,b,c en R.

El producto en R no tiene por qué ser un grupo. De hecho, ni siquiera tiene que tener neutro.

Definición. Si un anillo R tiene neutro, decimos que R es un anillo con 1. Si la multiplicación de R es conmutativa, decimos que R es conmutativo.

Definición. Un dominio entero es un anillo conmutativo con uno en donde además se vale cancelar, es decir, ab=ac implica b=c y ba=ca implica b=c.

Definición. Un campo es un anillo conmutativo con uno en donde cada elemento tiene inverso multiplicativo. En otras palabras, es un anillo en donde la suma y el producto son grupos.

Problema. Muestra que todo dominio entero finito es un campo.

Sugerencia pre-solución. Usa el principio de las casillas.

Solución. Supongamos que R=\{a_1,\ldots,a_n\} es un dominio entero con una cantidad finita de elementos. Lo único que falta para que sea campo es que los elementos tengan inversos multiplicativos.

Sea a un elemento de R y supongamos que a no tiene inverso multiplicativo. Entonces, los números

    \[a_1a, a_2a,\ldots,a_n a\]

sólo pueden tomar a lo más n-1 valores diferentes, de modo que por principio de las casillas existen dos de ellos que son iguales, digamos a_ia=a_ja para i\neq j.

Como R es dominio entero, se vale cancelar, lo cual muestra a_i=a_j. Esto es una contradicción, pues a_i y a_j eran elementos distintos de R. Así, todo elemento tiene inverso multiplicativo.

\square

En cursos de matemáticas a nivel superior se ven muchos ejemplos de estas estructuras algebraicas. En cursos de Álgebra Superior se construye el dominio entero de enteros \mathbb{Z}. Se construyen los campos \mathbb{R}, \mathbb{Q} y \mathbb{C}. También, se construyen los anillos de polinomios \mathbb{F}[x]. La noción de campo es fundamental cuando se construye la teoría de Álgebra Lineal. Como se puede ver, la teoría de álgebra es muy amplia, así que esta entrada sólo queda como invitación al tema.

Más problemas

Puedes encontrar más problemas de estructuras algebraicas en la Sección 4.4 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:

Seminario de Resolución de Problemas: Aritmética de números complejos

Introducción

En entradas anteriores de esta sección hablamos de propiedades aritméticas de números enteros. En esta entrada veremos varias de las propiedades aritméticas de los números complejos y cómo se pueden usar para resolver problemas, incluso aquellos en los que los números complejos no están mencionados de manera explícita en el enunciado.

Distintas formas de los números complejos

La forma más común en la que pensamos en números complejos es en su forma rectangular, en donde un complejo se escribe de la forma z=a+bi, en donde a y b son números reales y pensamos a i como un número tal que i^2=-1. A a le llamamos la parte real y a b la parte imaginaria.

Podemos colocar al complejo z=a+ib en el plano cartesiano, identificándolo con el punto (a,b). De aquí, la forma polar del complejo es z=r(\cos \theta + i \sin \theta), en donde r es la norma |z|:=\sqrt{a^2+b^2} y si z\neq 0, \theta es el argumento, que es el ángulo en el sentido antihorario desde el origen entre el eje horizontal y el punto (a,b). Si z=0+i0=0, no definimos el argumento.

Forma polar y rectangular de un complejo
Forma polar y rectangular de un complejo.

Así como le hacíamos en el caso de trabajar con módulos, a veces conviene pensar que el argumento es el único ángulo en [0,2\pi) que cumple lo anterior. En otras ocasiones, conviene pensar al argumento como a veces que es la clase de todos los ángulos módulo 2\pi.

Cuando tenemos a complejos w=a+ib y z=c+id en forma rectangular, su suma w+z=(a+c) + i(b+d) corresponde geométricamente a encontrar la diagonal del paralelogramo definido por (a,b), (c,d) y el origen, pues corresponde justo al punto (a+c,b+d).

Suma de números complejos
Suma de números complejos.

Su multiplicación wz en forma rectangular es (ac-bd)+(ad+bc)i, que geométricamente no es tan claro que sea.

La forma exponencial z=re^{i\theta} es simplemente una forma de abreviar a la forma polar, pues por definición e^{i\theta}=\cos \theta + i \sin \theta. En forma exponencial, el producto es más sencillo de entender.

Ejercicio. Demuestra lo siguiente:

  • Muestra que la norma es multiplicativa, es decir, que para complejos r y s se tiene que |rs|=|r||s|.
  • Muestra que e^{i\alpha}e^{i\beta}=e^{i(\alpha+\beta)}.

Sugerencia. Para el primer punto, haz las cuentas usando la forma rectangular. Para el segundo punto, escribe las definiciones de todos los términos en forma polar. Haz las multiplicaciones en el lado izquierdo y usa las fórmulas trigonométricas para sumas de ángulos.

Por el ejercicio anterior, si tenemos a los complejos en forma polar w=re^{i\alpha}, z=se^{i\beta}, entonces el producto es wz=rse^{i(\alpha+\beta)}, de modo que el producto corresponde al complejo con el producto de normas y suma de argumentos. En ocasiones esto nos permite plantear algunos problemas geométricos en términos de números complejos.

Producto de números complejos.
Multiplicación de números complejos.


Aplicaciones de aritmética de complejos

Veamos dos aplicaciones de la teoría anterior a problemas que no mencionan en el enunciado a los números complejos.

Problema. Sean a y b enteros. Muestra que el número (a^2+b^2)^n se puede expresar como la suma de los cuadrados de dos números enteros.

Podría ser tentador usar el binomio de Newton para elevar el binomio a la n-ésima potencia. Sugerimos que intentes esto para darte cuenta de las dificultades que presenta.

Sugerencia pre-solución. Escribe a a^2+b^2 como el cuadrado de la norma de un complejo y usa que es multiplicativa.

Solución. El número r=a^2+b^2 es la norma al cuadrado del número complejo z=a+ib. Entonces, el número r^n=(a^2+b^2)^n es la norma al cuadrado del número complejo z^n=(a+ib)^n. Pero al desarrollar (a+ib)^n obtenemos únicamente a i, potencias de a y de b, y coeficientes binomiales. De modo que z^n=(a+ib)^n=c+id con c y d enteros (aquí estamos usando notación adecuada: no es necesario saber quienes son, sólo que son enteros). Así, r^n=c^2+d^2 con c y d enteros.

\square

Veamos ahora un ejemplo de geometría. Este problema es posible resolverlo de muchas formas, pero notemos que los números complejos nos dan una forma de hacerlo de manera algebraica de manera inmediata.

Problema. En la siguiente figura hay tres cuadrados de lado 1 pegados uno tras otro. Determina la suma de los ángulos marcados con \alpha y \beta.

Problema de suma de ángulos
Determinar el valor de la suma \alpha+\beta.

Sugerencia pre-solución. El problema pide determinar una suma de ángulos, así que conviene pensar esta suma de ángulos como el ángulo del producto de dos complejos. Haz tu propia figura, pero ahora sobre el plano complejo.

Solución. El ángulo \alpha es igual al argumento del complejo 2+i y el ángulo \beta es igual al argumento del complejo 3+i. De esta forma, \alpha+\beta es igual al argumento del complejo (2+i)(3+i)=(6-1)+(2+3)i=5+5i. Este complejo cae sobre la recta \text{Re}(z)=\text{Im}(z), de modo que su argumento es \pi / 4.

\square

Este problema también se puede resolver de (numerosas) maneras geométricas, que puedes consultar en este video.

Fórmula de De Moivre

El siguiente teorema se puede demostrar por inducción sobre n.

Teorema (fórmula de De Moivre). Para cualquier entero n y ángulo \theta se tiene que

    \[(\cos \theta + i \sin \theta)^n=\cos (n\theta) + i \sin (n\theta).\]

Dicho de otra forma, en términos de la forma exponencial, se vale usar la siguiente ley de los exponentes

    \[(e^{\theta i})^n=e^{(n\theta) i}.\]

La fórmula de De Moivre es otra herramienta que ayuda a resolver problemas de números reales enunciándolos en términos trigonométricos. El truco consiste en:

  1. Tomar una expresión real que queramos entender.
  2. Identificarla como la parte real o imaginaria de una expresión compleja.
  3. Usar la aritmética de números complejos para entender la expresión compleja.
  4. Regresar lo que entendamos a los reales.

Veamos un par de ejemplos, relacionados con funciones trigonométricas. Comenzamos con una fórma de encontrar la fórmula para el coseno de cinco veces un ángulo.

Problema. Sea \theta\in [0,2\pi). Expresa a \cos 5\theta en términos de \cos \theta.

Sugerencia pre-solución. Identifica a \cos 5\theta como la parte real de un número complejo. Inspírate en la fórmula de De Moivre. Usa binomio de Newton.

Solución. Por la fórmula de De Moivre, \cos 5\theta es la parte real del complejo (\cos \theta + i \sin \theta)^5, así que calculemos quién es exactamente este número usando binomio de Newton. Para simplificar la notación, definimos a=\cos \theta y b=\sin \theta. Tenemos que

    \begin{align*} (a+ib)^5&=a^5+5a^4(bi)+10a^3(ib)^2+10a^2(ib)^3+5a(ib)^4+(ib)^5\\&=(a^5-10a^3b^2+5ab^4) + (5a^4b-10a^2b^3+b^5) i.\end{align*}

Además, por la identidad pitagórica recordemos que a^2+b^2=1, de donde b^2=1-a^2, de modo que la parte real de la expresión anterior es

    \[a^5-10a^3(1-a^2)+5a(1-2a^2+a^4),\]

que agrupando es

    \[16a^5-20a^3+5a.\]

Recordando que a es \cos \theta, obtenemos la fórmula final

    \[\cos 5\theta = 16\cos^5 \theta - 20 \cos^3 \theta + 5\cos \theta.\]

\square

Raíces de la unidad

En muchos problemas se utilizan las raíces de la ecuación x^n=1.

Teorema. Sea n\geq 1 un entero. Las ecuación x^n=1 tiene n soluciones complejas, que en el plano complejo forman los vértices del n-ágono regular con centro en 0 y tal que uno de sus vértices es 1. Si \omega es la raíz de menor argumento positivo, entonces estas soluciones son 1,\omega, \omega^2,\ldots,\omega^{n-1}.

Raíces de la unidad en los números complejos
Raíces n-ésimas de la unidad para n=5.

A estas soluciones les llamamos las raíces n-ésimas de la unidad. Notemos que \omega^{n}=1, y que en general si escribimos a un entero m usando el algoritmo de la división como m=qn+r, entonces \omega^m=\omega^r. ¡Los productos de raíces de la unidad se comportan como los elementos de \mathbb{Z}_n bajo suma módulo n!

Proposición. Sea n\geq 2 un entero. La suma de las n raíces n-ésimas de la unidad es 0 y su producto es 1.

La proposición anterior nos permite, en ocasiones, “filtrar” ciertas expresiones algebraicas. A continuación presentamos un ejemplo, que retomamos de los primeros ejemplos que vimos, cuando estábamos aprendiendo la heurística de encontrar un patrón.

Problema. Determina el valor de la suma

    \[\binom{100}{0}+\binom{100}{3}+\binom{100}{6}+\ldots+\binom{100}{99}.\]

Sugerencia pre-solución. Si no recuerdas lo que debería salir, vuelve a experimentar con los primeros valores, para cuando en vez de usar 100 se usan números más chiquitos. Para entender mejor el patron, generaliza el problema, y en vez de sólo tener múltiplos de 3 abajo, explora también qué sucede cuando tienes los números que dejan residuo 0, 1 o 2 módulo 3.

Ya que recuerdes la fórmula que queremos, considera una raíz cúbica \omega de la unidad distinta de 1. Calcula (1+1)^{100}, (1+\omega)^{100} y (1+\omega^2)^{100} usando el binomio de Newton y aprovechando que toda potencia de \omega es 1, \omega u \omega^2 para simplificar la notación.

Solución. Sea \omega una raíz cúbica de la unidad distinta de 1. Tenemos que \omega^3=1 y que 1+\omega+\omega^2=0. De este modo, podemos usar \omega y el binomio de Newton para calcular las siguientes expresiones

    \begin{align*}(1+1)^{100}&=\binom{100}{0}+\binom{100}{1}+\binom{100}{2}+ \binom{100}{3}+ \ldots\\(1+\omega)^{100}&= \binom{100}{0}+\binom{100}{1}\omega+\binom{100}{2}\omega^2+\binom{100}{3}+\ldots\\(1+\omega^2)^{100}&= \binom{100}{0}+\binom{100}{1}\omega^2+\binom{100}{2}\omega+ \binom{100}{3}+\ldots \end{align*}

¿Qué sucede al sumar las tres expresiones? En el lado derecho, cada vez que m es un múltiplo de 3, tenemos 3\binom{100}{m}, y cada vez que m no es un múltiplo de 3, tenemos

    \[(1+\omega+\omega^2)\binom{100}{m}=0.\]

¡Se filtran exactamente los coeficientes binomiales con parte inferior múltiplo de 3! Así, tres veces la suma que buscamos es igual a

    \[2^{100}+(1+\omega)^{100}+(1+\omega^2)^{100}.\]

Esta ya es una expresión suficientemente cerrada, pero podemos simplificar todavía más:

    \begin{align*}(1+\omega)^{100}&=(-\omega^2)^{100}=\omega^{200}=\omega^2\\(1+\omega^2)^{100}&=(-\omega)^{100}=\omega\\(1+\omega)^{100}+(1+\omega^2)^{100}&=\omega^2+\omega=-1.\end{align*}

Así, la expresión que queremos es \frac{2^{100}-1}{3}.

\square

Más ejemplos

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

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