Índice Superior

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

Sumário

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 ≡ 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,  a^p ≡ 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 [(n⁵)/5] + [(n³)/3] + [7n/15]  é um inteiro para todo inteiro  n.

     Primeiramente note que [(n⁵)/5] + [(n³)/3] + [7n/15] = [(3n⁵ + 5n³ + 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  n⁷ ≡ n     (mod 42), ∀n ∈ N

     Pelo teorema de Fermat,

     Como 2, 3 e 7 são primos entre si,  n⁷ ≡ 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²⁵ − a  é divisível por  n  para cada inteiro  a.

     Se  n  satisfaz o enunciado,  p²  (p  primo) não pode dividí-lo, pois  p²⁵ − p  não é divisível por  p². Assim,  n  é múltiplo de primos diferentes. Os fatores primos de  n  são fatores de  2²⁵ − 2 = 2 ·3² ·5 ·7 ·13 ·17 ·241. Entretanto,  n  não é divisível por 17 e 241 pois  3²⁵ ≡ − 3     (mod 17)  e  3²⁵ ≡ 32     (mod 241). Seguindo o exemplo anterior, podemos usar o teorema de Fermat para mostrar que  a²⁵ ≡ 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 é  2⁵ − 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  2ⁿ − 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  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,

     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  x² ≡ − 1     (mod 19),  x¹⁸ ≡ (−1)⁹ ≡ 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 {a₁,  a₂, ... ,  a_m} e {b₁,  b₂, ... ,  b_m} 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  a_n  definida por  a₁ = 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  a_k  é múltiplo de 7. Seja  a_2k−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  3x² + 4y²  e  4x² + 3y²  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  m^p−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  7x² + 7y² = w² + z² (∗). 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  c² + d²  mínimo. Pelo lema, temos que  7 | c  e  7 | d, e daí  c = 7c^′  e  d = 7d^′. Mas então  a² + b² = 7c^′2 + 7d^′2 ⇒ (c^′, d^′, a, b) ∈ S, com

o que contraria a minimalidade de (a,  b,  c,  d).

1.1  Problemas Propostos

     Problema 17. Prove que se  p  é primo então

     Problema 18. Encontre os restos da divisões de:

     a)  300³⁰⁰⁰ − 1  por 1001

     b)  7¹²⁰ − 1  por 143

     Problema 19. Encontre o resto de 111 …11_p−1 uns  por  p, onde  p  é um primo maior que 5.

     Problema 20. Prove que se  n  é ímpar, então  n⁵ ≡ n     (mod 240).

     Problema 21. Sejam  p  e  q  primos distintos. Mostre que

     i)  (a + b)^p ≡ a^p + b^p     (mod p)

     ii)  p^q + q^p ≡ p + q     (mod pq)

     iii) [(p^q + p^q)/pq]   é par se  p,  q ≠ 2.

     Problema 22. Mostre que se  p  é primo e  a² ≡ b²     (mod p), então  a ≡ ± b     (mod p).

     Problema 23. Encontre os últimos três dígitos de  7⁹⁹⁹⁹

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

     Problema 25. Sejam {a₁,  a₂, ... ,  a₁₀₁} e {b₁,  b2, ... ,  b₁₀₁} sistemas completos de resíduos módulo 101. Pode {a₁b₁,  a₂b₂, ... ,  a₁₀₁b₁₀₁} 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³ − 1. Mostre que  4p − 3  é um quadrado perfeito.

1.2  Dicas e Soluções

     17. Pelo teorema de Fermat,  a ≡ a^p ≡ b^p ≡ b     (mod p). Assim,

     Como  a − b ≡ 0     (mod p), temos:

     19. Veja que:

     Pelo teorema de Fermat, o numerador  10^p−1 − 1  é divisível por  p  visto que  p ≠ 5. Além disso, usando que  p ≠ 2  e 3, segue que [(10^p−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  a_i  e  b_j  tais que  a_i ≡ b_j ≡ 0     (mod 101). Se  i ≠ j, o conjunto {a₁b₁,  a₂b₂, ... ,  a₁₀₁b₁₀₁} 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.