Índice Superior

Arquivos de Impressão: Tamanho A4 (pdf), Tamanho A5 (pdf), Texto (txt).

Sumário

1  Congruências I

     Definição 1. Dizemos que os inteiros  a  e  b  são congrentes módulo  m  se eles deixam o mesmo resto quando divididos por  m. Denotaremos isso por  a ≡ b (mod m).

     Por exemplo,  7 ≡ 2 (mod 5),  9 ≡ 3 (mod 6),  37 ≡ 7 (mod 10)  mas  5 ≠ 3 (mod 4). Veja que  a ≡ b (mod m)  se, e somente se,  m | a − b.

     Teorema 2. Se  a ≡ b (mod m)  e  c ≡ d (mod m), então:

     i)  a + c ≡ b + d (mod m)

     ii)  a − c ≡ b − d (mod m)

     iii)  ka ≡ kb (mod m) ∀k ∈ Z

     iv)  ac ≡ bd (mod m)

     v)  a^k ≡ b^k (mod m) ∀k ∈ N

     vi) Se  mdc(k, m) = d, então  ka ≡ kb (mod m) ⇔ a ≡ b (mod m/d)

     Demonstração. Sejam  q₁  e  q₂  tais que:

     Então,  (a + c) − (b + d) = (q₁ + q₂)m. Logo,  a + c  e  b + d  deixam o mesmo resto por  m  e consequentemente  a + c ≡ b + d (mod m). Usando que  a − b (mod a)^k − b^k  e que  m | a − b, concluímos que  m (mod a)^k − b^k. Os demais itens serão deixados para o leitor.

     Em termos práticos, podemos realizar quase todas as operações elementares envolvendo igualdade de inteiros. Uma das diferenças cruciais é a operação de divisão como mostra o último item do teorema anterior.

     Exemplo 3. Calcule o resto de  4¹⁰⁰  por 3.

     Como  4 ≡ 1 (mod 3), temos  4¹⁰⁰ ≡ 1¹⁰⁰ = 1 (mod 3).

     Exemplo 4. Calcule o resto de  4¹⁰⁰  por 5.

     Como  4 ≡ −1 (mod 5), temos  4¹⁰⁰ ≡ (−1)¹⁰⁰ = 1 (mod 5).

     Exemplo 5. Calcule o resto de  4¹⁰⁰  por 7.

     Você deve ter percebido que encontrar relações do tipo  a ≡ ± 1 (mod m)  podem simplificar bastante o cálculo de  a^k (mod m). Procuremos alguma relação como essa para 4 e 7. Veja que:

     Assim,

     Como  4³ ≡ 1 (mod 7), os restos das potências de 4 na divisão por 7 se repetem periodicamente de 3 em 3 pois  4^3k+r ≡ 4^3k ·4^r ≡ 4^r (mod 7).

     Exemplo 6. Qual o resto de  36³⁶ + 41⁴¹  na divisão por 77?

     Inicialmente devemos perceber que existe uma relação entre os números do problema:  36 + 41 = 77. Assim:

     Nosso próximo passo é encontrar o resto de  36⁵  na divisão por 77. Como  36 ≡ 1 (mod 7),  36⁵ ≡ 1 (mod 7). Além disso,  36 ≡ 3 (mod 11)  produzindo  36⁵ ≡ 3⁵ ≡ 1 (mod 11). Como  mdc(7, 11) = 1  e ambos dividem  36⁵ − 1, podemos concluir que  77 | 36⁵ − 1. Logo,  36³⁶ + 41⁴¹  deixa resto 0 na divisão por 77.

     Exemplo 7. Prove que  p² − 1  é divisível por 24 se  p  é um primo maior que 3.

     Se  p  é um primo maior que 3,  p ≡ ± 1 (mod 3)  e  p ≡ 1 (mod 2). Daí,  p² ≡ 1 (mod 3). Além disso, se  p = 2k + 1, segue que  p² = 4k (k + 1) + 1 ≡ 1 (mod 8)  pois  k(k + 1)  é par. Como  mdc(8, 3) = 1  e ambos dividem  p² − 1, segue que  24 | p² − 1.

     Exemplo 8. (OCM-2001) Achar o menor natural  n  tal que 2001 é a soma dos quadrados de  n  inteiros

     Podemos concluir da solução do problema anterior que todo todo inteiro ímpar ao quadrado deixa resto 1 por 8. Usemos isso para estimar o valor de  n. Sejam  x₁,  x₂, ... ,  x_n  inteiros ímpares tais que:

     Analisando a congruência módulo 8, obtemos:

     Como 2001 não é quadrado perfeito, não podemos ter  n = 1. O próximo candidado para  n  seria  1 + 8 = 9. Se exibirmos um exemplo para  n = 9, teremos achado o valor mínimo. Veja que:

     Exemplo 9. (IMO) Seja  s(n)  a soma dos dígitos de  n. Se  N = 4444⁴⁴⁴⁴,  A = s(N)  e  B = s(A). Quanto vale  s(B)?

     Pelo critério de divisibilidade por 9,  N ≡ A ≡ B (mod 9). Inicialmente calculemos o resto de  N  por 9. Como  4444 ≡ 16 ≡ 7 (mod 9), precisamos encontrar  7⁴⁴⁴⁴ (mod 9). Seguindo os métodos dos primeiros exemplos, seria interessante encontrarmos um inteiro  r  tal que  7^r ≡ ± 1 (mod 9). O menor inteiro positivo com essa propriedade é  r = 3. Como  4444 = 1481 ·3 + 1, temos:

     Nosso próximo passo é estimar o valor de  s(B). Como  N = 4444⁴⁴⁴⁴ < 10^{5 ·4444},  A = s(N) ≤ 5 ·4444 ·9 = 199980. Além disso,  B = s(A) ≤ 1 + 9 ·5 = 46  e  s(B) ≤ 12. O único inteiro menor ou igual a 12 com resto 7 por 9 é o próprio 7, daí  s(B) = 7.

     Exemplo 10. Prove que  11^{n + 2} + 12^{2n + 1}  é divisível por 133 para qualquer natural  n.

     Duas relações que podemos extrair dos números envolvidos são:  144 − 11 = 133  e  133 − 12 = 121. Assim:

     Exemplo 11. Prove que  n⁵ + 4n  é divisível por 5 para todo inteiro  n

     Inicialmente note que  n⁵ + 4n = n(n⁴ + 4). Se  n ≡ 0 (mod 5), não há o que fazer. Se  n ≡ ± 1 (mod 5),  n⁴ + 4 ≡ 1 + 4 = 0 (mod 5). Finalmente, se  n ≡ ± 2 (mod 5),  n² ≡ 4 ≡ − 1 (mod 5)  e consequentemente  n⁴ + 4 ≡ 1 + 4 = 0 (mod 5).

     Exemplo 12. Seja  n > 6  um inteiro positivo tal que  n − 1  e  n + 1  são primos. Mostre que  n²(n² + 16)  é divisível por 720. A recíproca é verdadeira?

     Veja que  n  é da forma  6k, pois  n − 1  e  n + 1  são primos maiores que 3, portanto da forma  6k − 1  e  6k + 1, respectivamente. Logo,

     Resta provar que  9k⁴ + 4k²  é um múltiplo de 5. Vamos analisar a igualdade acima módulo 5.

     i) Se  k ≡ 0, 2 ou 3 (mod 5), temos  9k⁴ + 4k² ≡ 0 (mod 5);

     ii) Se  k ≡ 1 (mod 5) ⇒ n ≡ 1 (mod 5), temos  n − 1 ≡ 0 (mod 5), um absurdo;

     iii) Se  k ≡ 4 (mod 5) ⇒ n ≡ 4 (mod 5), temos  n + 1 ≡ 0 (mod 5), novamente um absurdo.

     Isso conclui a demonstração. A recíproca não é verdadeira. Basta tomar, por exemplo,  n = 90.

