Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 2
Lección 5: Aritmética modular- ¿Qué es la aritmética modular?
- Operador módulo
- Desafío de módulo
- Congruencia módulo
- Relación de congruencia
- Relaciones de equivalencia
- El teorema del cociente y del residuo
- Suma y resta modular
- Suma modular
- Desafío de módulo (suma y resta)
- Multiplicación modular
- Multiplicación modular
- Exponenciación modular
- Exponenciación modular rápida
- Exponenciación modular rápida
- Inversos modulares
- El algoritmo de Euclides
© 2023 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
Suma y resta modular
Exploremos la propiedad de la suma de la aritmética modular:
(A + B) mod C = (A mod C + B mod C) mod C
Ejemplo:
Sean A=14, B=17, C=5.
Verifiquemos que: (A + B) mod C = (A mod C + B mod C) mod C
LI = lado izquierdo de la ecuación.
LD = lado derecho de la ecuación.
LI = lado izquierdo de la ecuación.
LD = lado derecho de la ecuación.
LI = (A + B) mod C
LI = (14 + 17) mod 5
LI = 31 mod 5
LI = 1
LI = (14 + 17) mod 5
LI = 31 mod 5
LI = 1
LD = (A mod C + B mod C) mod C
LD = (14 mod 5 + 17 mod 5) mod 5
LD = (4 + 2) mod 5
LD = 1
LD = (14 mod 5 + 17 mod 5) mod 5
LD = (4 + 2) mod 5
LD = 1
LI = LD = 1
Intuición detrás de la suma modular
Observa la siguiente figura. Si queremos calcular 12+9 mod 7, podemos fácilmente ir alrededor del círculo modular por una secuencia de 12+9 pasos en sentido de las manecillas del reloj (como se muestra en el círculo inferior izquierdo).
Podemos tomar un atajo si observamos que cada 7 pasos terminamos en la misma posición en el círculo modular. Estas vueltas completas alrededor del círculo modular no contribuyen a nuestra posición final. Podemos ignorar estas vueltas completas alrededor del círculo al calcular cada número mod 7 (como se muestra en los dos círculos modulares superiores). Esto nos dará el número de pasos en sentido de las manecillas del reloj, relativos al 0, que contribuyen a cada una de las posiciones finales alrededor del círculo modular.
Ahora, solo tenemos que ir alrededor del círculo en sentido de las manecillas del reloj el número total de pasos que contribuyen a la posición final de cada número (como se muestra en el círculo modular inferior derecho). Este método aplica, en general, a cualesquiera dos enteros y cualquier círculo modular.
Demostración de la suma modular
Probaremos que (A + B) mod C = (A mod C + B mod C) mod C
Debemos mostrar que LI=LD
Debemos mostrar que LI=LD
A partir del teorema del cociente y del residuo podemos escribir A y B como:
A = C * Q1 + R1 donde 0 ≤ R1 < C y Q1 son enteros. A mod C = R1
B = C * Q2 + R2 donde 0 ≤ R2 < C y Q2 son enteros. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2
B = C * Q2 + R2 donde 0 ≤ R2 < C y Q2 son enteros. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2
LI = (A + B) mod C
LI = (C * (Q1 + Q2) + R1+ R2) mod C
Podemos eliminar los múltiplos de C cuando tomamos mod C.
LI = (R1 + R2) mod C
LI = (C * (Q1 + Q2) + R1+ R2) mod C
Podemos eliminar los múltiplos de C cuando tomamos mod C.
LI = (R1 + R2) mod C
LD = (A mod C + B mod C) mod C
LD = (R1 + R2) mod C
LD = (R1 + R2) mod C
LI=LD= (R1 + R2) mod C
Resta modular
Para la resta modular, se hace una prueba muy parecida:
(A - B) mod C = (A mod C - B mod C) mod C
¿Quieres unirte a la conversación?
Necesito probar que $\left(\sum_{i=1}^{n}{a_i\,\text{m\'od.}\,m}\right)\,\text{m\'od.}\,m=\left(\sum_{i=1}^{n}{a_i}\right)\,\text{m\'od.}\,m$, cómo me recomiendan que proceda?(2 votos)- Por qué se eliminan los múltiplos de C, cuando se toma el módulo C? Hablo de la parte de la demostración.
Si me pueden aclarar por favor.(1 voto)- El módulo es una división de la que nos quedamos con el resto.
Si un número lo multiplicas por otro y lo divides por este mismo nos queda el original:
5*2=10; 10/2=5
(C*(Q1+Q2)+R1+R2)mod C es como si hiciesemos
(C*(Q1+Q2)+R1+R2)/C y nos quedamos el resto, no nos importa el cociente y por lo tanto, siguiendo el uso del círculo modular, no nos importa cuantas vueltas demos.
De esta manera tanto (C*(Q1+Q2)+R1+R2)modC como (R1+R2)modC nos van a dar el mismo resto (módulo).(1 voto)
noooooooooooooooo eeeeeeeeeennnnnnnnnnnnntttttttttttttttttteeeeeeeeeeennnnnnnnnnnnnndddddddddddddiiiiiiiiiiiiiiiiiiiiiiinnnnnnnnnnnaddddddddddaaaaaaaaaaa ddddddddddddddddddddeeeeeeeeee eeeeeeeeeeeeeeeeeeeesssssssssstttttttttttttto(0 votos)- No es tan complicado. Guiate por los dibujos. Quiza debas ver antes la explicacion de modulo.(3 votos)