Congruencias · Definición

Sistema completo de residuos

teoría de números elementalcongruencias

Antes de empezar necesitas conocer

Los residuos son la herramienta para contar clases de congruencia sin repetir ni omitir ninguna. Aparecen en demostraciones sobre potencias, funciones aritméticas y primalidad.

Definición

Un sistema completo de residuos módulo \(m\) es un conjunto de \(m\) enteros que contiene exactamente un representante de cada clase de congruencia módulo \(m\).

\[\{r_1,\dots,r_m\}\ \text{con}\ r_i\not\equiv r_j\ (\bmod\ m)\ \forall i\neq j\]

Si \(\{r_1,\dots,r_m\}\) es un sistema completo de residuos módulo \(m\), entonces cualquier entero es congruente módulo \(m\) con exactamente uno de los \(r_i\). Además, si \(\gcd(a,m)=1\), la imagen \(\{ar_1,\dots,ar_m\}\) también es un sistema completo, porque la multiplicación por \(a\) permuta las clases. Por ejemplo, \(\{0,1,2,3\}\) es completo módulo \(4\), y \(\{0,5,6,3\}\) también lo es, pues \(5\equiv1\), \(6\equiv2\) y \(3\equiv3\) (mód 4).

Para demostrar que \(\{0,5,6,3\}\) es completo módulo \(4\), basta comprobar que sus cuatro elementos dan residuos distintos al dividir entre \(4\): \(0,1,2,3\). Como son cuatro residuos distintos y hay exactamente cuatro clases, el conjunto es completo. Este argumento de conteo evita verificar todas las congruencias por pares.

Un error típico es pensar que cualquier conjunto de \(m\) enteros es un sistema completo. Por ejemplo, \(\{0,1,5,9\}\) tiene cuatro elementos, pero \(1,5\) y \(9\) son todos congruentes a \(1\) módulo \(4\), así que no es completo. Hay que comprobar que las clases sean todas distintas.

Para pensar

¿Qué debes comprobar para afirmar que un conjunto de \(m\) enteros es completo módulo \(m\)?

Que sus elementos den restos distintos al dividir entre \(m\), es decir, que cada clase aparezca exactamente una vez.

Ejercicios 10

  1. ¿Cuántos elementos debe tener un sistema completo de residuos módulo \(7\)?
  2. ¿Cuál de estos conjuntos es un sistema completo de residuos módulo \(5\)?
  3. ¿Cuántas clases de congruencia hay módulo \(9\)?
  4. Si \(\{0,1,2,3\}\) es completo módulo \(4\), ¿cuál es el resto de \(7\) al dividir entre \(4\)?
  5. ¿Cuál de estos enteros pertenece a la clase de \(2\) módulo \(6\)?
  6. Determina si \(\{0,1,7,3,4,5,6\}\) es un sistema completo de residuos módulo \(7\) y explica por qué.
  7. Si \(\{1,2,3,4,5,6\}\) es completo módulo \(6\), ¿cuál de estos conjuntos también es completo módulo \(6\)?
  8. Sea \(m=8\) y considera \(\{1,3,5,7\}\) como conjunto de residuos. ¿Cuántos enteros faltan para completar un sistema completo?
  9. Demuestra que si \(\gcd(a,7)=1\) y \(\{r_1,\dots,r_7\}\) es completo módulo \(7\), entonces \(\{ar_1,\dots,ar_7\}\) también lo es. Indica la idea clave.
  10. Sea \(m=6\). ¿Cuál es el resultado de multiplicar el sistema \(\{0,1,2,3,4,5\}\) por \(a=5\) y reducir módulo \(6\)?

Después de esto

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 4
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2