If you're seeing this message, it means we're having trouble loading external resources on our website.

Si estás detrás de un filtro de páginas web, por favor asegúrate de que los dominios *.kastatic.org y *.kasandbox.org estén desbloqueados.

Contenido principal

Curso: Ciencias de la computación > Unidad 2

Lección 5: Aritmética modular
Computación
Ciencias de la computación
Criptografía
Aritmética modular
© 2024 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies

Relaciones de equivalencia

Google Classroom

Proposiciones equivalentes

Antes de continuar, es importante recordar que las siguientes proposiciones son equivalentes:
  • A≡B (mod C)
  • A mod C=B mod C
  • C | (A−B) (El símbolo | significa divide o es un factor de)
  • A=B+K⋅C (donde K es algún entero)
Esto nos permite expresar la misma idea de diferentes formas.
Por ejemplo, las siguientes expresiones son equivalentes:
  • 13≡23 (mod 5)
  • 13 mod 5=23 mod 5
  • 5 | (13−23), (5 | −10, lo cual es cierto ya que 5×(−2)=−10)
  • 13=23+K⋅5. Podemos satisfacer esta expresión con K=−2: 13=23+(−2)×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 mod C=B.
  • Cómo cortamos el pastel en rebanadas: al usar la relación de congruencia módulo C, ≡(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:
  • A≡A (mod C)
  • Si A≡B (mod C), entonces B≡A (mod C)
  • Si A≡B (mod C) y B≡D (mod C), entonces A≡D (mod C)

Ejemplo

mod5
Vamos a aplicar estas propiedades a un ejemplo concreto usando mod 5:
  • 3≡3 (mod 5) (propiedad reflexiva)
  • if 3≡8 (mod 5) then 8≡3 (mod 5) (propiedad simétrica)
  • if 3≡8 (mod 5) and if 8≡18 (mod 5) then 3≡18 (mod 5) (propiedad transitiva)

¿Quieres unirte a la conversación?

Inicia sesión
¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.