Proposiciones equivalentes

Antes de continuar, es importante recordar que las siguientes proposiciones son equivalentes:
  • AB (mod C) A \equiv B\ (\text{mod }C)
  • A, space, m, o, d, space, C, equals, B, space, m, o, d, space, C
  • C, space, vertical bar, space, left parenthesis, A, minus, B, right parenthesis (El símbolo | significa divide o es un factor de)
  • A, equals, B, plus, K, dot, C (donde K es algún entero)
Esto nos permite expresar la misma idea de diferentes formas.
Por ejemplo, las siguientes expresiones son equivalentes:
  • 1323 (mod 5) 13 \equiv 23\ (\text{mod }5)
  • 13 mod 523 mod 5 13 \text{ mod } 5 \equiv 23 \text{ mod }5
  • 5, space, vertical bar, space, left parenthesis, 13, minus, 23, right parenthesis, left parenthesis, 5, space, vertical bar, space, minus, 10, lo cual es cierto porque ya que
  • 13, equals, 23, plus, K, dot, 5. Podemos satisfacer esta expresión con : 13, equals, 23, plus, left parenthesis, minus, 2, right parenthesis, times, 5

La congruencia módulo es una relación de equivalencia

tarta

Convéncete de que las rebanadas utilizadas en el ejemplo anterior tienen las siguientes propiedades:
  • Cada par de valores en una rebanada están relacionados entre sí.
  • Nunca encontraremos un valor en más de una rebanada (las rebanadas son mutuamente disjuntas).
  • Si combináramos todas las rebanadas formaríamos un pastel que contendría todos los valores.
Un pastel cuyas rebanadas tengan estas propiedades tiene una relación de equivalencia.
Una relación de equivalencia define cómo podemos cortar nuestro pastel (cómo hacer una partición de nuestro conjunto de valores) en rebanadas (clases de equivalencia).
En general, las relaciones de equivalencia deben tener estas propiedades:
  • El pastel: una colección de todos los valores que nos interesan.
  • Una rebanada de pastel: una clase de equivalencia.
  • Cómo cortamos el pastel en rebanadas: relación de equivalencia.
Específicamente, para nuestro ejemplo anterior:
  • El pastel: la colección de todos los enteros.
  • Una rebanada del pastel etiquetada con B: una clase de equivalencia en donde todos los valores son m, o, d, space, C, equals, B.
  • Cómo cortamos el pastel en rebanadas: al usar la relación de congruencia módulo C, (mod C) \equiv (\text{mod } C) .
Es por esto que decimos que la congruencia módulo C es una relación de equivalencia. Hace una partición de los enteros en C clases de equivalencia diferentes.

¿Por qué nos importa que la congruencia módulo C sea una relación de equivalencia?

Saber que la congruencia módulo C es una relación de equivalencia nos permite conocer algunas propiedades que debe tener.
Las relaciones de equivalencia son relaciones que tienen las siguientes propiedades:
  • Son reflexivas: A está relacionada con A.
  • Son simétricas: si A está relacionada con B, entonces B está relacionada con A.
  • Son transitivas: si A está relacionada con B y B está relacionada con C, entonces A está relacionada con C.
Dado que la congruencia módulo es una relación de equivalencia para (mod C). Esto significa:
  • AA (mod C) A \equiv A \ (\text{mod } C)
  • Si AB (mod C) A \equiv B \ (\text{mod }C) , entonces BA (mod C) B \equiv A \ (\text{mod }C)
  • Si y , entonces

Ejemplo

mod5
Vamos a aplicar estas propiedades a un ejemplo concreto usando m, o, d, space, 5, colon
  • 33  mod 5 3 \equiv 3\ \text{ mod } 5 (propiedad reflexiva)
  • Si 38 (mod 5) 3 \equiv 8\ (\text{mod }5) , entonces 83 (mod 5) 8 \equiv 3\ (\text{mod }5) (propiedad simétrica)
  • Si 38 (mod 5) 3 \equiv 8\ (\text{mod }5) y si 818 (mod 5) 8 \equiv 18\ (\text{mod }5) , entonces 318  mod 5 3 \equiv 18\ \text{ mod }5 (propiedad transitiva)