(a) Demonstre que se a e b são inteiros não nulos tais que a=b q+r, com 0 \leq r<b, então o resto de dividir a^{2} por b é igual ao resto de dividir r^{2} por b.
(b) Calcule o resto de dividir 12^{20}+4^{100}+5^{8}-7 por 3 , sem usar congruências.

Passo 1

Enunciado e dados relevantes (o que o problema pede e o que nos dão).
(a) Dado que a e b são inteiros não nulos e que existem inteiros q e r tais que
a = bq + r
com 0 \le r < b. O pedido é: demonstrar que o resto da divisão de a^{2} por b é igual ao resto da divisão de r^{2} por b.
(b) Calcular o resto da divisão de
12^{20}+4^{100}+5^{8}-7
por 3, 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 x por um inteiro positivo y temos a identidade da divisão:
x = y\cdot k + s
onde k é um inteiro (o quociente) e s é o resto, com 0 \le s < y. A ideia-chave que vamos usar é: se dois inteiros u e v são escritos como
u = y\cdot m + s_u,\qquad v = y\cdot n + s_v,
então podemos escrever o produto uv e a soma u+v como um múltiplo de y mais algo que depende só dos restos s_u,s_v. 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
u = y\cdot m + s_u,\qquad v = y\cdot n + s_v,
temos para a soma
u+v = y(m+n) + (s_u+s_v).
Isso mostra que o resto de u+v ao dividir por y é o mesmo que o resto de s_u+s_v ao dividir por y (pois y(m+n) é múltiplo de y) — depois pode ser necessário reduzir s_u+s_v se ele for maior ou igual a y.
Para o produto:
uv = (y m + s_u)(y n + s_v) = y\big(ymn + m s_v + n s_u\big) + s_u s_v.
Isso mostra que o resto da divisão de uv por y é igual ao resto da divisão de s_u s_v por y. Essa propriedade é exatamente o que vamos usar para potências (produto repetido).

Passo 4

Aplicação direta ao caso (a): provar que resto de a^{2} por b é o mesmo que resto de r^{2} por b.
Começamos da hipótese
a = bq + r
com 0\le r < b. Elevando ao quadrado:
a^{2} = (bq + r)^{2} = b^{2}q^{2} + 2bq r + r^{2}.
Agrupando os termos múltiplos de b:
a^{2} = b\big(b q^{2} + 2 q r\big) + r^{2}.
Da identidade acima vemos que a^{2} é um múltiplo de b mais r^{2}. Pela definição de resto, isso significa que o resto de dividir a^{2} por b é exatamente o mesmo que o resto de dividir r^{2} por b — porque a parte que difere é um múltiplo de b. Observação: pode acontecer de r^{2}\ge b; nesse caso o resto de r^{2} ao dividir por b é um número entre 0 e b-1, 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 a=11, b=4 então q=2 e r=3 porque 11=4\cdot2+3. Então a^{2}=121 e r^{2}=9. Dividindo 121 por 4 obtemos resto 1; dividindo 9 por 4 obtemos resto 1. É 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
12^{20}+4^{100}+5^{8}-7
ao dividir por 3. Vou analisar cada termo separadamente, usando divisão com resto por 3 e a propriedade: o resto da potência é o mesmo que o resto da potência do resto da base.
Primeiro termo, 12^{20}. Dividindo 12 por 3 temos
12 = 3\cdot 4 + 0,
ou seja, o resto de 12 por 3 é 0. Pelo raciocínio do Passo 3, qualquer potência de 12 será da forma 3\cdot(\text{algo}) + 0. Portanto o resto de 12^{20} por 3 é 0.
Segundo termo, 4^{100}. Dividindo 4 por 3 temos
4 = 3\cdot 1 + 1,
ou seja, o resto de 4 por 3 é 1. Pela propriedade do produto, o resto de 4^{100} por 3 é o mesmo que o resto de 1^{100} por 3. Como 1^{100}=1, o resto é 1.
Terceiro termo, 5^{8}. Dividindo 5 por 3 temos
5 = 3\cdot 1 + 2,
ou seja, o resto de 5 por 3 é 2. Podemos reduzir potências usando a propriedade:
5^{2}\\ \text{tem o mesmo resto que}\\\ 2^{2}=4.
Mas dividindo 4 por 3 já vimos que o resto é 1. Logo o resto de 5^{2} por 3 é 1. Então
5^{4} = (5^{2})^{2}
terá o mesmo resto que 1^{2}=1, e assim por diante; portanto 5^{8}=(5^{2})^{4} terá resto 1. (Resumo: resto de 5^{8} por 3 é 1.)
Quarto termo, -7. Dividindo 7 por 3 obtemos
7 = 3\cdot 2 + 1,
portanto o resto de 7 por 3 é 1. Subtrair 7 é subtrair resto 1 (novamente, depois ajustamos se necessário para ficar entre 0 e 2).

Passo 7

Somamos os restos dos termos e reduzimos para obter o resto final.
Reunindo os restos que encontramos:
  • resto de 12^{20} por 3 é 0,
  • resto de 4^{100} por 3 é 1,
  • resto de 5^{8} por 3 é 1,
  • resto de 7 por 3 é 1 (e subtraímos esse 1).
Somando esses restos conforme a expressão:
0 + 1 + 1 - 1 = 1.
O resultado 1 já está entre 0 e 2, portanto é o resto final da divisão de toda a expressão por 3.

Resposta

(a) O resto da divisão de a^{2} por b é igual ao resto da divisão de r^{2} por b.
(b) 1

Exercícios relacionados