tn-aula56-congruências_I_II

Prévia do material em texto

Polos Olímpicos de Treinamento
Curso de Teoria dos Números - Nível 2
Prof. Samuel Feitosa
Aula 6
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 6≡ 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) ak ≡ bk (mod m) ∀k ∈ N
vi) Se mdc(k,m) = d, então ka ≡ kb (mod m) ⇔ a ≡ b (mod m/d)
Demonstração. Sejam q1 e q2 tais que:
a− b = q1m
c− d = q2m
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 ≡ b+d (mod m). Usando que a− b (mod a)k− bk e que m | a− b,
conclúı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.
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
Exemplo 3. Calcule o resto de 4100 por 3.
Como 4 ≡ 1 (mod 3), temos 4100 ≡ 1100 = 1 (mod 3).
Exemplo 4. Calcule o resto de 4100 por 5.
Como 4 ≡ −1 (mod 5), temos 4100 ≡ (−1)100 = 1 (mod 5).
Exemplo 5. Calcule o resto de 4100 por 7.
Você deve ter percebido que encontrar relações do tipo a ≡ ±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:
40 ≡ 1 (mod 7), 41 ≡ 4 (mod 7), 42 ≡ 2 (mod 7), 43 ≡ 1 (mod 7).
Assim,
499 = (43)33 ≡ 133 = 1 (mod 7).
Como 43 ≡ 1 (mod 7), os restos das potências de 4 na divisão por 7 se repetem periodica-
mente de 3 em 3 pois 43k+r ≡ 43k · 4r ≡ 4r (mod 7).
Exemplo 6. Qual o resto de 3636 + 4141 na divisão por 77?
Inicialmente devemos perceber que existe uma relação entre os números do problema: 36+
41 = 77. Assim:
−36 ≡ 41 (mod 77),
(−36)41 ≡ 4141 (mod 77),
3636(1− 365) ≡ 3636 + 4141 (mod 77).
Nosso próximo passo é encontrar o resto de 365 na divisão por 77. Como 36 ≡ 1 (mod 7),
365 ≡ 1 (mod 7). Além disso, 36 ≡ 3 (mod 1)1 produzindo 365 ≡ 35 ≡ 1 (mod 1)1.
Como mdc(7, 11) = 1 e ambos dividem 365 − 1, podemos concluir que 77 | 365 − 1. Logo,
3636 + 4141 deixa resto 0 na divisão por 77.
Exemplo 7. Prove que p2 − 1 é diviśı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). Dáı, p2 ≡ 1 (mod 3).
Além disso, se p = 2k + 1, segue que p2 = 4k(k + 1) + 1 ≡ 1 (mod 8) pois k(k + 1) é par.
Como mdc(8, 3) = 1 e ambos dividem p2 − 1, segue que 24 | p2 − 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:
x21 + x
2
2 + . . . x
2
n = 2001.
2
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
Analisando a congruência módulo 8, obtemos:
x21 + x
2
2 + . . . x
2
n = 2001 (mod 8)
1 + 1 + . . .+ 1 ≡ 1 (mod 8)
n ≡ 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 = 432 + 112 + 52 + 12 + 12 + 12 + 12 + 12 + 12.
Exemplo 9. (IMO) Seja s(n) a soma dos d́ıgitos de n. Se N = 44444444, 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 74444 (mod 9).
Seguindo os métodos dos primeiros exemplos, seria interessante encontrarmos um inteiro r
tal que 7r ≡ ±1 (mod 9). O menor inteiro positivo com essa propriedade é r = 3. Como
4444 = 1481 · 3 + 1, temos:
74444 ≡ 71481·3+1 ≡ (73)1481 · 7 ≡ 7 (mod 9).
Nosso próximo passo é estimar o valor de s(B). Como N = 44444444 < 105·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, dáı s(B) = 7.
Exemplo 10. Prove que 11n+2 + 122n+1 é diviśı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 ≡ 11 (mod 133),
122 ≡ 11 (mod 133),
122n ≡ 11n (mod 133),
122n+1 ≡ 11n · 12 (mod 133),
122n+1 ≡ 11n · (−121) + 133 · 11n (mod 133),
122n+1 ≡ −11n+2 (mod 133).
Exemplo 11. Prove que n5 + 4n é diviśıvel por 5 para todo inteiro n
Inicialmente note que n5 + 4n = n(n4 + 4). Se n ≡ 0 (mod 5), não há o que fazer. Se
n ≡ ±1 (mod 5), n4+4 ≡ 1+4 = 0 (mod 5). Finalmente, se n ≡ ±2 (mod 5), n2 ≡ 4 ≡ −1
(mod 5) e consequentemente n4 + 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
n2(n2 + 16) é diviśıvel por 720. A rećıproca é verdadeira?
3
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
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,
n2(n2 + 16) = 144(9k4 + 4k2).
Resta provar que 9k4 +4k2 é um múltiplo de 5. Vamos analisar a igualdade acima módulo
5.
i) Se k ≡ 0, 2 ou 3 (mod 5), temos 9k4 + 4k2 ≡ 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 rećıproca não é verdadeira. Basta tomar, por exemplo,
n = 90.
Problemas Propostos
Problema 13. Determine o resto de 220 − 1 na divisão por 41.
Problema 14. Qual o resto de 12000 + 22000 + . . .+ 20002000 na divisão por 7?
Problema 15. Qual o resto na divisão de 270 + 370 por 13?
Problema 16. Qual o resto de 3200 por 100?
Problema 17. (Estônia 2000) Determine todos os posśıveis restos da divisão do quadrado
de um número primo com o 120 por 120.
Problema 18. Qual o último d́ıgito de 777777?
Exemplo 19. Prove que 22225555 + 55552222 é diviśıvel por 7.
Problema 20. Prove que o número n3 + 2n é diviśıvel por 3 para todo natural n.
Problema 21. Prove que n2 + 1 não é diviśıvel por 3 para nenhum n inteiro.
Problema 22. Prove que n3 + 2 não é diviśıvel por 9 para nenhum n inteiro.
Problema 23. Prove que p2 − q2 é diviśı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 é
diviśıvel por 40.
Problema 25. Se n é ı́mpar, prove que 7|22n+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 posśıveis restos da divisão de n por 9?
Problema 27. Prove que não existem inteiros positivos x1, x2, . . . , x14 tais que:
x41 + x
4
2 + . . .+ x
4
14 = 1599.
4
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
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 2015 − 1 é diviśıvel por 11 · 31 · 61
Problema 30. (Alemanha 1997) Determine todos os primos p para os quais o sistema
p+ 1 = 2x2
p2 + 1 = 2y2
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.
Dicas e Soluções
13. Veja que
25 = 32 ≡ −9 (mod 41) ⇒
210 ≡ 81 ≡ −1 (mod 42) ⇒
220 ≡ 1 (mod 41).
Assim, o resto procurado é zero.
14. Como i2000 ≡ (i + 7k)2000 (mod 7), podemos simplificar o problema calculando pri-
meiramente o valor de:
12000 + 22000 + 32000 + 42000 + 52000 + 62000 + 72000 (mod 7).
Outra observação importante que simplificará o cálculo é perceber que 23 ≡ 1 (mod 7).
Assim,
23k ≡ 1 (mod 7), 23k+1 ≡ 2 (mod 7), e 23k+2 ≡ 4(mod 7).
Usando isso e o fato de que 2000 é par, temos:
12000 + 22000 + 32000 + 42000 + 52000 + 62000 + 72000 ≡
12000 + 22000 + (−4)2000 + 42000 + (−2)2000 + (−1)2000 + 02000 ≡
≡ 1 + 4 + 2 + 2 + 4 + 1 + 0
≡ 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:
19962000 + 19972000 + 19982000 + 19992000 + 20002000 ≡ 1 + 4 + 2 + 2 + 4
≡ 6 (mod 7).
Assim, o resto da soma na divisão por 7 é 6.
5
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
15. Inicialmente é interessante buscarmos alguma relação entre os números envolvidos no
problema. Como 13 = 4 + 9, podemos escrever:
9 ≡ −4 (mod 13) ⇒
935 ≡ (−4)35 (mod 13) ⇒
370 + 270 ≡ 0 (mod 13).
17. Use a fatoração 120 = 3 ·5 ·23 e analise a congruência módulo 3, 5 e 8 separadamente.
18. Se n não é múltiplo de 3, sabemos que n2 ≡ 1 (mod 3). Assim n2 + 2 ≡ 0 (mod 3).
Se n é múltiplo de 3, n ≡ 0 (mod 3). Em qualquer caso, n(n2 + 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:
n 0 1 2 3 4 5 6 7 8
n3 0 1 8 0 1 8 0 1 8
Como nenhum cubo perfeito diexa resto 7 na divisão por 9, n3 + 2 6≡ 0 (mod 9).
23. Proceda como no exemplo 7.
25.
22n+1 + 3n+2 ≡ 4n · 2 + 3n · 9
≡ (−3)n · 2 + 3n · 2
≡ 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)) ≡ 3r ≡ 1995 (mod 9).
Assim, r ≡ 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 x4 ≡ 0 ou 1 (mod 1)6.
Assim, a soma
x41 + x
4
2 + . . .+ x
4
14
é congruente a um dos números do conjunto {0, 1, . . . , 14} m odulo 16 enquanto que
1599 ≡ 15 (mod 16). Um absurdo.
6
28. x ≡ 5 (mod 12).
30. Suponha sem perda de generalidade que x, y ≥ 0. Como p + 1 é par, p 6= 2. Além
disso,
2x2 ≡ 1 ≡ 2y2 (mod p)
e consequentente, usando que p é ı́mpar, x ≡ ±y (mod p). Como x < y < p, temos
p2 + 1 = 2(p− x)2 = 2p2 − 4px+ p+ 1,
de modo que p = 4x − 1, 2x2 = 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, é posśıvel mostrarmos
que os restos de seus termos na divisão por qualquer número formam uma sequência
periódica.
Referências
[1] E. Carneiro, O. Campos and F. Paiva, Olimṕı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.
Polos Olímpicos de Treinamento
Curso de Teoria dos Números - Nível 2
Prof. Samuel Feitosa
Aula 6
Congruências II
Na aula de hoje, aprenderemos um dos teoremas mais importantes do curso: o ”pe-
queno”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
ap−1 ≡ 1 (mod p).
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 é diviśı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 ≡ 1 · 2 · 3 · . . . (p− 1) (mod p),
ap−1(p− 1)! ≡ (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
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:
3n5 + 5n3 + 7n ≡ 5n3 + 7n ≡ 5n+ 7n = 12n ≡ 0 (mod 3),
3n5 + 5n3 + 7n ≡ 3n5 + 7n ≡ 3n+ 7n = 10n ≡ 0 (mod 5).
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
Problema 4. Mostre que n7 ≡ n (mod 42), ∀n ∈ N
Pelo teorema de Fermat,
n7 ≡ n (mod 7)
n7 ≡ (n3)2 · n ≡ n2 · n = n3 ≡ n (mod 3)
n7 ≡ (n2)3 · n ≡ n3 · n = (n2)2 ≡ n2 ≡ n (mod 2)
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 é diviśı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 é diviśı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 é diviśı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
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:
111 . . . 11
︸ ︷︷ ︸
p uns
=
10p − 1
9
.
Assim, podemos escrever o número S = 111 . . . 11222 . . . 22333 . . . 33 . . . 888 . . . 88999 . . . 99
como:
S =
10p − 1
9
· 108p + 2 ·
10p − 1
9
· 107p + . . . 9 ·
10p − 1
9
9S = (10p − 1) · 108p + 2 · (10p − 1) · 107p + . . . 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) é diviśıvel por p pois mdc(p, 9) = 1. Pelo teorema de Fermat:
9S = (10p − 1) · 108p + 2 · (10p − 1) · 107p + . . . 9 · (10p − 1)
≡ (10− 1) · 108 + 2 · (10− 1) · 107 + . . . 9 + ·(10− 1) (mod p)
≡ 9 · 123456789 (mod p).
2
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
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
≡ (2p−1)(p−1)
2k−1
≡ 1(p−1)
2k−1
= 1 ≡ (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 ≡ 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 ≡ 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
(p− 1)! ≡ −1 (mod p)
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, teŕı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,
(p− 1)! ≡ 1 · (p− 1) ≡ −1 (mod p).
Exemplo 10. (Estônia 2000) Prove que não é posśıvel dividir qualquer conjunto de 18
inteiros consecutivos em dois conjuntos disjuntos A e B tais que o produtos 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
produtos 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 dos produtos dos elementos de A.
Calculemos então o resto na divisão por 19 do produto de todos os 18 inteiros consecutivos:
x · x ≡ n(n+ 1)(n+ 2)(n+ 3) . . . (n+ 17)
≡ 1 · 2 · 3 . . . · 18
≡ −1 (mod 19)(Pelo teorema de Wilson).
Como x2 ≡ −1 (mod 19), x18 ≡ (−1)9 ≡ 1 (mod 1)9. Isso contraria o teorema de Fermat
e obtemos um absurdo.
3
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
Definição 11. Um conjunto S é chamado de sistema completo de reśıduos módulo n, de-
notado 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 porm. Como existem exatamentem restos na divisão porm, o conjunto
é um scr.
Exemplo 13. Seja m um inteiro positivo par. Suponha que {a1, a1, . . . , am} e {b1, b2, . . . , bm}
são dois sistemas completos de reśıduso módulo m. Prove que
S = {a1 + b1, a2 + b2, . . . , am + bm}
não é um sistema completo de reśıduos.
Suponha que S seja um scr, então:
1 + 2 + . . .+m ≡ (a1 + b1) + (a2 + b2) + . . .+ (an + bn) (mod m)
≡ (a1 + a2 + . . .+ an) + (b1 + b2 + . . .+ bn)
≡ 2(1 + 2 + . . .+ n)
≡ 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 diviśı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 ≡ s (mod 7)
a2k+1 = a2k + ak ≡ s (mod 7)
4
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
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 ≡ t+ a2k−1 ≡ t+ s (mod 7)
a4k−1 ≡ t+ s+ a2k−1 ≡ t+ 2s (mod 7)
a4k ≡ t+ 2s+ a2k ≡ t+ 3s (mod 7)
a4k+1 ≡ t+ 3s+ a2k ≡ t+ 4s (mod 7)
a4k+2 ≡ t+ 4s+ a2k+1 ≡ t+ 5s (mod 7)
a4k+3 ≡ t+ 5s+ a2k+2 ≡ 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 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
p | m2 + n2 ⇐⇒ p | m e p | n.
Façamos inicialmente a primeira implicação. Se p ∤ m, então mp−1 ≡ 1 (mod p), e dáı
temos as equivalências módulo p
n2 ≡ −m2
⇒ (nmp−2)2 ≡ −(mp−1)2
≡ −1
⇒ (nmp−2)p−1 ≡ (−1)
p−1
2
≡ (−1)2k+1
≡ −1,
o que contraria o teorema de Fermat. Assim, p | m e p | n.
A rećıproca é óbvia. Voltando ao problema, suponha que existam w, z inteiros positivos
tais que
3x2 + 4y2 = w2 e
4x2 + 3y2 = z2.
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
5
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
com c2 + d2 mı́nimo. Pelo lema, temos que 7|c e 7|d, e dáı c = 7c′ e d = 7d′. Mas então
a2 + b2 = 7c′2 + 7d′2 ⇒ (c′, d′, a, b) ∈ S, com
a2 + b2 < 7(a2 + b2) = c2 + d2,
o que contraria a minimalidade de (a, b, c, d).
Problemas Propostos
Problema 17. Prove que se p é primo então
ap ≡ bp (mod p) ⇒ ap ≡ bp (mod p2)
Problema 18. Encontre os restos da divisões de:
a) 3003000 − 1 por 1001
b) 7120 − 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 n5 ≡ n (mod 240).
Problema 21. Sejam p e q primos distintos. Mostre que
i) (a+ b)p ≡ ap + bp (mod p)
ii) pq + qp ≡ p+ q (mod pq)
iii)
⌊
pq + pq
pq
⌋
é par se p, q 6= 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 é diviśıvel por 11 · 31 · 61
Problema 25. Sejam {a1, a2, ..., a101} e {b1, b2, ..., b101} sistemas completos de reśıduos
módulo 101. Pode {a1b1, a2b2, ..., a101b101} ser um sistema completo de reśı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 é
diviśı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.
6
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
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.
Dicas e Soluções
17. Pelo teorema de Fermat, a ≡ ap ≡ bp ≡ b (mod p). Assim,
ap−1 + ap−2b+ . . .+ abp−2 + bp−1 ≡ ap−1 + ap−1 + . . .+ ap−1
≡ pap−1
≡ 0 (mod p)
Como a− b ≡ 0 (mod p), temos:
ap − bp = (a− b)(ap−1 + ap−2b+ . . .+ abp−2 + bp−1) ≡ 0 (mod p2)
19. Veja que:
111 . . . 11
︸ ︷︷ ︸
p−1 uns
=
999 . . . 99
9
=
10p−1 − 1
9
Pelo teorema de Fermat, o numerador 10p−1 − 1 é diviśıvel por p visto que p 6= 5.
Além disso, usando que p 6= 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:
(a+ b)p ≡ a+ b
≡ ap + bp (mod p).
ii) Pelo teorema de Fermat,
pq + qp ≡ 0 + q ≡ p+ q (mod p)
pq + qp ≡ p+ 0 ≡ p+ q (mod q)
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 posśıvel. Sejam ai e bj tais que ai ≡ bj ≡ 0
(mod 101). Se i 6= j, o conjunto {a1b1, a2b2, ..., a101b101} teria dois inteiros com resto
7
POT 2012 - Teoria dos Números - Nı́vel 2 - Aula 5 - Samuel Feitosa
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! ≡ (a1b1)(a2b2) . . . (a100b100)
≡ (a1a2 . . . a100)(b1b2 . . . b100)
≡ (100!)(100!)
≡ (100!)2 (mod 101)
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 inteirosque deixem resto
1 por 2003.
8