Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
Resolucao da lista 9 Congruencia
Compartilhar
Prévia do material em texto
UNIVERSIDADE FEDERAL DE OURO PRETO
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA
LICENCIATURA EM MATEMÁTICA
Introdução à Teoria dos Números
Lista de exercícios: Congruência
Exercício 2 da página 31 do fascículo: Álgebra I, vol.2: Determine a congruência de 6m+5, módulo 4, sabendo-se que m
1 (mod 4).
Resolução:
m
1 (mod 4)
tal que
Logo
.
Exercício 3 da página 31 do fascículo: Álgebra I, vol.2: Sabendo-se que x
y (mod n), mostre que x²+y²
2(xy) (mod n²).
Resolução:
Se x
y (mod n), existe um inteiro q tal que x = nq + y.
Então x² = (nq + y)² = n²q² + 2nqy + y²
x² + y² = n²q² + 2nqy + 2y² =
= n²q² + 2y(nq+y) = n²q² + 2xy.
Logo x²+y²
2(xy) (mod n²).
Exercício 4 da página 31 do fascículo: Álgebra I, vol.2: Determine a classe
em Z3 e em Z5.
Resolução:
em Z3 : {x
Z3 / x ~ 2} = {x
Z / x
2 (mod 3)} =
{ x
Z / x = 3q + 2, q
Z}.
em Z5 : {x
Z5 / x ~ 2} = {x
Z / x
2 (mod 5)} =
{ x
Z / x = 5q + 2, q
Z}.
Exercício 2 da página 54 do fascículo Introdução à Criptografia: Determine se as afirmações a seguir são verdadeiras ou falsas:
25
1 (mod 12) VERDADEIRA
-5
-14 (mod 3) VERDADEIRA
12
-2 (mod 3) FALSA
5+7t
5 (mod 7), para todo t inteiro. VERDADEIRA
x²+17y
3 (mod 17)
x²
3 (mod 17) VERDADEIRA
Exercício 1 da página 42 do fascículo: Álgebra I, vol.2: Calcule:
a)
Resolução:
Temos que 2³ = 8
1(mod 7)
Como 6736730 = 3 x 2245576 + 2, então
b)
Temos que
Como 123400 = 5 x 24680, então
c)
Resolução:
O primeiro passo é efetuar potências de 13 para tentar encontrar:
13? = 1(mod 19)
O melhor que encontramos é 134 = 4 (mod 19).
Vamos agora dividir 234500 por 4:
234500 = 4 x 58625.
Então 13234500 = 134x58625
458625(mod 19).
O próximo passo é efetuar potências de 4 para tentar encontrar:
4? = 1(mod 19).
O melhor que encontramos é 43 = 7 (mod 19) .
Vamos agora dividir 58625 por 3:
58625 = 3x19541+2.
Então 458625= 43x19541+2
719541x 42 (mod 19).
O próximo passo é efetuar potências de 7 para tentar encontrar:
7? = 1(mod 19). Temos que 73 = 1 (mod 19).
Vamos agora dividir 19541 por 3:
19541 = 3 x 6513+ 2.
Então 719541x 42 = 73.6513+2 x 42
72 x 42.
Logo
13234500 = 134x58625= 458625= 43x19541+2 =719541x 42 = 73.6513+2 x 42 =72 x 42 =
49 x 16 = 784 = 5 (mod 19).
Exercício 1 da página 49 do fascículo: Álgebra I, vol.2: Escreva as tabelas de operações de soma e multiplicação de Zn, para os seguintes valores de n:
n = 2
+
0
1
0
0
1
1
1
0
x
0
1
0
0
0
1
0
1
n = 5
+
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
x
0
1
2
3
4
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
3
2
1
n = 7
+
0
1
2
3
4
5
6
0
0
1
2
3
4
5
6
1
1
2
3
4
5
6
0
2
2
3
4
5
6
0
1
3
3
4
5
6
0
1
2
4
4
5
6
0
1
2
3
5
5
6
0
1
2
3
4
6
6
0
1
2
3
4
5
x
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
2
0
2
4
6
1
3
5
3
0
3
6
2
5
1
4
4
0
4
1
5
2
6
3
5
0
5
3
1
6
4
2
6
0
6
5
4
3
2
1
n = 12
+
0
1
2
3
4
5
6
7
8
9
10
11
0
0
1
2
3
4
5
6
7
8
9
10
11
1
1
2
3
4
5
6
7
8
9
10
11
0
2
2
3
4
5
6
7
8
9
10
11
0
1
3
3
4
5
6
7
8
9
10
11
0
1
2
4
4
5
6
7
8
9
10
11
0
1
2
3
5
5
6
7
8
9
10
11
0
1
2
3
4
6
6
7
8
9
10
11
0
1
2
3
4
5
7
7
8
9
10
11
0
1
2
3
4
5
6
8
8
9
10
11
0
1
2
3
4
5
6
7
9
9
10
11
0
1
2
3
4
5
6
7
8
10
10
11
0
1
2
3
4
5
6
7
8
9
11
11
0
1
2
3
4
5
6
7
8
9
10
x
0
1
2
3
4
5
6
7
8
9
10
11
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
7
8
9
10
11
2
0
2
4
6
8
10
0
2
4
6
8
10
3
0
3
6
9
0
3
6
9
0
3
6
9
4
0
4
8
0
4
8
0
4
8
0
4
8
5
0
5
10
3
8
1
6
11
4
9
2
7
6
0
6
0
8
0
6
0
6
0
6
0
6
7
0
7
2
9
4
11
6
1
8
3
10
5
8
0
8
4
0
8
4
0
8
4
0
8
4
9
0
9
6
3
0
9
6
3
0
9
6
3
10
0
10
8
6
4
2
0
10
8
6
4
2
11
0
11
10
9
8
7
6
5
4
3
2
1
_1351527580.unknown
_1412530798.unknown
_1412530971.unknown
_1412531271.unknown
_1412531359.unknown
_1412531014.unknown
_1412530810.unknown
_1351527811.unknown
_1412530719.unknown
_1351528172.unknown
_1351527777.unknown
_1349263862.unknown
_1349264610.unknown
_1349264660.unknown
_1349264697.unknown
_1349264311.unknown
_1349263705.unknown
Continue navegando
Compartilhar