Conteúdo principal
Curso: Computer science theory > Unidade 2
Lição 5: Aritmética modular- O que é aritmética modular?
- Operador módulo
- Desafio de Módulo
- Módulo de congruência
- Relação de congruência
- Relações equivalentes
- O teorema do resto do quociente
- Adição e subtração modular
- Adição modular
- Desafio de Módulo (Adição e Subtração)
- Multiplicação modular
- Multiplicação modular
- Exponenciação modular
- Exponenciação modular rápida
- Exponenciação Modular Rápida
- Inversas modulares
- O Algoritmo Euclidiano
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
Multiplicação modular
Vamos explorar a propriedade de multiplicação da aritmética modular:
(A * B) mod C = (A mod C * B mod C) mod C
Exemplo de multiplicação:
Seja A=4, B=7, C=6
'Verificamos que: (A * B) mod C = (A mod C * B mod C) mod C
LE= Lado Esquerdo da Equação
LD= Lado Direito da Equação
LE = (A * B) mod C
LE = (4 * 7) mod 6
LE = 28 mod 6
LE = 4
LD = (A mod C * B mod C) mod C
LD = (4 mod 6 * 7 mod 6) mod 6
LD = (4 * 1) mod 6
LD = 4 mod 6
LD = 4
LE = LD = 4
Prova da Multiplicação Modular
Provaremos que (A * B) mod C = (A mod C * B mod C) mod C
Precisamos mostrar que LE = LD
A partir do teorema do resto-quociente podemos escrever A e B, como:
A = C * Q1 + R1 onde 0 ≤ R1 < C e Q1 são números inteiros.A mod C = R1
B = C * Q2 + R2 onde 0 ≤ R2 < C e Q2 são números inteiros. B mod C = R2
LE = (A * B) mod C
LE = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C
LE = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C
LE = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C
Podemos eliminar os múltiplos de C quando obtemos o mod C
LHS = (R1 * R2) mod C
Na próxima vamos fazer a RHS
LD = (A mod C * B mod C) mod C
RHS = (R1 * R2 ) mod C
Assim RHS = LHS
LHS = RHS = (R1 * R2 ) mod C
Quer participar da conversa?
Nenhuma postagem por enquanto.