Relaciones de equivalencia

Proposiciones equivalentes

• $A \equiv B\ (\text{mod }C)$A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
• $A \text{ mod } C = B \text{ mod }C$A, start text, space, m, o, d, space, end text, C, equals, B, start text, space, m, o, d, space, end text, C
• $C \ |\ (A - B)$C, space, vertical bar, space, left parenthesis, A, minus, B, right parenthesis (El símbolo | significa divide o es un factor de)
• $A = B + K \cdot C$A, equals, B, plus, K, dot, C (donde $K$K es algún entero)

• $13 \equiv 23\ (\text{mod }5)$13, \equiv, 23, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis
• $13 \text{ mod } 5 = 23 \text{ mod }5$13, start text, space, m, o, d, space, end text, 5, equals, 23, start text, space, m, o, d, space, end text, 5
• $5 \ |\ (13 - 23)$5, space, vertical bar, space, left parenthesis, 13, minus, 23, right parenthesis, $(5 \ |\ -10$left parenthesis, 5, space, vertical bar, space, minus, 10, lo cual es cierto ya que $\bf{5 \times (-2) = -10} )$5, times, left parenthesis, minus, 2, right parenthesis, equals, minus, 10, right parenthesis
• $13 = 23 + K \cdot 5$13, equals, 23, plus, K, dot, 5. Podemos satisfacer esta expresión con $\bf{K = -2}$K, equals, minus, 2: $13 = 23 + (-2) \times 5$13, equals, 23, plus, left parenthesis, minus, 2, right parenthesis, times, 5

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

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

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

• El pastel: la colección de todos los enteros.
• Una rebanada del pastel etiquetada con $B$B: una clase de equivalencia en donde todos los valores son $\text{mod } C = B$start text, m, o, d, space, end text, C, equals, B.
• Cómo cortamos el pastel en rebanadas: al usar la relación de congruencia módulo C, $\equiv (\text{mod } C)$\equiv, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis.

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

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

• $A \equiv A \ (\text{mod } C)$A, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
• Si $A \equiv B \ (\text{mod }C)$A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, entonces $B \equiv A \ (\text{mod }C)$B, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
• Si $A \equiv \bf{B} \ (\text{mod } C)$A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis y $\bf{B} \equiv D \ (\text{mod } C)$B, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, entonces $\bf{A \equiv D} \ (\text{mod } C)$A, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

Ejemplo

• $3 \equiv 3\ (\text{mod } 5)$3, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (propiedad reflexiva)
• if $3 \equiv 8\ (\text{mod } 5)$3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis then $8 \equiv 3\ (\text{mod }5)$8, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (propiedad simétrica)
• if $3 \equiv 8\ (\text{mod }5)$3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis and if $8 \equiv 18\ (\text{mod }5)$8, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis then $3 \equiv 18\ (\text{mod }5)$3, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (propiedad transitiva)