Arquivos de Impressão: Tamanho A4 (pdf), Tamanho A5 (pdf), Texto (txt).
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 ≡ kb (mod m) e mdc(m, k) = 1, então 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
|
Além disso, para todo inteiro a, ap ≡ 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,
|
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 [(n5)/5] + [(n3)/3] + [7n/15] é um inteiro para todo inteiro n.
Primeiramente note que [(n5)/5] + [(n3)/3] + [7n/15] = [(3n5 + 5n3 + 7n)/15]. Como mdc(3, 5) = 1, basta mostrarmos que o numerador é mútiplo de 3 e 5. Pelo teorema de Fermat:
|
Problema 4. Mostre que n7 ≡ n (mod 42), ∀n ∈ N
|
Como 2, 3 e 7 são primos entre si, n7 ≡ 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 a25 − a é divisível por n para cada inteiro a.
Se n satisfaz o enunciado, p2 (p primo) não pode dividí-lo, pois p25 − p não é divisível por p2. Assim, n é múltiplo de primos diferentes. Os fatores primos de n são fatores de 225 − 2 = 2 ·32 ·5 ·7 ·13 ·17 ·241. Entretanto, n não é divisível por 17 e 241 pois 325 ≡ − 3 (mod 17) e 325 ≡ 32 (mod 241). Seguindo o exemplo anterior, podemos usar o teorema de Fermat para mostrar que a25 ≡ a (mod p) para p ∈ {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 é 25 − 1 = 31.
Exemplo 6. Prove que para cada primo p, a diferença
|
(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:
|
Assim, podemos escrever o número S = 111 …11222 …22333 …33 …888 …88999 …99 como:
|
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:
|
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:
|
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
|
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 ≡ 1 (mod m). Se y é outro inteiro que satisfaz a congruência, temos ax ≡ ay (mod m). Pelo primeiro lema, x ≡ 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
|
Demonstração. Em virtude do lema anterior, para cada a ∈ {2, 3, …, p−2}, existe um resto x ∈ {0, 1, 2, …, p − 1} tal que ax ≡ 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 a2 ≡ 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,
|
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:
|
Como x2 ≡ − 1 (mod 19), x18 ≡ (−1)9 ≡ 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 ∈ S tal que i ≡ 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 ≡ t + js (mod m), temos is ≡ js (mod m) e i ≡ j (mod m). Como i, j ∈ {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
|
não é um sistema completo de resíduos.
Suponha que S seja um scr, então:
|
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
|
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:
|
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.
|
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 3x2 + 4y2 e 4x2 + 3y2 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
|
Façamos inicialmente a primeira implicação. Se p ∤ m, então mp−1 ≡ 1 (mod p), e daí temos as equivalências módulo p
|
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
|
Então 7x2 + 7y2 = w2 + z2 (∗). 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) ∈ S com c2 + d2 mínimo. Pelo lema, temos que 7 | c e 7 | d, e daí c = 7c′ e d = 7d′. Mas então a2 + b2 = 7c′2 + 7d′2 ⇒ (c′, d′, a, b) ∈ S, com
|
o que contraria a minimalidade de (a, b, c, d).
Problema 17. Prove que se p é primo então
|
Problema 18. Encontre os restos da divisões de:
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 n5 ≡ n (mod 240).
Problema 21. Sejam p e q primos distintos. Mostre que
iii) [(pq + pq)/pq] é par se p, q ≠ 2.
Problema 22. Mostre que se p é primo e a2 ≡ b2 (mod p), então a ≡ ± b (mod p).
Problema 23. Encontre os últimos três dígitos de 79999
Problema 24. Prove que 2015 − 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 n3 − 1. Mostre que 4p − 3 é um quadrado perfeito.
17. Pelo teorema de Fermat, a ≡ ap ≡ bp ≡ b (mod p). Assim,
|
Como a − b ≡ 0 (mod p), temos:
|
|
Pelo teorema de Fermat, o numerador 10p−1 − 1 é divisível por p visto que p ≠ 5. Além disso, usando que p ≠ 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:
|
|
22. Veja que (a − b)(a + b) ≡ 0 (mod p) e assim a − b ≡ 0 (mod p) ou a + b ≡ 0 (mod p).
25. Suponha, por abusurdo, que seja possível. Sejam ai e bj tais que ai ≡ bj ≡ 0 (mod 101). Se i ≠ 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:
|
Assim, 100! ≡ 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.