1.1  Problemas Propostos

     Problema 13. Determine o resto de  2²⁰ − 1  na divisão por 41.

     Problema 14. Qual o resto de  1²⁰⁰⁰ + 2²⁰⁰⁰ + …+ 2000²⁰⁰⁰  na divisão por 7?

     Problema 15. Qual o resto na divisão de  2⁷⁰ + 3⁷⁰  por 13?

     Problema 16. Qual o resto de  3²⁰⁰  por 100?

     Problema 17. (Estônia 2000) Determine todos os possíveis restos da divisão do quadrado de um número primo como 120 por 120.

     Problema 18. Qual o último dígito de  777⁷⁷⁷?

     Exemplo 19. Prove que  2222⁵⁵⁵⁵ + 5555²²²²  é divisível por 7.

     Problema 20. Prove que o número  n³ + 2n  é divisível por 3 para todo natural  n.

     Problema 21. Prove que  n² + 1  não é divisível por 3 para nenhum  n  inteiro.

     Problema 22. Prove que  n³ + 2  não é divisível por 9 para nenhum  n  inteiro.

     Problema 23. Prove que  p² − q²  é divisível por 24 se  p  e  q  são primos maiores que 3.

     Problema 24. Prove que se  2n + 1  e  3n + 1  são ambos quadrados perfeitos, então  n  é divisível por 40.

     Problema 25. Se  n  é ímpar, prove que  7 | 2^{2n + 1} + 3^{n + 2}.

     Problema 26. Seja  d(n)  a soma dos dígitos de  n. Suponha que  n + d(n) + d(d(n)) = 1995. Quais os possíveis restos da divisão de  n  por 9?

     Problema 27. Prove que não existem inteiros positivos  x₁,  x₂, ... ,  x₁₄  tais que:

     Problema 28. Escreva uma única congruência que é equivalente ao par de congruências  x ≡ 1 (mod 4)  e  x ≡ 2 (mod 3).

     Problema 29. Prove que  20¹⁵ − 1  é divisível por  11 ·31 ·61

     Problema 30. (Alemanha 1997) Determine todos os primos  p  para os quais o sistema

