Lista 2 Fundamentos de Algebra com resolução

Prévia do material em texto

Semestre II, 2016. 12-1-2017. Fundamentos de A´lgebra
Segunda Tarefa.
Q 1
Usando o princ`ıpio da induc¸a˜o, prove que, para todo nu´mero natural n, vale:
1 · 3 · 5 · . . . · (2n− 1) = (2n)!
2n · n!
Resposta:
(i) Base Indutiva: O resultado vale para n = 1. De fato, 1 = 2!
2·1 .
(ii) Passo indutivo: seja k ≥ 1 e suponhamos que vale a formula
1 · 3 · 5 · . . . · (2k − 1) = (2k)!
2k · k!
e verificamos que, para k + 1, vale a formula:
1 · 3 · 5 · . . . · (2k − 1) · (2(k + 1)− 1) = 1 · 3 · 5 · . . . · (2k − 1) · (2k + 1) =
=
(2k)!
2k · k! · (2k + 1) =
(2k + 1)!
2k · k! ·
2(k + 1)
2(k + 1)
=
(2(k + 1))!
2k+1 · (k + 1)! .
1
Q 2
Para qualquer inteiro n ≥ 1, denotamos por Bn um conjunto de n linhas do plano tais que:
(i) na˜o sejam paralelas dois a dois,
(ii) treˆs linhas na˜o passam para o mesmo ponto.
Prove por induc¸a˜o que Bn divide o plano em 1 +
(
n+1
2
)
regio˜es distintas.
Resposta:
(i) Base Indutiva: O resultado vale para n = 1. De fato, uma linha L1 divide o plano
em duas regio˜es e 1 +
(
1+1
2
)
= 2.
(ii) Passo indutivo: seja k ≥ 1 e suponhamos que o resultado e´ verdadeiro para n = k e
vamos provar-lho para n = k + 1.
Seja Bk = {L1, . . . , Lk} e Bk+1 = {L1, . . . , Lk, Lk+1}. Por hipo´tese indutiva, Bk
divide o plano em 1 +
(
k+1
2
)
regio˜es distintas Pk. A linha Lk+1 intersecta as linhas
de Bk em k pontos distintos, para as hipo´teses de acima. Portanto Lk+1 e´ dividida
em n+ 1 segmentos distintos, dos quais dois sa˜o ilimitados. Cada segmento esta´ em
uma u´nica regia˜o de Pk e divide-lha em duas regio˜es distintas. Portanto Bk+1 divide
o plano em 1 +
(
k+1
2
)
+ (k + 1) regio˜es distintas. Agora:
1 +
(
k + 1
2
)
+ (k + 1) = 1 +
(
k + 1
2
)
+
(
k + 1
1
)
= 1 +
(
k + 2
2
)
.
2
Q 3
(i) Escreva o numero inteiro 149 na base 2.
(ii) Escreva o numero racional 0, 75 na base 5.
(iii) Qual’e´ o resto da divisa˜o do inteiro [234521653645216542654265431]7 por 49?
Resposta (i): Precisamos as diviso˜es euclidianas:
149 = 2 · 74 + 1
74 = 2 · 37 + 0
37 = 2 · 18 + 1
18 = 2 · 9 + 0
9 = 2 · 4 + 1
4 = 2 · 2 + 0
2 = 2 · 1 + 0
1 = 2 · 0 + 1.
Portanto 149 = [10010101]2.
(ii): Seja 0, 75 = [0, a1a2a3a4 . . .]5 (com 0 ≤ ai < 5, para i = 1, 2, 3, 4, . . .). Enta˜o:
α = 0, 75 =
a1
5
+
a2
52
+
a3
53
+
a4
54
+ . . . ,
5 · α = 3, 75 = a1 + a2
5
+
a3
52
+
a4
53
+ . . .⇒ a1 = 3,
5 · α− a1 = 0, 75 = a2
5
+
a3
52
+
a4
53
+ . . . ,
5(5 · α− a1) = 3, 75 = a2 + a3
5
+
a4
52
+ . . .⇒ a2 = 3,
5(5 · α− a1)− a2 = 0, 75 = a3
5
+
a4
52
+ . . . ,
5[5(5 · α− a1)− a2] = 3, 75 = a3 + a4
5
+ . . .⇒ a3 = 3.
E´ claro que os coeficientes ak = 3 repetem indefinidamente. Portanto 0, 75 = [0, 3¯]5.
(ii): 49 = [100]7. Portanto
[234521653645216542654265431]7 = [2345216536452165426542654]7 · [100]7 + [31]7
e o resto e´ [31]7 = 3 · 71 + 1 · 70 = 3 · 7 + 1 = 22.
3
Q 4
(i) Calcule o ma´ximo divisor comum dos nu´meros inteiros a = 506 e b = −2178.
(ii) Determine inteiros α e β tais que MDC(a, b) = α · a+ β · b.
Resposta (i): Utilizando o algoritmo de divisa˜o euclidiana obtemos:
2178 = 506 · 4 + 154
506 = 154 · 3 + 44
154 = 44 · 3 + 22
44 = 22 · 2 + 0.
Portanto MDC(506,−2178) = MDC(2178, 506) = 22.
(ii): Das identidades de acima, obtemos:
22 = 154− 44 · 3 = 154− 3(506− 154 · 3) = 10 · 154− 3 · 506 = 10(2178− 506 · 4)− 3 · 506 =
= 10 · 2178− 43 · 506 = (−43) · 506 + (−10) · (−2178).
Portanto α = −43 e β = −10.
4
Q 5
(i) Encontrar, se existem, todas as soluc¸o˜es inteiras da equac¸a˜o 33x− 22y = 54.
(ii) Encontrar, se existem, todas as soluc¸o˜es inteiras da equac¸a˜o 115x− 336y = 2.
Resposta: (i): MDC(33,−22) = 11 - 54. Portanto a equac¸a˜o na˜o tem soluc¸o˜es.
(ii): Utilizando o algoritmo de divisa˜o euclidiana obtemos:
336 = 115 · 2 + 106
115 = 106 · 1 + 9
106 = 9 · 11 + 7
9 = 7 · 1 + 2
7 = 2 · 3 + 1
2 = 1 · 2 + 0.
Portanto MDC(115, 336) = 1. Portanto a equac¸a˜o tem soluc¸o˜es. Ale´m disso, das identida-
des de acima, obtemos:
1 = 7− 2 · 3 = 7− 3(9− 7) = 4 · 7− 3 · 9 = 4(106− 9 · 11)− 3 · 9 = 4 · 106− 47 · 9 =
= 4 · 106− 47 · (115− 106) = 51 · 106− 47 · 115 = 51(336− 115 · 2)− 47 · 115 =
= 51 · 336− 149 · 115 = 115 · (−149)− 336 · (−51).
Portanto, uma soluc¸a˜o particular e´ x = −298, y = −102 e a soluc¸a˜o geral e´
x = 38 + k · 336, y = 13 + k · 115,
para todos k ∈ Z.
5
Q 6
Encontrar, se existem, as soluc¸o˜es inteiras das congrueˆncias:
(i) 15x ≡ 12 mod 21;
(ii) 121x ≡ 22 mod 33.
Resposta: (i): Desde 3 = MDC(15, 21) | 12, a equac¸a˜o e´ compat´ıvel e e´ equivalente a`
equac¸a˜o:
5x ≡ 4 mod 7. (1)
Um inverso aritme´tico modulo 7 para 5 e´ 3 (de fato 5 · 3 = 15 ≡ 1 mod 7). Portanto a
equac¸a˜o (1) e´ equivalente a` x ≡ 5 mod 7 e tem como conjunto de soluc¸o˜es:
{5 + 7k| ∀k ∈ Z}.
(ii): Desde 11 = MDC(121, 33) | 22, a equac¸a˜o e´ compat´ıvel e e´ equivalente a` equac¸a˜o:
11x ≡ 2 mod 3. (2)
Um inverso aritme´tico modulo 3 para 11 e´ 2 (de fato 2 · 11 = 22 ≡ 1 mod 3). Portanto a
equac¸a˜o (2) e´ equivalente a` x ≡ 4 mod 3 e tem como conjunto de soluc¸o˜es:
{4 + 3k| ∀k ∈ Z}.
6
1 Q7
Encontrar, se existem, todas as soluc¸o˜es inteiras do sistema de equac¸o˜es de congrueˆncia:
x ≡ 2 mod 5
x ≡ 1 mod 3
x ≡ 6 mod 14
Resposta:A soluc¸a˜o geral da primeira equac¸a˜o e´:
x = 2 + 5y, ∀y ∈ Z. (1)
Substituindo na segunda equac¸a˜o, obtemos:
2 + 5y ≡ 1 mod 3, o seja y ≡ 1 mod 3, do qual: y = 1 + 3z ∀z ∈ Z.
Substituindo y = 1 + 3z em (1), obtemos:
x = 2 + 5y = 2 + 5(1 + 3z) = 7 + 15z, ∀z ∈ Z. (2)
Substituindo na terceira equac¸a˜o, obtemos:
7 + 15z ≡ 6 mod 14, o seja z ≡ 13 mod 14, do qual: z = 13 + 14k ∀k ∈ Z.
Substituindo z = 13 + 14k em (2), obtemos:
x = 7 + 15z = 7 + 15(13 + 14k) = 202 + 210k, ∀k ∈ Z,
que e´ a soluc¸a˜o geral do sistema.
7
Q 8
Dado o seguinte sistema de equac¸o˜es de congrueˆncia, dependendo dos paraˆmetros a, b ∈ Z:{
ax ≡ 3 mod 5
3x ≡ b mod 8
(i) Determinar para quais a e b o sistema e´ compat´ıvel.
(ii) Para esses valores, escreva a soluc¸a˜o gene´rica do sistema, em func¸a˜o de a e b e pos-
sivelmente de seus inversos aritme´ticos a′ e b′ ( mod 5 e mod 8 respectivamente).
Resposta: (i): Os mo´dulos das duas equac¸o˜es sa˜o coprimos. A segunda equac¸a˜o e´
compat´ıvel porque MDC(3, 8) = 1. A primeira equac¸a˜o e´ compat´ıvel, se e somente se,
MDC(a, 5) | 3, o seja, se e somente se, 5 - a ⇔ a 6≡ 0 mod 5. Portanto, o sistema e´
compat´ıvel, se e somente se, a 6≡ 0 mod 5.
(ii): A segunda equac¸a˜o e´ equivalente a x ≡ 3b mod 8 (porque 3 e´ um inverso aritme´tico
modulo 8 para 3) e tem a soluc¸a˜o geral:
x = 3b+ 8y, ∀y ∈ Z. (1)
Substituindo na primeira equac¸a˜o, obtemos:
3ab+ 8ay ≡ 3 mod 5, o seja 3ab+ 3ay ≡ 3 mod 5 ⇔ ay ≡ 1− ab mod 5. (2)
Seja a′ um inverso aritme´tico modulo 5 para a. Podemos escrever a ultima equac¸a˜o de (2)
como:
y ≡ a′(1− ab) mod 5, do qual y = a′(1− ab) + 5k, ∀k ∈ Z. (3)
Substituindo (3) em (1), obtemos:
x = 3b+ 8a′(1− ab) + 40k, ∀a 6≡ 0 mod 5 e ∀k ∈ Z.
que e´ a soluc¸a˜o geral do sistema.
8
Q 9
(i) Sejam a,m inteiros com m > 0 e tais que MDC(a,m) = 1. Mostrar que aφ(m)−1 e´
um inverso aritme´tico de a modulo m.
(ii) Utilizar o me´todo anterior para calcular os inversos aritme´ticos 1 ≤ a∗ ≤ 6 modulo
7 dos inteiros a ∈ {1, 2, 3, 4, 5, 6}.
Resposta: (i): Pelo Teorema de Euler-Fermat, temos aφ(m) ≡ 1 mod m. Seja a′ um
inverso aritme´tico modulo m para a (que existe porque MDC(a,m) = 1). Enta˜o:
a′aφ(m) ≡ a′ mod m ⇔ aφ(m)−1 ≡ a′ mod m.
(ii): φ(7) = 6, portanto:
• 15 = 1 e´ o inverso aritme´tico de 1 modulo 7;
• 25 = 23 · 22 ≡ 4 mod 7 e´ o inverso aritme´tico de 2 modulo 7;
• 35 = 32 · 32 · 3 ≡ 5 mod 7 e´ o inverso aritme´tico de 3 modulo 7;
• 45 = (25)2≡ 16 ≡ 2 mod 7 e´ o inverso aritme´tico de 4 modulo 7;
• 55 ≡ (−2)5 ≡ −4 ≡ 3 mod 7 e´ o inverso aritme´tico de 5 modulo 7;
• 65 = (2 · 3)5 = 25 · 35 ≡ 4 · 5 ≡ 6 mod 7 e´ o inverso aritme´tico de 6 modulo 7.
9
Q 10
Dado o numero natural n = 13342.
(i) Utilizando o Teorema de Euler-Fermat, calcular os u´ltimos dois algarismos de n.
(ii) Utilizando o Teorema chineˆs do resto, calcular os u´ltimos tres algarismos de n.
Resposta: (i): Vale 13342 ≡ 33 mod 100. Desde MDC(33, 100) = 1, pelo Teorema de
Euler-Fermat, temos que 33φ(100) ≡ 1 mod 100. Agora φ(100) = φ(25)φ(4) = (25− 5)(4−
2) = 40. Portanto:
3342 ≡ 3340 · 332 ≡ 1089 ≡ 89 mod 100.
Enta˜o os u´ltimos dois algarismos de 13342 sa˜o 89.
(ii): Temos que solucionar a congrueˆncia 13342 ≡ x mod 1000. Desde MDC(8, 125) = 1,
pelo Teorema Chineˆs do resto, temos que a congrueˆncia dada e´ equivalente ao sistema de
equac¸o˜es de congrueˆncias: {
x ≡ 13342 mod 8
x ≡ 13342 mod 125
Reducimos 13342 modulo 8 e modulo 125.
modulo 8 : 133 ≡ 5 mod 8 e temos 542 ≡ (52)21 ≡ 121 ≡ 1 mod 8.
modulo 125 : 133 ≡ 8 mod 125. Ale´m disso 842 = 2126. Desde MDC(2, 125) = 1, pelo
Teorema de Euler-Fermat, temos que 2φ(125) ≡ 1 mod 125. Agora φ(125) = 100. Portanto:
2100 ≡ 1 mod 125. Enta˜o:
13342 ≡ 2126 ≡ 226 ≡ (27)3 · 25 ≡ 1283 · 32 ≡ 33 · 32 ≡ 864 ≡ 114 mod 125.
Fica para solucionar o sistema de equac¸o˜es de congrueˆncias:{
x ≡ 1 mod 8
x ≡ 114 mod 125
E´ fa´cil ver que isso tem como soluc¸a˜o geral x = 489 + 1000k. Portanto os u´ltimos tres
algarismos de 13342 sa˜o 489.
10