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
Adição e subtração modular
Vamos explorar a propriedade da adição da aritmética modular:
(A + B) mod C = (A mod C + B mod C) mod C
Exemplo:
Sendo A = 14, B = 17, C = 5
Vamos verificar: (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 = lado esquerdo da equação
LD = lado direito da equação
LE = (A + B) mod C
LE = (14 + 17) mod 5
LE = 31 mod 5
LE = 1
LE = (14 + 17) mod 5
LE = 31 mod 5
LE = 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
LE = LD = 1
A Intuição por trás da Adição Modular
Observe a figura abaixo. Se queremos calcular 12 + 9 mod 7, podemos facilmente utilizar o círculo modular para uma sequência de 12 + 9 passos para a direita (como mostrado no círculo inferior esquerdo).
Podemos pegar um atalho observando que em todos os 7 passos terminamos na mesma posição no círculo modular. Estas voltas completas em torno do modular do círculo não contribuem para a nossa posição final. Podemos ignorar essas voltas completas ao redor do círculo calculando cada número de mod 7 (como mostrado nos dois círculos modulares superiores). Isto nos dará o número de passos em sentido horário, em relação a 0, o que contribuem para cada uma das suas posições finais ao redor do círculo modular.
Agora, só temos de ir ao redor do círculo no sentido horário o total do número de etapas que contribui para cada posição final dos números (como mostrado no círculo modular inferior direito). Este método aplica-se, em geral, para quaisquer dois números inteiros e qualquer círculo modular.
Prova da Adição Modular
Provaremos que (A + B) mod C = (A mod C + B mod C) mod C
Temos que mostrar que LE = LD
Temos que 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 é um número inteiro. A mod C = R1
B = C * Q2 + R2 onde 0 ≤ R2 < C e Q2 é um número inteiro. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2
B = C * Q2 + R2 onde 0 ≤ R2 < C e Q2 é um número inteiro. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2
LE = (A + B) mod C
LE = (C * (Q1 + Q2) + R1 + R2) mod C
podemos eliminar os múltiplos de C quando obtemos o mod C
LE = (R1 + R2) mod C
LE = (C * (Q1 + Q2) + R1 + R2) mod C
podemos eliminar os múltiplos de C quando obtemos o mod C
LE = (R1 + R2) mod C
LD = (A mod C + B mod C) mod C
LD = (R1 + R2) mod C
LD = (R1 + R2) mod C
LE = LD = (R1 + R2) mod C
Subtração Modular
Uma prova muito semelhante aplica-se para a subtração modular
(A - B) mod C = (A mod C - B mod C) mod C
Quer participar da conversa?
- vivendo ou apenas sobrevivendo?(1 voto)
- Viver é a coisa mais rara do mundo.
A maioria das pessoas apenas existe.
- Oscar Wilde(2 votos)