(a) Demonstre que se
e
são inteiros não nulos tais que
, com
, então o resto de dividir
por
é igual ao resto de dividir
por
.
(b) Calcule o resto de dividir
por 3 , sem usar congruências.
(b) Calcule o resto de dividir
Passo 1
Enunciado e dados relevantes (o que o problema pede e o que nos dão).
(a) Dado que
e
são inteiros não nulos e que existem inteiros
e
tais que
com
. O pedido é: demonstrar que o resto da divisão de
por
é igual ao resto da divisão de
por
.
(b) Calcular o resto da divisão de
por
, e o enunciado pede explicitamente que não usemos congruências; portanto devemos usar apenas a ideia de divisão com resto e as propriedades algébricas elementares que permitem reduzir restos.
Passo 2
Definição de resto e propriedade básica que vamos usar (aula curta e intuitiva).
Quando dividimos um inteiro
por um inteiro positivo
temos a identidade da divisão:
onde
é um inteiro (o quociente) e
é o resto, com
. A ideia-chave que vamos usar é: se dois inteiros
e
são escritos como
então podemos escrever o produto
e a soma
como um múltiplo de
mais algo que depende só dos restos
. Vou demonstrar isso porque é a base do argumento.
Passo 3
Mostro explicitamente as fórmulas de soma e produto em termos dos restos (isso é mecânica algébrica).
Partindo de
temos para a soma
Isso mostra que o resto de
ao dividir por
é o mesmo que o resto de
ao dividir por
(pois
é múltiplo de
) — depois pode ser necessário reduzir
se ele for maior ou igual a
.
Para o produto:
Isso mostra que o resto da divisão de
por
é igual ao resto da divisão de
por
. Essa propriedade é exatamente o que vamos usar para potências (produto repetido).
Passo 4
Aplicação direta ao caso (a): provar que resto de
por
é o mesmo que resto de
por
.
Começamos da hipótese
com
. Elevando ao quadrado:
Agrupando os termos múltiplos de
:
Da identidade acima vemos que
é um múltiplo de
mais
. Pela definição de resto, isso significa que o resto de dividir
por
é exatamente o mesmo que o resto de dividir
por
— porque a parte que difere é um múltiplo de
. Observação: pode acontecer de
; nesse caso o resto de
ao dividir por
é um número entre
e
, e é precisamente o resto pedido. Isso completa a demonstração do item (a).
Passo 5
Exemplo rápido para fixar a intuição (opcional, mas ajuda a ver que não é só formalismo).
Por exemplo, se
,
então
e
porque
. Então
e
. Dividindo
por
obtemos resto
; dividindo
por
obtemos resto
. É o mesmo resto, como a demonstração garante.
Passo 6
Agora resolvemos (b) passo a passo, aplicando a propriedade do item (a) repetidamente, sem usar linguagem de congruências.
Queremos o resto de
ao dividir por
. Vou analisar cada termo separadamente, usando divisão com resto por
e a propriedade: o resto da potência é o mesmo que o resto da potência do resto da base.
Primeiro termo,
. Dividindo
por
temos
ou seja, o resto de
por
é
. Pelo raciocínio do Passo 3, qualquer potência de
será da forma
. Portanto o resto de
por
é
.
Segundo termo,
. Dividindo
por
temos
ou seja, o resto de
por
é
. Pela propriedade do produto, o resto de
por
é o mesmo que o resto de
por
. Como
, o resto é
.
Terceiro termo,
. Dividindo
por
temos
ou seja, o resto de
por
é
. Podemos reduzir potências usando a propriedade:
Mas dividindo
por
já vimos que o resto é
. Logo o resto de
por
é
. Então
terá o mesmo resto que
, e assim por diante; portanto
terá resto
. (Resumo: resto de
por
é
.)
Quarto termo,
. Dividindo
por
obtemos
portanto o resto de
por
é
. Subtrair
é subtrair resto
(novamente, depois ajustamos se necessário para ficar entre
e
).
Passo 7
Somamos os restos dos termos e reduzimos para obter o resto final.
Reunindo os restos que encontramos:
- resto de
por é , - resto de
por é , - resto de
por é , - resto de
por é (e subtraímos esse ).
Somando esses restos conforme a expressão:
O resultado
já está entre
e
, portanto é o resto final da divisão de toda a expressão por
.
Resposta
(a) O resto da divisão de
por
é igual ao resto da divisão de
por
.
(b)
(b)