Utilizando o Algoritmo da Divisão:
O que podemos mostrar em relação ao produto de dois inteiros?
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
e
ao fixar um divisor positivo
. O conteúdo aqui é teoria dos números elementar: divisão com resto e congruências módulo
. Nosso objetivo é relacionar o resto da divisão de
pelo
com os restos de
e
pela mesma divisão.
Passo 2
Pelo Algoritmo da Divisão, existem inteiros
tais que
com
, e existem inteiros
tais que
com
.
Passo 3
Multiplicando as duas expressões:
Passo 4
Agora aplicamos novamente o Algoritmo da Divisão ao produto
. Existem inteiros
e
tais que
com
. Substituindo em
obtemos
Isso mostra que, ao dividir
por
, o resto é exatamente
.
Passo 5
Repare que
satisfaz
pois
. Como
e
, concluímos também
Resposta
Podemos mostrar que, se
é o resto de
na divisão por
e
é o resto de
na divisão por
, então o resto de
na divisão por
é o resto de
. Em termos de congruências,