Lista 4 - Congruência I

Prévia do material em texto

Universidade Federal de Pernambuco
Teoria dos Números
Congruência
Professora: Maria do Desterro A. da Silva 1
Exercícios
1. Achar os inteiros que deixam resto 1, 2, 3 quando divididos por 3, 4, 5, respectiva-
mente.
2. Ache o número que quando somado com (n2−1)1000(n2+1)1001 torna o resultado
divisível por n.
3. Encontre os valores:
(a) φ(8)
(b) φ(11)
(c) φ(14)
(d) φ(125)
(e) φ(81)
4. Se n = pr, onde p é um número primo e r ⩾ 1, então φ(n) = pr−1(p− 1).
5. Sejam r, s inteiros maiores do que ou iguais a 1 e p um número primo. Então
φ(pr) ⋅ φ(ps) < φ(pr+s).
1Professora Assistente do Núcleo de Formação Docente, UFPE (desterrouepb@gmail.com)
1
6. Encontre o resto da divisão de 3102 por 101.
7. Use o Pequeno Teorema de Fermat para verificar que 17 divide 11104 + 1.
8. Prove que 1812 deixa resto 1 quando dividido por 7.
9. Se a e n sao primos entre si, então x = baφ(n)−1 é a única solução módulo n da
congruência linear ax ≡ b(mod n).
10. Mostre que p é o menor primo que divide (p− 1)! + 1.
11. Mostre que se p e q são primos distintos, então pq−1 + qp−1 ≡ 1(mod p).
2