Lista 4 - Teoria Dos Números

Teoria dos Números – Lista 4 (Congruência)
Aluno: _____________________________________________________
Prof: Helano Leom
1. Ache o resto da divisão de:
𝑎) 710 𝑝𝑜𝑟 51 𝑏) 2100 𝑝𝑜𝑟 11
𝑐) 14256 𝑝𝑜𝑟 17 𝑑) (116 + 1717 )21 𝑝𝑜𝑟 8
𝑒) 1316 − 225 515 𝑝𝑜𝑟 3 𝑓) 15 + 25 + ⋯ + 1005 𝑝𝑜𝑟 4
𝑔) 1! + 2! + ⋯ + (1010 )! 𝑝𝑜𝑟 40 ℎ) (4103 + 2 ⋅ 5104 )122 𝑝𝑜𝑟 13
2. Sejam 𝑎, 𝑝 ∈ ℕ, com 𝑝 primo. Mostre que 𝑎2 ≡ 1 (𝑚𝑜𝑑 𝑝), então 𝑎 ≡ 1 (𝑚𝑜𝑑 𝑝) ou

𝑎 ≡ −1 (𝑚𝑜𝑑 𝑝).
3. Sejam 𝑎, 𝑏, 𝑛 ∈ ℤ, com 𝑛 > 1. Mostre que se 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) então 𝑚𝑑𝑐(𝑛, 𝑎) =

𝑚𝑑𝑐(𝑛, 𝑏).
4. Use congruência para verificar que:

𝑎) 89 | 244 − 1 𝑏) 97 | 248 − 1 𝑐) 23 | 211 − 1
5. Para todo 𝑛 ∈ ℕ, mostre que:

𝑎) 1016𝑛 − 1 é 𝑑𝑖𝑣𝑖𝑠𝑖𝑣𝑒𝑙 𝑝𝑜𝑟 70 𝑎) 198𝑛 − 1 é 𝑑𝑖𝑣𝑖𝑠𝑖𝑣𝑒𝑙 𝑝𝑜𝑟 17
6. A que número, entre 0 𝑒 6, é congruente módulo 7, o produto 11 ⋅ 18 ⋅ 2322 ⋅ 13 ⋅ 19?
7. A que número, entre 0 𝑒 3, é congruente módulo 4, a soma 1 + 2 + 22 + ⋯ + 219 ?
8. Resolva as seguintes congruências lineares:

𝑎) 25𝑋 ≡ 15(𝑚𝑜𝑑 29) 𝑏) 5𝑋 ≡ 2(𝑚𝑜𝑑 26) 𝑐) 140𝑋 ≡ 133(𝑚𝑜𝑑 301)
9. Sejam 𝑎, 𝑏 ∈ ℤ e 𝑚, 𝑛, 𝑚1 , 𝑚2 , … , 𝑚𝑟 inteiros maiores do que 1. Mostre que:

a) se 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) e 𝑛 | 𝑚, então 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛)
b) 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚𝑖 ), ∀𝑖 ∈ {1,2, … , 𝑟} se, e somente se, 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 [𝑚1 , 𝑚2 , … , 𝑚𝑟 ])
10. Resolva o seguinte sistema de congruências lineares:
17𝑋 ≡ 3(𝑚𝑜𝑑 2)
17𝑋 ≡ 3(𝑚𝑜𝑑 3)
{
17𝑋 ≡ 3(𝑚𝑜𝑑 5)
17𝑋 ≡ 3(𝑚𝑜𝑑 7)
11. Resolva os seguintes sistemas de congruências lineares:
𝑋 ≡ 1(𝑚𝑜𝑑 3) 𝑋 ≡ 5(𝑚𝑜𝑑 6)
𝑎) {𝑋 ≡ 2(𝑚𝑜𝑑 5) 𝑏) {𝑋 ≡ 4(𝑚𝑜𝑑 11)
𝑋 ≡ 3(𝑚𝑜𝑑 7) 𝑋 ≡ 3(𝑚𝑜𝑑 7)
12. Determine o menor inteiro 𝑎 > 100 tal que 2 | 𝑎, 3 | (𝑎 + 1), 4 | (𝑎 + 2), 5 |(𝑎 + 3)
e 6 | (𝑎 + 4).
13. Se de uma cesta de ovos retirarmos duas unidades por vez, sobra um ovo. O mesmo
ocorre quando são retirados de 3 em 3, de 4 em 4, de 5 em 5 e de 6 em 6. Mas não resta
nenhum ovo se retirarmos de 7 em 7. Determine o menor número possível de ovos que
cumpre tais condições.
14. Utilize o Teorema Chinês do Resto para resolve o sistema de congruências:
2𝑋 ≡ 1(𝑚𝑜𝑑 31)
{ 6𝑋 ≡ 5(𝑚𝑜𝑑 11)
3𝑋 ≡ 17(𝑚𝑜𝑑 29)
Dica: Note que (𝑛 + 1)𝑋 ≡ 𝑋(𝑚𝑜𝑑 𝑛).

Lista 4 - Teoria Dos Números

Enviado por

Direitos autorais:

Formatos disponíveis

Lista 4 - Teoria Dos Números

Enviado por

Dados do documento

Descrição original:

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Lista 4 - Teoria Dos Números

Enviado por

Direitos autorais:

Formatos disponíveis

Teoria dos Números – Lista 4 (Congruência)

1. Ache o resto da divisão de:

𝑎) 710 𝑝𝑜𝑟 51 𝑏) 2100 𝑝𝑜𝑟 11

𝑐) 14256 𝑝𝑜𝑟 17 𝑑) (116 + 1717 )21 𝑝𝑜𝑟 8

𝑒) 1316 − 225 515 𝑝𝑜𝑟 3 𝑓) 15 + 25 + ⋯ + 1005 𝑝𝑜𝑟 4

𝑔) 1! + 2! + ⋯ + (1010 )! 𝑝𝑜𝑟 40 ℎ) (4103 + 2 ⋅ 5104 )122 𝑝𝑜𝑟 13

2. Sejam 𝑎, 𝑝 ∈ ℕ, com 𝑝 primo. Mostre que 𝑎2 ≡ 1 (𝑚𝑜𝑑 𝑝), então 𝑎 ≡ 1 (𝑚𝑜𝑑 𝑝) ou

3. Sejam 𝑎, 𝑏, 𝑛 ∈ ℤ, com 𝑛 > 1. Mostre que se 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) então 𝑚𝑑𝑐(𝑛, 𝑎) =

4. Use congruência para verificar que:

5. Para todo 𝑛 ∈ ℕ, mostre que:

6. A que número, entre 0 𝑒 6, é congruente módulo 7, o produto 11 ⋅ 18 ⋅ 2322 ⋅ 13 ⋅ 19?

7. A que número, entre 0 𝑒 3, é congruente módulo 4, a soma 1 + 2 + 22 + ⋯ + 219 ?

8. Resolva as seguintes congruências lineares:

9. Sejam 𝑎, 𝑏 ∈ ℤ e 𝑚, 𝑛, 𝑚1 , 𝑚2 , … , 𝑚𝑟 inteiros maiores do que 1. Mostre que:

11. Resolva os seguintes sistemas de congruências lineares:

14. Utilize o Teorema Chinês do Resto para resolve o sistema de congruências:

Dica: Note que (𝑛 + 1)𝑋 ≡ 𝑋(𝑚𝑜𝑑 𝑛).

Você também pode gostar