Justifica que, quaisquer que sejam os inteiros x, y e z e n >= 1: ((w times x) times y) bmod n=(w times(x times y)) bmod n.

Passo 1

O enunciado pede para mostrarmos que a operação de multiplicação seguida de redução módulo n é compatível com a associatividade da multiplicação em ℤ. O conteúdo aqui é aritmética modular e usamos a associatividade da multiplicação inteira e a propriedade de que restos iguais vêm de números iguais.

Passo 2

Em ℤ, a multiplicação é associativa. Ou seja, para quaisquer inteiros w, x e y vale
(w times x) times y = w times (x times y)

Passo 3

Pela definição de resto da divisão, se dois inteiros A e B são iguais, então seus resíduos módulo n também são iguais. Formalmente, se A = B então
A bmod n = B bmod n

Passo 4

Aplicando essa propriedade ao resultado da associatividade temos
((w times x) times y) bmod n = (w times (x times y)) bmod n, pois o que está antes do “\bmod n” são dois números idênticos.

Passo 5

Assim, concluímos que a multiplicação antes de tomar módulo pode ser feita em qualquer ordem sem alterar o resultado do resto por n.

Resposta

((w × x) × y) mod n = (w × (x × y)) mod n, pois a multiplicação em ℤ é associativa e a operação de tomar módulo preserva igualdade de inteiros.

Exercícios relacionados