Polos Olímpicos de Treinamento Intensivo (POTI) Curso de Teoria dos Números - Nível 2 Aula 5 - Congruências I Prof. Samuel Feitosa "Arquivo Original"{1} ****** Sumário ****** 1 Congruências I 1.1 Problemas Propostos 1.2 Dicas e Soluções 1.3 Referências ***** 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 a b (mod m). Por exemplo, 7 a 2 (mod 5), 9 a 3 (mod 6), 37 a 7 (mod 10) mas 5 não= 3 (mod 4). Veja que a a b (mod m) se, e somente se, m | a - b. Teorema 2. Se a a b (mod m) e c a d (mod m), então: i) a + c a b + d (mod m) ii) a - c a b - d (mod m) iii) ka a kb (mod m) para todo k pertence Z iv) ac a bd (mod m) v) ak a bk (mod m) para todo k pertence N vi) Se mdc(k, m) = d, então ka a kb (mod m) <--> a a b (mod m/d) Demonstração. Sejam q1 e q2 tais que: a - b = q1 m c - d = q2 m Então, (a + c) - (b + d) = (q1 + q2)m. Logo, a + c e b + d deixam o mesmo resto por m e consequentemente a + c a b + d (mod m). Usando que a - b (mod a)k - bk e que m | a - b, concluímos que m (mod a)k - bk. 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^(100) por 3. Como 4 a 1 (mod 3), temos 4^(100) a 1^(100) = 1 (mod 3). Exemplo 4. Calcule o resto de 4^(100) por 5. Como 4 a -1 (mod 5), temos 4^(100) a (-1)^(100) = 1 (mod 5). Exemplo 5. Calcule o resto de 4^(100) por 7. Você deve ter percebido que encontrar relações do tipo a a +ou- 1 (mod m) podem simplificar bastante o cálculo de ak (mod m). Procuremos alguma relação como essa para 4 e 7. Veja que: 4^(0) a 1 (mod 7), 4^(1) a 4 (mod 7), 4^(2) a 2 (mod 7), 4^(3) a 1 (mod 7). Assim, 4^(99) = (4^(3))^(33) a 1^(33) = 1 (mod 7). Como 4^(3) a 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) a 4^(3k) ·4r a 4r (mod 7). Exemplo 6. Qual o resto de 36^(36) + 41^(41) na divisão por 77? Inicialmente devemos perceber que existe uma relação entre os números do problema: 36 + 41 = 77. Assim: -36 a 41 (mod 77), (-36)^(41) a 41^(41) (mod 77), 36^(36)(1 - 36^(5)) a 36^(36) + 41^(41) (mod 77). Nosso próximo passo é encontrar o resto de 36^(5) na divisão por 77. Como 36 a 1 (mod 7), 36^(5) a 1 (mod 7). Além disso, 36 a 3 (mod 11) produzindo 36^(5) a 3^(5) a 1 (mod 11). Como mdc(7, 11) = 1 e ambos dividem 36^(5) - 1, podemos concluir que 77 | 36^(5) - 1. Logo, 36^(36) + 41^(41) deixa resto 0 na divisão por 77. Exemplo 7. Prove que p^(2) - 1 é divisível por 24 se p é um primo maior que 3. Se p é um primo maior que 3, p a +ou- 1 (mod 3) e p a 1 (mod 2). Daí, p^ (2) a 1 (mod 3). Além disso, se p = 2k + 1, segue que p^(2) = 4k (k + 1) + 1 a 1 (mod 8) pois k(k + 1) é par. Como mdc(8, 3) = 1 e ambos dividem p^(2) - 1, segue que 24 | p^(2) - 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 x1, x2, ... , xn inteiros ímpares tais que: x12 + x22 + ... xn2 = 2001. Analisando a congruência módulo 8, obtemos: x12 + x22 + ... xn2 = 2001 (mod 8) 1 + 1 + ... + 1 a 1 (mod 8) n a 1 (mod 8) 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: 2001 = 43^(2) + 11^(2) + 5^(2) + 1^(2) + 1^(2) + 1^(2) + 1^(2) + 1^(2) + 1^(2). Exemplo 9. (IMO) Seja s(n) a soma dos dígitos de n. Se N = 4444^(4444), A = s(N) e B = s(A). Quanto vale s(B)? Pelo critério de divisibilidade por 9, N a A a B (mod 9). Inicialmente calculemos o resto de N por 9. Como 4444 a 16 a 7 (mod 9), precisamos encontrar 7^(4444) (mod 9). Seguindo os métodos dos primeiros exemplos, seria interessante encontrarmos um inteiro r tal que 7r a +ou- 1 (mod 9). O menor inteiro positivo com essa propriedade é r = 3. Como 4444 = 1481 ·3 + 1, temos: 7^(4444) a 7^(1481 ·3 + 1) a (7^(3))^(1481) ·7 a 7 (mod 9). Nosso próximo passo é estimar o valor de s(B). Como N = 4444^(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 11n + 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: 144 a 11 (mod 133), 12^(2) a 11 (mod 133), 12^(2n) a 11n (mod 133), 12^(2n + 1) a 11n ·12 (mod 133), 12^(2n + 1) a 11n ·(-121) + 133 ·11n (mod 133), 12^(2n + 1) a - 11n + 2 (mod 133). Exemplo 11. Prove que n^(5) + 4n é divisível por 5 para todo inteiro n Inicialmente note que n^(5) + 4n = n(n^(4) + 4). Se n a 0 (mod 5), não há o que fazer. Se n a +ou- 1 (mod 5), n^(4) + 4 a 1 + 4 = 0 (mod 5). Finalmente, se n a +ou- 2 (mod 5), n^(2) a 4 a - 1 (mod 5) e consequentemente n^(4) + 4 a 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^(2)(n^(2) + 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, n^(2)(n^(2) + 16) = 144(9k^(4) + 4k^(2)). Resta provar que 9k^(4) + 4k^(2) é um múltiplo de 5. Vamos analisar a igualdade acima módulo 5. i) Se k a 0, 2 ou 3 (mod 5), temos 9k^(4) + 4k^(2) a 0 (mod 5); ii) Se k a 1 (mod 5) -> n a 1 (mod 5), temos n - 1 a 0 (mod 5), um absurdo; iii) Se k a 4 (mod 5) -> n a 4 (mod 5), temos n + 1 a 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^(20) - 1 na divisão por 41. Problema 14. Qual o resto de 1^(2000) + 2^(2000) + ... + 2000^(2000) na divisão por 7? Problema 15. Qual o resto na divisão de 2^(70) + 3^(70) por 13? Problema 16. Qual o resto de 3^(200) 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^(777)? Exemplo 19. Prove que 2222^(5555) + 5555^(2222) é divisível por 7. Problema 20. Prove que o número n^(3) + 2n é divisível por 3 para todo natural n. Problema 21. Prove que n^(2) + 1 não é divisível por 3 para nenhum n inteiro. Problema 22. Prove que n^(3) + 2 não é divisível por 9 para nenhum n inteiro. Problema 23. Prove que p^(2) - q^(2) é 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) + 3n + 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 x1, x2, ... , x14 tais que: x14 + x24 + ... + x144 = 1599. Problema 28. Escreva uma única congruência que é equivalente ao par de congruências x a 1 (mod 4) e x a 2 (mod 3). Problema 29. Prove que 20^(15) - 1 é divisível por 11 ·31 ·61 Problema 30. (Alemanha 1997) Determine todos os primos p para os quais o sistema p + 1 = 2x^(2) p^(2) + 1 = 2y^(2) 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 2^(5) = 32 a -9 (mod 41) -> 2^(10) a 81 a -1 (mod 42) -> 2^(20) a 1 (mod 41). Assim, o resto procurado é zero. 14. Como i^(2000) a (i + 7k)^(2000) (mod 7), podemos simplificar o problema calculando primeiramente o valor de: 1^(2000) + 2^(2000) + 3^(2000) + 4^(2000) + 5^(2000) + 6^(2000) + 7^(2000) (mod 7). Outra observação importante que simplificará o cálculo é perceber que 2^(3) a 1 (mod 7). Assim, 2^(3k) a 1 (mod 7), 2^(3k + 1) a 2 (mod 7), e 2^(3k + 2) a 4 (mod 7). Usando isso e o fato de que 2000 é par, temos: 1^(2000) + 2^(2000) + 3^(2000) + 4^(2000) + 5^(2000) + 6^(2000) + 7^(2000) a 1^(2000) + 2^(2000) + (-4)^(2000) + 4^(2000) + (-2)^(2000) + (-1)^(2000) + 0^(2000) a a 1 + 4 + 2 + 2 + 4 + 1 + 0 a 0 (mod 7). 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: 1996^(2000) + 1997^(2000) + 1998^(2000) + 1999^(2000) + 2000^(2000) a 1 + 4 + 2 + 2 + 4 a 6 (mod 7). 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: 9 a -4 (mod 13) -> 9^(35) a (-4)^(35) (mod 13) -> 3^(70) + 2^(70) a 0 (mod 13). 17. Use a fatoração 120 = 3 ·5 ·2^(3) e analise a congruência módulo 3, 5 e 8 separadamente. 18. Se n não é múltiplo de 3, sabemos que n^(2) a 1 (mod 3). Assim n^(2) + 2 a 0 (mod 3). Se n é múltiplo de 3, n a 0 (mod 3). Em qualquer caso, n(n^ (2) + 2) a 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: n 0 1 2 3 4 5 6 7 8 n^(3) 0 1 8 0 1 8 0 1 8 Como nenhum cubo perfeito diexa resto 7 na divisão por 9, n^(3) + 2 não= 0 (mod 9). 23. Proceda como no exemplo 7. 25. 2^(2n + 1) + 3n + 2 a 4n ·2 + 3n ·9 a (-3)n ·2 + 3n ·2 a 0 (mod 7). 26. Seja r o resto na divisão por 9 de n. Pelo critério de divisibilidade por 9, temos: n + d(n) + d(d(n)) a 3r a 1995 (mod 9). Assim, r a 2 (mod 3) (Pela propriedade vi do teorema 2). Além disso, n <= 1995 -> d(n) <= 27 = d(1989) -> d(d(n)) <= 10 = d(19). 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^(4) a 0 ou 1 (mod 16). Assim, a soma x14 + x24 + ... + x144 é congruente a um dos números do conjunto {0, 1, ... , 14} módulo 16 enquanto que 1599 a 15 (mod 16). Um absurdo. 28. x a 5 (mod 12). 30. Suponha sem perda de generalidade que x, y >= 0. Como p + 1 é par, p não= 2. Além disso, 2x^(2) a 1 a 2y^(2) (mod p) e consequentente, usando que p é ímpar, x a +ou- y (mod p). Como x < y < p, temos p^(2) + 1 = 2(p - x)^(2) = 2p^(2) - 4px + p + 1, de modo que p = 4x - 1, 2x^(2) = 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. =============================================================================== **** Notas de Rodapé: **** {1} Documento: "... gaia/educacional/matematica/pot2tn05/Aula05-CongruenciasI.pdf".