tem uma solução nos inteiros  x,  y.

     Problema 31. Mostre que se  n  divide um número de Fibonacci então ele dividirá uma infinidade.

1.2  Dicas e Soluções

     13. Veja que

     Assim, o resto procurado é zero.

     14. Como  i²⁰⁰⁰ ≡ (i + 7k)²⁰⁰⁰ (mod 7), podemos simplificar o problema calculando primeiramente o valor de:

     Outra observação importante que simplificará o cálculo é perceber que  2³ ≡ 1 (mod 7). Assim,

     Usando isso e o fato de que 2000 é par, temos:

     Dentre os primeiros 2000 naturais consecutivos, podemos formar 285 grupos de 7 números consecutivos cuja soma é múltipla de 7, em virtude da soma anterior. Os cinco números restantes possuem como resto na divisão por 7 o número:

     Assim, o resto da soma na divisão por 7 é 6.

     15. Inicialmente é interessante buscarmos alguma relação entre os números envolvidos no problema. Como  13 = 4 + 9, podemos escrever:

     17. Use a fatoração  120 = 3 ·5 ·2³  e analise a congruência módulo 3, 5 e 8 separadamente.

     18. Se  n  não é múltiplo de 3, sabemos que  n² ≡ 1 (mod 3). Assim  n² + 2 ≡ 0 (mod 3). Se  n  é múltiplo de 3,  n ≡ 0 (mod 3). Em qualquer caso,  n(n² + 2) ≡ 0 (mod 3).

     19. Basta repetir a análise do problema anterior

     20. Podemos montar uma tabela de congruências na divisão por 9:

     Como nenhum cubo perfeito diexa resto 7 na divisão por 9,  n³ + 2 ≠ 0 (mod 9).

     23. Proceda como no exemplo 7.

     25.

     26. Seja  r  o resto na divisão por 9 de  n. Pelo critério de divisibilidade por 9, temos:

     Assim,  r ≡ 2 (mod 3)  (Pela propriedade vi do teorema 2). Além disso,

     Consequentemente,  n ≥ 1995 − d(n) − d(d(n)) ≥ 1958. Basta procurarmos nos conjunto {1958, 1959, ... , 1995} os inteiros que deixam resto 2 por 3 e que satisfazem a equação do problema. Nesse conjunto, apena o inteiro 1967 cumpre essas condições.

     27. Estudando a congruência módulo 16, podemos mostrar que  x⁴ ≡ 0  ou  1 (mod 16). Assim, a soma

é congruente a um dos números do conjunto {0, 1, ... , 14} módulo 16 enquanto que  1599 ≡ 15 (mod 16). Um absurdo.

     28.  x ≡ 5 (mod 12).

     30. Suponha sem perda de generalidade que  x,  y ≥ 0. Como  p + 1  é par,  p ≠ 2. Além disso,

e consequentente, usando que  p  é ímpar,  x ≡ ± y (mod p). Como  x < y < p, temos

de modo que  p = 4x − 1,  2x² = 4x. Podemos concluir que  x  é 0 ou 2 e que a única possibilidade para  p  é  p = 7.

     31. Em virtude da fórmula recursiva da sequência de Fibonacci, é possível mostrarmos que os restos de seus termos na divisão por qualquer número formam uma sequência periódica.

1.3  Referências

Referências Bibliográficas

[1]

E. Carneiro, O. Campos and F. Paiva, Olimpíadas Cearenses de Matemática 1981-2005 (Níveis Júnior e Senior), Ed. Realce, 2005.

[2]

S. B. Feitosa, B. Holanda, Y. Lima and C. T. Magalhães, Treinamento Cone Sul 2008. Fortaleza, Ed. Realce, 2010.

[3]

D. Fomin, A. Kirichenko, Leningrad Mathematical Olympiads 1987-1991, MathPro Press, Westford, MA, 1994.

[4]

D. Fomin, S. Genkin and I. Itenberg, Mathematical Circles, Mathematical Words, Vol. 7, American Mathematical Society, Boston, MA, 1966.

[5]

I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers.