Utilizando o Algoritmo da Divisão:
O que podemos mostrar em relação ao produto de dois inteiros?

Passo 1

Vamos usar o Algoritmo da Divisão para dois inteiros quaisquer a e b ao fixar um divisor positivo n. O conteúdo aqui é teoria dos números elementar: divisão com resto e congruências módulo n. Nosso objetivo é relacionar o resto da divisão de ab pelo n com os restos de a e b pela mesma divisão.

Passo 2

Pelo Algoritmo da Divisão, existem inteiros q_{1},r_{1} tais que
a = n\,q_{1} + r_{1},
com 0 \le r_{1} < n, e existem inteiros q_{2},r_{2} tais que
b = n\,q_{2} + r_{2},
com 0 \le r_{2} < n.

Passo 3

Multiplicando as duas expressões:
ab = (n q_{1} + r_{1})\,(n q_{2} + r_{2}) = n\bigl(n q_{1}q_{2} + q_{1}r_{2} + q_{2}r_{1}\bigr) + r_{1}r_{2}.

Passo 4

Agora aplicamos novamente o Algoritmo da Divisão ao produto r_{1}r_{2}. Existem inteiros s e r tais que
r_{1}r_{2} = n\,s + r,
com 0 \le r < n. Substituindo em ab obtemos
ab = n\bigl(n q_{1}q_{2} + q_{1}r_{2} + q_{2}r_{1} + s\bigr) + r.
Isso mostra que, ao dividir ab por n, o resto é exatamente r.

Passo 5

Repare que r satisfaz
r \equiv r_{1}r_{2}\pmod{n},
pois r = r_{1}r_{2} - n\,s. Como r_{1}\equiv a\pmod{n} e r_{2}\equiv b\pmod{n}, concluímos também
ab \equiv r_{1}r_{2}\equiv a\,b\pmod{n}.

Resposta

Podemos mostrar que, se r_{1} é o resto de a na divisão por n e r_{2} é o resto de b na divisão por n, então o resto de ab na divisão por n é o resto de r_{1}r_{2}. Em termos de congruências,
ab \equiv r_{1}r_{2}\pmod{n}.

Exercícios relacionados