Polos Olímpicos de Treinamento Intensivo (POTI) Curso de Teoria dos Números - Nível 2 Aula 6 - Congruências II Prof. Samuel Feitosa "Arquivo Original"{1} ****** Sumário ****** 1 Congruências II 1.1 Problemas Propostos 1.2 Dicas e Soluções ***** 1 Congruências II ***** Na aula de hoje, aprenderemos um dos teoremas mais importantes do curso: o "pequeno" teorema de Fermat. Começaremos relembrando um resultado da aula passada: Lema 1. Se ka a kb (mod m) e mdc(m, k) = 1, então a a b (mod m). Demonstração. Como m | k(a - b) e mdc(m, k) = 1, segue que m | a - b. Teorema 2. (Teorema de Fermat) Seja p um primo. Se p não divide a então ap - 1 a 1 (mod p). Além disso, para todo inteiro a, ap a a (mod p) Demonstração. Considere o conjunto de inteiros B = {a, 2a, 3a, ... , (p-1)a} onde a é um inteiro satisfazendo mdc(a, p) = 1. Nenhum deles é divisível por p e quaisquer dois deles são incongruentes módulo p, em virtude do lema anterior. Assim, o conjunto dos restos dos elementos de B coincide com o conjunto dos restos não nulos na divisão por p, a saber, {1, 2, 3, ... , p-1}. Portanto, a ·2a ·3a ... (p - 1)a a 1 ·2 ·3 · ... (p - 1) (mod p), ap-1 (p - 1)! a (p - 1)! (mod p). Podemos cancelar o termo (p - 1)! em ambos os lados pois mdc((p - 1)!, p) = 1, concluindo assim a demonstração do teorema. Exemplo 3. Prove que [(n^(5))/5] + [(n^(3))/3] + [7n/15] é um inteiro para todo inteiro n. Primeiramente note que [(n^(5))/5] + [(n^(3))/3] + [7n/15] = [(3n^(5) + 5n^(3) + 7n)/15]. Como mdc(3, 5) = 1, basta mostrarmos que o numerador é mútiplo de 3 e 5. Pelo teorema de Fermat: 3n^(5) + 5n^(3) + 7n a 5n^(3) + 7n a 5n + 7n = 12n a 0 (mod 3), 3n^(5) + 5n^(3) + 7n a 3n^(5) + 7n a 3n + 7n = 10n a 0 (mod 5). Problema 4. Mostre que n^(7) a n (mod 42), para todo n pertence N Pelo teorema de Fermat, n^(7) a n (mod 7) n^(7) a (n^(3))^(2) ·n a n^(2) ·n = n^(3) a n (mod 3) n^(7) a (n^(2))^(3) ·n a n^(3) ·n = (n^(2))^(2) a n^(2) a n (mod 2) Como 2, 3 e 7 são primos entre si, n^(7) a n (mod 2 ·3 ·7 = 42). Exemplo 5. (Bulgária 95) Encontre o número de inteiros n > 1 para os quais o número a^(25) - a é divisível por n para cada inteiro a. Se n satisfaz o enunciado, p^(2) (p primo) não pode dividí-lo, pois p^ (25) - p não é divisível por p^(2). Assim, n é múltiplo de primos diferentes. Os fatores primos de n são fatores de 2^(25) - 2 = 2 ·3^(2) ·5 ·7 ·13 ·17 ·241. Entretanto, n não é divisível por 17 e 241 pois 3^(25) a - 3 (mod 17) e 3^(25) a 32 (mod 241). Seguindo o exemplo anterior, podemos usar o teorema de Fermat para mostrar que a^(25) a a (mod p) para p pertence {2, 3, 5, 7, 13}. Portanto, n deve ser igual a um dos divisores de 2 ·3 ·5 ·7 ·13 diferente de 1. A quantidade de tais divisores é 2^(5) - 1 = 31. Exemplo 6. Prove que para cada primo p, a diferença 111 ... 11222 ... 22333 ... 33 ... 888 ... 88999 ... 99 - 123456789 (onde cada digito está escrito exatamente p vezes) é múltiplo de p. Uma boa maneira de associar os números do problema com o teorema de Fermat é perceber que: 10p - 1 111 ... 11 = ===================================== . ==================================== 9 p uns Assim, podemos escrever o número S = 111 ... 11222 ... 22333 ... 33 ... 888 ... 88999 ... 99 como: 10p - 1 ·10^(8p) + 2 10p - 1 ·10^(7p) + 10p - 1 S = ============ · ============ ... 9 · ============= 9 9 9 9S = (10p - 1) ·10^(8p) + 2 ·(10p - 1) ·10^(7p) + ... 9 ·(10p - 1) Para p = 2 ou p = 3, o resultado do enunciado segue dos critérios de divisibilidade por 2 e 3. Podemos então nos concentrar no caso p > 3. Nesse caso, é suficiente mostrarmos que 9(S - 123456789) é divisível por p pois mdc(p, 9) = 1. Pelo teorema de Fermat: 9S = (10p - 1) ·10^(8p) + 2 ·(10p - 1) ·10^(7p) + ... 9 ·(10p - 1) a (10 - 1) ·10^(8) + 2 ·(10 - 1) ·10^(7) + ... + 9 ·(10 - 1) (mod p) a 9 ·123456789 (mod p). Exemplo 7. Dado um primo p, prove que existem infinitos naturais n tais que p divide 2n - n. Se p = 2, n pode ser qualquer número par. Suponha que p > 2. Considere (p - 1)^(2k), pelo teorema de Fermat temos: 2(p - 1)^(2k) a (2p - 1)(p - 1)^(2k - 1) a 1(p - 1)^(2k - 1) = 1 a (p - 1)^(2k) (mod p). Assim, para qualquer k, n = (p - 1)^(2k) satisfaz o problema. Lema 8. Se mdc(a, m) = 1 então existe um inteiro x tal que ax a 1 (mod m). Tal x é único módulo m. Se mdc(a, m) > 1 então não existe tal x. Demonstração. Pelo teorema de Bachet-Bézout, existem inteiros x e y tais que ax + my = 1. Analisando essa congruência módulo m, obtemos ax a 1 (mod m). Se y é outro inteiro que satisfaz a congruência, temos ax a ay (mod m). Pelo primeiro lema, x a y (mod m). Se d = mdc(a, m) > 1, não podemos ter d | m e m | ax - 1 pois d $ ax - 1. Teorema 9. (Teorema de Wilson) Se p é primo, então (p - 1)! a - 1 (mod p) Demonstração. Em virtude do lema anterior, para cada a pertence {2, 3, ... , p-2}, existe um resto x pertence {0, 1, 2, ... , p - 1} tal que ax a 1 (mod p). Se x = 1 ou x = p - 1, teríamos a = 1 ou p - 1. Além disso, não podemos ter a = x pois os únicos restos que satisfazem a^(2) a 1 (mod p) são 1 e p - 1 (Veja o problema 20). Com isso, podemos agrupar os números de {2, 3, ... , p - 2} em pares onde o produto deixa resto 1 por p, o que nos permite concluir que o produto de todos eles também deixa resto 1 por p. Logo, (p - 1)! a 1 ·(p - 1) a - 1 (mod p). Exemplo 10. (Estônia 2000) Prove que não é possível dividir qualquer conjunto de 18 inteiros consecutivos em dois conjuntos disjuntos A e B tais que o produto dos elementos de A seja igual ao produto dos elementos de B. Suponha, por absurdo, que existam tais conjuntos. Considere o primo p = 19. Como o produto dos elementos de A é igual ao produtos dos elementos de B, se um dos conjuntos contém um múltiplo de 19, o outro necessariamente também conterá. Como entre 18 inteiros consecutivos não existem dois múltiplos de 19, nenhum dos conjuntos do problema contém tais números. Seja x o resto na divisão por 19 do produto dos elementos de A. Calculemos então o resto na divisão por 19 do produto de todos os 18 inteiros consecutivos: x ·x a n(n + 1)(n + 2)(n + 3) ... (n + 17) a 1 ·2 ·3 ... ·18 a - 1 (mod 19) (Pelo teorema de Wilson). Como x^(2) a - 1 (mod 19), x^(18) a (-1)^(9) a 1 (mod 19). Isso contraria o teorema de Fermat e obtemos um absurdo. Definição 11. Um conjunto S é chamado de sistema completo de resíduos módulo n, denotado abreviadamente por scr, se para cada 0 <= i <= n - 1, existe um elemento de s pertence S tal que i a s (mod n). Para qualquer a, o conjunto {a, a + 1, a + 2, ... , a + (n - 1)} é um exemplo de scr. Exemplo 12. Se mdc(m, s) = 1, mostre que {t, t + s, t + 2s, ... , t + (m - 1)s} é um scr. Pelo primeiro lema, se t + is a t + js (mod m), temos is a js (mod m) e i a j (mod m). Como i, j pertence {0, 1, ... , m - 1}, i = j. Isso nos diz que temos m inteiros que deixam restos distintos na divisão por m. Como existem exatamente m restos na divisão por m, o conjunto é um scr. Exemplo 13. Seja m um inteiro positivo par. Suponha que {a1, a2, ... , am} e {b1, b2, ... , bm} são dois sistemas completos de resíduso módulo m. Prove que S = {a1 + b1, a2 + b2, ... , am + bm} não é um sistema completo de resíduos. Suponha que S seja um scr, então: 1 + 2 + ... + m a (a1 + b1) + (a2 + b2)+ ... + (an + bn) (mod m) a (a1 + a2 + ... + an) + (b1 + b2+ ... + bn) a 2 (1 + 2 + ... + n) a 2 (1 + 2 + ... + m) Isso implica que m | [(m(m + 1))/2], ou seja, [(m + 1)/2] é inteiro. Um absurdo pois m é par. Exemplo 14. (Polônia 1997) Prove que a sequência an definida por a1 = 1 e an = an-1 + a\[n/2] / contém infinitos termos divisíveis por 7. Uma maneira natural para mostrarmos que existem infinitos inteiros múltiplos de 7 na sequência é verificar que o aparecimento de um múltiplo de 7 acarreta o aparecimento de outro múltiplo na sequência com um índice maior. Suponha que ak é múltiplo de 7. Seja a2k-1 = s. Então: a2k - 1 = s a2k = s + ak a s (mod 7) a2k + 1 = a2k + ak a s (mod 7) Ou seja, o aparecimento de um inteiro múltiplo de 7 implica no aparecimento de 3 inteiros com o mesmo resto por 7. Exploremos essa ideia mais uma vez. a4k - 3 = t a4k - 2 a t + a2k - 1 a t + s (mod 7) a4k - 1 a t + s + a2k - 1 a t + 2s (mod 7) a4k a t + 2s + a2k a t + 3s (mod 7) a4k + 1 a t + 3s + a2k a t + 4s (mod 7) a4k + 2 a t + 4s + a2k + 1 a t + 5s (mod 7) a4k + 3 a t + 5s + a2k + 2 a t + 6s (mod 7) Se s é múltiplo de 7, já teremos conseguido outro múltiplo de 7 na sequência. Em caso contrário, o conjunto {t, t + s, t + 2s, ... , t + 6s} é um scr e conterá um múltiplo de 7. Exemplo 15. Sejam x, y inteiros. Prove que 3x^(2) + 4y^(2) e 4x^(2) + 3y^(2) não podem ser ambos quadrados perfeitos. Comecemos com um lema bastante útil: Lema 16. Seja p um número primo da forma 4k + 3. Então p | m^(2) + n^(2) <--> p | m e p | n. Façamos inicialmente a primeira implicação. Se p $ m, então mp-1 a 1 (mod p), e daí temos as equivalências módulo p n^(2) a - m^(2) -> (nmp-2)^(2) a -(mp-1)^(2) a - 1 -> (nmp-2)p-1 a (-1)[(p-1)/2] a (-1)^(2k+1) a -1, o que contraria o teorema de Fermat. Assim, p | m e p | n. A recíproca é óbvia. Voltando ao problema, suponha que existam w, z inteiros positivos tais que 3x^(2) + 4y^(2) = w^(2) e 4x^(2) + 3y^(2) = z^(2). Então 7x^(2) + 7y^(2) = w^(2) + z^(2) (*). Afirmamos que a equação (*) não possui solução. Para isso, seja S o conjunto formado pelas soluções inteiras (x, y, w, z) de (*), e tome (a, b, c, d) pertence S com c^(2) + d^(2) mínimo. Pelo lema, temos que 7 | c e 7 | d, e daí c = 7c2 e d = 7d2. Mas então a^(2) + b^(2) = 7c22 + 7d22 -> (c2, d2, a, b) pertence S, com a^(2) + b^(2) < 7(a^(2) + b^(2)) = c^(2) + d^(2), o que contraria a minimalidade de (a, b, c, d). **** 1.1 Problemas Propostos **** Problema 17. Prove que se p é primo então ap a bp (mod p) -> ap a bp (mod p^(2)) Problema 18. Encontre os restos da divisões de: a) 300^(3000) - 1 por 1001 b) 7^(120) - 1 por 143 Problema 19. Encontre o resto de 111 ... 11p-1 uns por p, onde p é um primo maior que 5. Problema 20. Prove que se n é ímpar, então n^(5) a n (mod 240). Problema 21. Sejam p e q primos distintos. Mostre que i) (a + b)p a ap + bp (mod p) ii) pq + qp a p + q (mod pq) iii) \[(pq + pq)/pq] / é par se p, q não= 2. Problema 22. Mostre que se p é primo e a^(2) a b^(2) (mod p), então a a +ou- b (mod p). Problema 23. Encontre os últimos três dígitos de 7^(9999) Problema 24. Prove que 20^(15) - 1 é divisível por 11 ·31 ·61 Problema 25. Sejam {a1, a2, ... , a101} e {b1, b2, ... , b101} sistemas completos de resíduos módulo 101. Pode {a1b1, a2b2, ... , a101b101} ser um sistema completo de resíduos módulo 101? Problema 26. (Balcânica 2003) Existe um conjunto B de 4004 inteiros positivos tal que, para cada subconjunto A de B com 2003 elementos, a soma dos elementos em A não é divisível por 2003? Problema 27. Para um inteiro ímpar n > 1, seja S o conjunto de inteiros x, 1 <= x <= n, tal que ambos x e x + 1 são relativamente primos com n. Mostre que o produto de todos os elementos de S deixa resto 1 na divisão por n. Problema 28. Sejam n um inteiro positivo maior que 1 e p um primo positivo tal que n divide p - 1 e p divide n^(3) - 1. Mostre que 4p - 3 é um quadrado perfeito. **** 1.2 Dicas e Soluções **** 17. Pelo teorema de Fermat, a a ap a bp a b (mod p). Assim, ap-1 + ap-2 b + ... + abp-2 + bp-1 a ap-1 + ap-1 + ... + ap-1 a pap-1 a 0 (mod p) Como a - b a 0 (mod p), temos: ap - bp = (a - b)(ap-1 + ap-2b + ... + abp-2 + bp-1) a 0 (mod p^(2)) 19. Veja que: 999 ... 99 111 ... 11 = ================================== ================================== 9 p-1 uns 10p-1 - 1 = ================================== 9 Pelo teorema de Fermat, o numerador 10p-1 - 1 é divisível por p visto que p não= 5. Além disso, usando que p não= 2 e 3, segue que [(10p-1 - 1)/9] também é múltiplo de p. 20. Proceda como no exemplo 20. 21. i) Pelo teorema de Fermat: (a + b)p a a + b a ap + bp (mod p). ii) Pelo teorema de Fermat, pq + qp a 0 + q a p + q (mod p) pq + qp a p + 0 a p + q (mod q) 22. Veja que (a - b)(a + b) a 0 (mod p) e assim a - b a 0 (mod p) ou a + b a 0 (mod p). 25. Suponha, por abusurdo, que seja possível. Sejam ai e bj tais que ai a bj a 0 (mod 101). Se i não= j, o conjunto {a1b1, a2b2, ... , a101b101} teria dois inteiros com resto 0 na divisão por p e não poderia ser um scr. Suponha, sem perda de generalidade, que i = j = 101, então: 100! a (a1b1)(a2b2) ... (a100b100) a (a1a2 ... a100)(b1b2 ... b100) a (100!)(100!) a (100!)^(2) (mod 101) Assim, 100! a 1 (mod 101). Isso contradiz o teorema de Wilson. 26. Sim. Um exemplo de tal conjunto é a união de um conjunto de 2002 inteiros positivos que deixem resto 0 com outro conjunto composto por 2002 inteiros que deixem resto 1 por 2003. =============================================================================== **** Notas de Rodapé: **** {1} Documento: "... gaia/educacional/matematica/pot2tn06/Aula06-CongruenciasII.pdf".