Neste texto o leitor vai encontrar uma série de exercícios de diversos níveis sobre aritmética modular, ou que usam técnicas dela para serem resolvidos.
Caso queira um texto para ser introduzido ao assunto pode conferir o seguinte:
Congruência: Introdução a Aritmética Modular
Assim, o que teremos a seguir pode ser visto como um banco de exercícios para treinar os conhecimentos aprendidos. Antes dos exercícios vamos resolver juntos alguns exemplos.
Exemplos
Exemplo 1. Qual o resto de 121·122·123+1 na divisão por 4?
Colocando em congruência esse exemplo fica bem simples, pois 121 deixa resto 1 na divisão por 4, 122 deixa resto 2 na divisão por 4, e 123 deixa deixa resto 3 na divisão por 4. Logo:
121·122·123+1 ≡ 1·2·3+1 (mod 4)
121·122·123+1 ≡ 6+1 ≡ 7 ≡ 3 (mod 4)
Portanto, deixe o resto igual a 3.
Exemplo 2. Sendo n um número inteiro ímpar, qual o resto de n² por 8?
Nessa questão vamos usar também a ideia de paridade.
Primeiro, se n é ímpar então tem a forma n=2k+1, onde k é um número inteiro.
Logo n² = (2k+1)² = 4k²+4k+1
Veja que k pode ser par ou ímpar.
Se k for par, então k=2q, e
n² = 4k²+4k+1 = 4(2q)²+4(2q)+1 = 16q²+8q+1 = 8(2q²+q)+1, logo deixa resto 1 na divisão por 8.
Se k for ímpar, então k=2q+1, e
Assim n² = 4k²+4k+1 = 4(2q+1)²+4(2q+1)+1 = 16q²+16q+4+8q+4+1 = 8(2q²+3q+1)+1, logo deixa resto 1 na divisão por 8.
Portanto, sendo n ímpar, n² deixa resto 1 na divisão por 8.
Exercícios de aritmética modular
Agora é sua vez de tentar resolver os exercícios.
Exercício 1. Se n não é divisível por 3, qual o resto de 7n⁴+1 por 3?
Exercício 2. Quais números divididos por 17 deixam o resto igual ao quadrado do quociente?
Exercício 3. Qual o resto de 46³·2 na divisão por 3?
Exercício 4. Qual o resto de 444³³³ por 7?
Exercício 5. Qual o resto de 1²⁰⁰⁰ + 2²⁰⁰⁰ + . . . + 2000²⁰⁰⁰ na divisão por 7?
Exercício 6. Prove que n²+1 não é divisível por 3 para nenhum n inteiro.
