Mostre que o resto da divisão por 3 do produto de dois números naturais quaisquer é igual ao resto da divisão por 3 do produto de seus respectivos restos.
Passo 1
O enunciado pede para mostrar que, dados dois números naturais quaisquer, o resto da divisão de seu produto por 3 coincide com o resto da divisão por 3 do produto dos restos desses números. O conteúdo envolvido é o algoritmo da divisão com resto e a propriedade de congruências (aritmética modular). Vamos usar o Teorema da Divisão para expressar cada número em termos de um quociente vezes 3 mais um resto.
Passo 2
Pelo Teorema da Divisão, existem inteiros q₁, q₂ e restos r₁, r₂ com 0 ≤ r₁, r₂ < 3 tais que
Aqui r₁ = a mod 3 e r₂ = b mod 3.
Passo 3
Agora multiplicamos a e b usando essas expressões:
Repare que os dois primeiros termos são múltiplos de 3.
Passo 4
Como 9q₁q₂ + 3(q₁r₂ + q₂r₁) é divisível por 3, podemos escrever
para algum inteiro K. Isso mostra que o resto de ab na divisão por 3 é exatamente o resto de r₁r₂.
Passo 5
Por fim, como r₁ = a mod 3 e r₂ = b mod 3, concluímos que o resto da divisão de ab por 3 é igual ao resto da divisão de (a mod 3)·(b mod 3) por 3. Ou seja,
Resposta
Concluímos que (ab) mod 3 = ((a mod 3)·(b mod 3)) mod 3.